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

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

以下は 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());
  }
}