【アルゴリズム解説】選択ソートとは

2020/5/27 2020/5/27 書き溜め

今回は、アルゴリズムの整列問題「選択ソート」について書き溜め
新しく計算機科学を学ぶ人のためのマイルストーンを残していく。

概要

選択ソート

小さい数字から決定していく

選択ソートとは、ソート(整列問題)に関するアルゴリズムの一つです。
配列された要素から、最大値やまたは最小値を探索し配列最後の要素と入れ替えを行い整列させていきます。

選択ソートアルゴリズム

選択ソートのアルゴリズムはWikipediaを参照する。

データ列中で一番小さい値を探し、1番目の要素と交換する。
次に、2番目以降のデータ列から一番小さい値を探し、2番目の要素と交換する。
これを、データ列の最後まで繰り返す（厳密には、データ列の最後より1つ手前までの繰り返しでよい。
一つ前まで交換済みであれば、最後（残り）は必ず最大値になるからである）。
大小が入れ替わる降順の場合も同様の手法である。

目的の条件の値(最小の値)を選択し並び替えていく。

選択ソートの計算量は

データ数nのときのアルゴリズム計算量はO(n^2)である。

バブルソート同様、学習用途で利用されるアルゴリズムで
ライブラリなどで採用されることはほぼ無い。

選択ソートの改良版として、「ヒープソート」がある。

選択ソートをPython3で実装する

選択ソートをPython3実装すると下記のようになる。

arr = [8, 3, 4, 10, 2, 7, 5, 6];
print(arr)
print("====START====")

for i in range(len(arr)-1):
  _min = i
  for j in range(i, len(arr)-1):
    if arr[_min] > arr[j+1]:
      _min = j+1
  tmp = arr[_min]
  arr[_min] =  arr[i]
  arr[i] = tmp

print("====END====")
print(arr)

arr = [8, 3, 4, 10, 2, 7, 5, 6];

print(arr)

print("====START====")

for i in range(len(arr)-1):

_min = i

for j in range(i, len(arr)-1):

if arr[_min] > arr[j+1]:

_min = j+1

tmp = arr[_min]

arr[_min] = arr[i]

arr[i] = tmp

print("====END====")

print(arr)

(*天才による指摘はいつでも受け付けている)

選択ソートをJavaで実装する

選択ソートをJava実装すると下記のようになる。

class SelectionSort {
  public static void main(String[] args){
    int[] arr = { 8, 3, 4, 10, 2, 7, 5, 6 };
    System.out.println("start");
    for (int i=0; i<arr.length; i++) System.out.print(arr[i]);

    for (int i=0; i < arr.length; i++){
      int min = i;
      for (int j=i; j<arr.length; j++){
        if (arr[min] > arr[j]){
          min = j;
        }
      }
      int tmp = arr[min];
      arr[min] = arr[i];
      arr[i] = tmp;
    }

    System.out.println("");
    System.out.println("end");
    for (int i=0; i<arr.length; i++) System.out.print(arr[i]);
    System.out.println("");
  }
}

class SelectionSort {

public static void main(String[] args){

int[] arr = { 8, 3, 4, 10, 2, 7, 5, 6 };

System.out.println("start");

for (int i=0; i<arr.length; i++) System.out.print(arr[i]);

for (int i=0; i < arr.length; i++){

int min = i;

for (int j=i; j<arr.length; j++){

if (arr[min] > arr[j]){

min = j;

}

int tmp = arr[min];

arr[min] = arr[i];

arr[i] = tmp;

}

System.out.println("");

System.out.println("end");

for (int i=0; i<arr.length; i++) System.out.print(arr[i]);

System.out.println("");

}

(*天才による指摘はいつでも受け付けている)

選択ソートを説明しプログラムを書いてください。

さて、先程の説明を読んだ人は、選択ソートを説明できますね。
余裕の有る方は、好きな言語で選択ソートを実装してみてください。

ノートやメモに書くでも、Twitterに呟くでもYoutubeにアップロードするでも構いません。
今日知った情報をアウトプットしてみましょう。

じゃあね〜〜〜。