O(N*log(N))のSorting Algorithm - Quick Sort(分割法)
http://d.hatena.ne.jp/yokolet/20080629#1214800194ではheapというデータ構造を利用するHeap Sortを試してみましたが、さらに速いと言われているQuick Sort(分割法)についても調べてみたのでメモです。
QUick Sortというのはpivot(あるいはmidpoint)とよばれる中央値を利用して、順番は維持したまま、それよりも小さいグループ、大きいグループに分けていくsortingです。例えば、[18, 6, 9, 1, 4, 12, 15, 5, 6, 7, 11]という数字の並びがあったとすると、このように進んでいきます。
[18, 6, 9, 1, 4, (12), 15, 5, 6, 7, 11] pivot: 12 [6, 9, 1, 4, (5), 6, 7, 11][12][18, (15)] pivot: 5, 15 [1, (4)][5][6, 9, (6), 7, 11][12][[15][18] pivot: 4, 6 [1][4][5][6][6][9, (7), 11][12][15][18] pivot: 7 [1][4][5][6][6][7][9, (11)][12][15][18] pivot: 11 [1][4][5][6][6][7][1][11][12][15][18]
Quick Sortはpivotが常にグループの平均値に近い値になっていれば、そのグループをうまく半分、半分、半分、、、に分けて(計算量O(log(N)))行けるので、平均でO(N*log(N))を期待できる手法です。が、最悪の場合はO(N^2)に落ちてしまいます。なぜなのかというと、pivotが運悪く常に最大値、あるいは最小値になってしまうと、グループを半分にしたつもりが最大値(あるいは最小値)と残り全部という組み合わせになってしまって、O(N)の比較をO(N)だけ繰り返すことになってしまうからです。例えば、同じ数値でも、[4, 6, 5, 11, 12, 18, 15, 9, 6, 7, 1]という並びになっていたとします。すると、
[4, 6, 5, 9, 12, (18), 15, 11, 6, 7, 1] pivot: 18 [4, 6, 5, 9, 12, (15), 11, 6, 7, 1][18] pivot: 15 [4, 6, 5, 9, (12), 11, 6, 7, 1][15][18] pivot: 12 [4, 6, 5, 9, (11), 6, 7, 1][12][15][18] pivot: 11 [4, 6, 5, (9), 6, 7, 1][11][12][15][18] pivot: 9 [4, 6, 5, (6), 7, 1][9][11][12][15][18] pivot: 6 ....
となってしまい、計算量が増えてしまいます。つまり、集団をちょうど半分に分けられるような、うまいpivotを選択するアルゴリズム取り入れると、O(N*log(N))の計算量を常に期待できるというものです。Quick Sortの改良版がいくつかあるのもうなずけます。
Java言語の場合、java.util.Arraysのうち、プリミティブな型の配列を対象とするsort()メソッドにQuick Sortが採用されています。ただ、単なるQucik Sortではないらしく、APIドキュメントには"The sorting algorithm is a tuned quicksort, adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993). "という説明がありました。
java.util.Arrays#sort()を使えばいいだけではありますが、途中がどうなっているのかも眺めてみたかったので、Quick Sortのプログラムを書いてみました。このクラスのsort()メソッドで上記のQuick Sortのアルゴリズムを実装しています。sort()メソッドを再帰的に呼び出して、分割できるところまで分割してから、concatenate()メソッドで、合成を繰り返してソート済みの配列を作っています。
import java.util.ArrayList; public class QuickSort { private int inputs = {18, 6, 9, 1, 4, 12, 15, 5, 6, 7, 11}; private QuickSort() { ArrayListlist = new ArrayList args) throws InterruptedException { new QuickSort(); } } 実行結果 1|4| 9|11| 7|9|11| 6|6|7|9|11| 1|4|5|6|6|7|9|11| 15|18| 1|4|5|6|6|7|9|11|12|15|18|(); for (int value : inputs) { list.add(value); } sort(list); } private static ArrayList concatenate( ArrayList left, int pivot, ArrayList right) { left.add(pivot); left.addAll(right); for (int value : left) { System.out.print(value + "|"); } System.out.println(); return left; } private ArrayList sort(ArrayList array) { if (array.size() <= 1) { return array; } int pivotIndex = array.size()/2; int pivot = array.get(pivotIndex); ArrayList left = new ArrayList (); ArrayList right = new ArrayList (); for (int i = 0; i < array.size(); i++) { if (i != pivotIndex) { int value = array.get(i); if (value <= pivot) { left.add(value); } else { right.add(value); } } } left = sort(left); right = sort(right); return concatenate(left, pivot, right); } public static void main(String
さて、ツリー全体を作り直すHeap Sortと違い、Quick Sortは分割された右側と左側は独立に動いていって、最後に合成されればいいはずです。つまり、それぞれスレッドに割り当てて実行できるはずです。せっかくなので、JDK 1.5で追加されたjava.util.concurrentパッケージのクラスを使ってQuick Sortを書き直してみました。このプログラムで使っている、Executors, ExecutorSerivceはスレッドプールを利用するためのクラスです。また、Callableはjava.util.Runnable#run()メソッドが戻り値を返せない問題を改善するために導入されたインタフェースです。QuickSortHandler#call()メソッドでQuick Sortのアルゴリズムを実装しているので、この再帰呼び出しをそれぞれスレッドに割り当てて実行して戻り値を取得しました。
import java.util.ArrayList;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
import java.util.concurrent.TimeUnit;
public class ConcurrentQuickSort {
private int inputs = {18, 6, 9, 1, 4, 12, 15, 5, 6, 7, 11};
private ExecutorService service;
private static ArrayList concatenate(
ArrayList left, int pivot, ArrayList right) {
left.add(pivot);
left.addAll(right);
for (int value : left) {
System.out.print(value + "|");
}
System.out.println();
return left;
}
private ConcurrentQuickSort() throws InterruptedException, ExecutionException {
ArrayList list = new ArrayList();
for (int value : inputs) {
list.add(value);
}
service = Executors.newCachedThreadPool();
service.submit(new QuickSortHandler(list));
service.awaitTermination(100, TimeUnit.MILLISECONDS);
service.shutdown();
}
public static void main(String args)
throws InterruptedException, ExecutionException {
new ConcurrentQuickSort();
}
class QuickSortHandler implements Callable {
private ArrayList array;
QuickSortHandler(ArrayList array) {
this.array = array;
}
public ArrayList call() throws InterruptedException, ExecutionException {
if (array.size() <= 1) {
return array;
}
int pivotIndex = array.size() / 2;
int pivot = array.get(pivotIndex);
ArrayList left = new ArrayList();
ArrayList right = new ArrayList();
for (int i = 0; i < array.size(); i++) {
if (i != pivotIndex) {
int value = array.get(i);
if (value <= pivot) {
left.add(value);
} else {
right.add(value);
}
}
}
Future leftResult = service.submit(new QuickSortHandler(left));
Future rightResult = service.submit(new QuickSortHandler(right));
return ConcurrentQuickSort.concatenate(leftResult.get(), pivot, rightResult.get());
}
}
}
実行結果(そのときの状況によって若干違う)
1|4|
15|18|
9|11|
7|9|11|
6|6|7|9|11|
1|4|5|6|6|7|9|11|
1|4|5|6|6|7|9|11|12|15|18|
この例にあげた11個程度の数のsortingではスレッドを使った効果は現れませんが、相当数のデータを並べ替えるようなケースでは違いがでるのでは。
Quick Sortの参考資料
