Java で、クイックソート（Quick Sort）を実装する。

ソートのアルゴリズムの中でも最も速いとされているのがクイックソートだ。平均計算量は O(n log n) とされている。しかし最悪のケースの場合は O(n^2) である。

このアルゴリズムは、 

    <li>データを半分に分ける。例 9452353381 の並びのデータの場合、94523 5 3381 というように、真ん中へんの 5 でデータを左右にわける。</li>
<li>分けた場所にあった1つのデータ（上の例では 5、下のコードでは middle という名前の変数）と、左右に分けたデータの大小をを1つずつ比べる。比較したデータが大きかったらそのデータより右の方へ、小さかったら左の方へと振り分ける（分割という）。このときに、左に振り分けたデータ、右に振り分けたデータの並びはなんでもいい。とにかく真ん中の値と比べて、ひたすら左右に振り分けるのである。</li>
<li>左右に振り分けるのだから当然その入れ物が必要になる。下のコードでは
<code>
List<integer> left   = new ArrayList<integer>();
List<integer> right  = new ArrayList<integer>();
</code>
としているところがそう。いわゆる<b>キュー</b>（として ArrayList）を用意している。</li>
<li>左右に振り分けたデータを、1. に戻ってさらにまた半分に分けて同じことを繰り返す。</li>
<li>同じことを繰り返すということは、データをどんどん半分半分にしていくということだから、最後は 2か3つのデータしか残らなくなる。そうなったら比較するものがなくなったので分割していったデータを組み立てていく。なぜなら、分割した最小単位のデータはすでにソートされているし、左右に振り分けていたのだから最初に半分に分けたデータよりも大きいか小さいかのデータの塊となっているからだ。</li>
import java.util.*; public class Sort { private Sort() { } public static void output(List data) { 
for(int i = 0, n = data.size(); i < n; i++)
System.out.print(data.get(i) + ", "); System.out.println(); } public static List quicksort(List 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

admin

Tags