ソートのアルゴリズムの中でも最も速いとされているのがクイックソートだ。
平均計算量は O(n log n) とされている。しかし最悪のケースの場合は
O(n^2) である。
このアルゴリズムは、
- データを半分に分ける。例 9452353381 の並びのデータの場合、94523 5 3381 というように、真ん中へんの 5 でデータを左右にわける。
- 分けた場所にあった1つのデータ（上の例では 5、下のコードでは middle という名前の変数）と、左右に分けたデータの大小をを1つずつ比べる。比較したデータが大きかったらそのデータより右の方へ、小さかったら左の方へと振り分ける（分割という）。このときに、左に振り分けたデータ、右に振り分けたデータの並びはなんでもいい。とにかく真ん中の値と比べて、ひたすら左右に振り分けるのである。
- 左右に振り分けるのだから当然その入れ物が必要になる。下のコードでは
List<integer> left = new ArrayList<integer>();
List<integer> right = new ArrayList<integer>();
としているところがそう。いわゆるキュー（として ArrayList）を用意している。
- 左右に振り分けたデータを、1. に戻ってさらにまた半分に分けて同じことを繰り返す。
- 同じことを繰り返すということは、データをどんどん半分半分にしていくということだから、最後は 2か3つのデータしか残らなくなる。そうなったら比較するものがなくなったので分割していったデータを組み立てていく。なぜなら、分割した最小単位のデータはすでにソートされているし、左右に振り分けていたのだから最初に半分に分けたデータよりも大きいか小さいかのデータの塊となっているからだ。
import java.util.*;
public class Sort {
private Sort() {
}
public static void output(List<Integer> data) {
for(int i = 0, n = data.size(); i < n; i++)
System.out.print(data.get(i) + ", ");
System.out.println();
}
public static List<Integer> quicksort(List<Integer> data) {
if(data.size() < 1) return new ArrayList<Integer>();
Integer middle = data.get(data.size() / 2);
List<Integer> left = new ArrayList<Integer>();
List<Integer> right = new ArrayList<Integer>();
for(int i = 0, n = data.size(); i < n; i++) {
// pass through the pivot data: data[data.size() / 2]
if(i != data.size() / 2) {
if(data.get(i) <= middle) { // leftward, rightward spreading
left.add(data.get(i));
} else {
right.add(data.get(i));
}
}
}
List<Integer> result = new ArrayList<Integer>();
result.addAll(quicksort(left));
result.add(middle);
result.addAll(quicksort(right));
output(result);
return result;
}
public static void main( String[] args ) {
List<Integer> data = new ArrayList<Integer>();
data.add(9); // 0
data.add(4); // 1
data.add(5); // 2
data.add(2); // 3
data.add(3); // 4
data.add(5); // 5
data.add(3); // 6
data.add(3); // 7
data.add(8); // 8
data.add(1); // 9
Sort.output(Sort.quicksort(data));
}
}
コンパイルは
javac Sort.java
実行は
java Sort
トラックバック URL:
https://perltips.twinkle.cc/trackback/299