ソートアルゴリズム(5)

今回はちょっと変わり種のソートアルゴリズムであるボゴソートを紹介します。

このソートはリストが整列された状態になるまでひたすら無作為に並び替えて、偶然に整列された状態のリストが
できるまで繰り返す、という非常にシンプルなソートです。

ちょっと考えてみれば分かる通り、このソートは非常に性能が悪くてとても実用にはなりません。

以下はJavaコードによる実装例です。

sort/BogoSort.java

package sort;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
public class BogoSort {
  private static <E extends Comparable<E>> boolean isSorted(List<E> list) {
    for (int i = 1; i < list.size(); i++) {
      if (list.get(i - 1).compareTo(list.get(i)) > 0) {
    	return false;
      }
    }
    return true;
  }

  public static <E extends Comparable<E>> void sort(List<E> list) {
    // リストが整列されるまでシャッフルし続ける
    while (!isSorted(list)) {
      Collections.shuffle(list);
    }
  }
  public static void main(String[] args) {
    List<Integer> list = new ArrayList<Integer>();
    for (int i = 0; i < 10; i++) {
      list.add(i);
    }
    Collections.shuffle(list);
    System.out.println(list);
    sort(list);
    System.out.println(list);
  }
}

EeBlog(テクニカルブログ)

ソートアルゴリズム(5)