今回はクイックソートを紹介します。

クイックソートの基本的な考え方は、まずピボットと呼ばれる基準値を設定し、リストの要素をピボットの値以下の値と、より大きい値に分けます。そしてピボットをそのリストの中心の値とします。そして、２つに分けた部分リストのそれぞれに対して再帰的にクイックソートを適用することでソートします。

以下は Java でのクイックソートの実装例です。

sort/QuickSort.java

package sort;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class QuickSort {
 public static <E extends Comparable<E>> void sort(List<E> list) {
  if (list.size() < 2) {
   return;
  }
  E pivot = list.get(0);
  int start = 1, last = list.size() - 1;
  while (start <= last) {
   while (start <= last) {
    if (list.get(start).compareTo(pivot) > 0) {
     break;
    }
    start++;
   }
   while (start <= last) {
    if (list.get(last).compareTo(pivot) <= 0) {
     break;
    }
    last--;
   }
   if (start <= last) {
    Collections.swap(list, start, last);
   }
  }
  Collections.swap(list, 0, start - 1);
  sort(list.subList(0, start -1));
  sort(list.subList(start, list.size()));
 }
 
 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("before: " + list.toString());
  sort(list);
  System.out.println("after : " + list.toString());
 }
}