今回は選択ソートを紹介します。

選択ソートのアルゴリズムは最初の要素から順に最後の要素まで調べて一番小さい値(昇順の場合)を一番最初の要素と入れ替え、今度は2つ目の要素から最後の要素まで調べて一番小さい値を2番目の要素と入れ替え・・・ということを最後まで繰り返す、というものです。

これはO(n^2)のアルゴリズムで効率がとても悪いですが、アルゴリズムがとても単純で分かりやすいのが特徴です。

以下はJavaによる選択ソートアルゴリズムの実装例です。

sort/SelectionSort.java

package sort; import java.util.List;
import java.util.ArrayList;
import java.util.Collections;

public class SelectionSort {

  private static <E> void swap(List<E> list, int index1, int index2) {
     E tmp = list.get(index1);
     list.set(index1, list.get(index2));
     list.set(index2, tmp);
  }

  public static <E extends Comparable<E>> void sort(List<E> list) {
     for (int i = 0; i < list.size(); i++) {
        int min = i;
        for (int j = i + 1; j < list.size(); j++) {
          if (list.get(min).compareTo(list.get(j)) > 0) { 
            min = j;
          } 
        } 
        swap(list, i, min);
     } 
  } 

  public static main(String[] args) {
    List<integer> list = new ArrayList<integer>();
    for (int i = 0; i < 10; i++) {
       list.add(i, i);
    }
    Collections.shuffle(list);
    System.out.println("before sorting: " + list);
    sort(list);
    System.out.println(" after sorting: " + list);
  }

}