トップページ > コンテンツ > 数学・アルゴリズム関連メモ > 数学・情報工学的 > ソートの種類 > クイックソート

はじめに基準となる値を決めておいて、それより大きい値のグループと小さい値のグループに分ける処理を繰り返すことで、ソートする方法。比較回数はデータの並び次第。
データの比較と交換回数が非常に少ないのが特徴で、一般的なばらばらデータに対して、最も効率良く並べ替えを実行する。

平均計算量	O(NlogN)
最悪計算量	O(N^2)

3

1

2

4

6

5

だった場合に基準値を3とすると、

1

2

が自分より小さいグループ、

4

6

5

が自分より大きいグループということで3の位置が確定する

1

2

③

4

6

5

これをさらにグループごとに基準値を決めて処理を行う。

実装は以下を参照のこと：
http://homepage3.nifty.com/teranet/JavaAlgorithm/QuickSort.html
http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/sort-algorithm/quick-sort.html

ちなみに2つ目の参照サイトのプログラムを引用し、実行結果を表示できるようにしたのが以下のコード。
他のソートのコードと統一するため多少変数を変更した。

public class QuickSort {
public static void main(String[] args) {
	int[] array = { 3, 2, 4, 6, 5, 1 };
	Selection select = new Selection();
	select.quickSort(array,0,array.length - 1);
	for (int i = 0; i < array.length; i++) {
		System.out.println(array[i]);
	}
}
public int pivot(int[] array, int left,int right) {
   int x = left + 1;
   while(x <= right && array[left] == array[x]) x++;
   if(x > right) return -1;
   if(array[left] >= array[x]) return left;
   return x;
}
public int partition(int[] array,int left,int right,int axis) {
   int l = left;
   int r = right;
   while(l <= r) {
      while(l <= right && array[l] < axis) l++;
      while(r >= left && array[r] >= axis) r--;   
      if(l <= r) {
         int temp=array[l];
         array[l]=array[r];
         array[r]=temp;
         l++;
         r--;
             }
  }
  return l;
        }
        public void quickSort(int[] array,int left,int right) {
    if(left == right) return;
    int p = pivot(array,left,right);
    if(p != -1) {
  	int x = partition(array,left,right,array[p]);
	quickSort(array,left,x-1);
	quickSort(array,x,right);
    }
}
}