クイックソート

ソートアルゴリズムの最後を飾るのは、やはりクリックソートです。

クイックソートは、データの比較と交換回数が非常に少ないのが特徴で、一般的なばらばらデータ（ランダムに散らばっているデータ）に対して、最も効率良く並べ替えを実行します。

クイックソートは、実用上もっとも高速であるとされている並べ替えアルゴリズムで、多くのプログラムで利用されています。

考え方

ばらばらなデータが格納された配列 a[ ] が与えられた場合に、それらをクイックソートで並べ替える手順を、下の図に示します。

quick-sort-image.gif (8562 バイト)

まず始めに、「軸要素」と呼ばれるデータ値を決定します。この値は、データ全体を2つに分割するときのしきい値として使われます。軸要素は、分割が均等に行われるように選ぶのが望ましいのですが、その選択に時間をかけると、かえって並べ替えの時間を大きくしてしまいます。一般には、次のような方法がよく用いられているようです。

  1. データの先頭の要素を軸要素とする
  2. ランダムに1つ選ぶ
  3. ランダムに3つ選んで、その中央値を取る
  4. 左から見て最初に得られた2つの異なる値の大きいほうを取る

上の図では、最後の方法で軸要素を決定しています。

データの先頭から軸要素以上のデータを検索し、データの末尾から軸要素未満のデータを検索し、見つかった場合、それぞれを交換します。この作業を検索ラインが交差するまで続けて、交差した場所でデータを2つに分割します。

分割されたそれぞれのデータに対して同様の処理を繰り返します。

これを再帰的に繰り返していくと、最終的にすべてのデータが小さい順に並び替わります。

アルゴリズム

Java で書かれたクイックソートアルゴリズムを以下に示します。

  /*
   * 軸要素の選択
   * 順に見て、最初に見つかった異なる2つの要素のうち、
   * 大きいほうの番号を返します。
   * 全部同じ要素の場合は -1 を返します。
   */
  int pivot(int[] a,int i,int j){
    int k=i+1;
    while(k<=j && a[i]==a[k]) k++;
    if(k>j) return -1;
    if(a[i]>=a[k]) return i;
    return k;
  }

  /*
   * パーティション分割
   * a[i]〜a[j]の間で、x を軸として分割します。
   * x より小さい要素は前に、大きい要素はうしろに来ます。
   * 大きい要素の開始番号を返します。
   */
  int partition(int[] a,int i,int j,int x){
    int l=i,r=j;

    // 検索が交差するまで繰り返します
    while(l<=r){

      // 軸要素以上のデータを探します
      while(l<=j && a[l]<x)  l++;

      // 軸要素未満のデータを探します
      while(r>=i && a[r]>=x) r--;

      if(l>r) break;
      int t=a[l];
      a[l]=a[r];
      a[r]=t;
      l++; r--;
    }
    return l;
  }

  /*
   * クイックソート（再帰用）
   * 配列aの、a[i]からa[j]を並べ替えます。
   */
  public void quickSort(int[] a,int i,int j){
    if(i==j) return;
    int p=pivot(a,i,j);
    if(p!=-1){
      int k=partition(a,i,j,a[p]);
      quickSort(a,i,k-1);
      quickSort(a,k,j);
    }
  }

  /*
   * ソート
   */
  public void sort(int[] a){
    quickSort(a,0,a.length-1);
  }

このアルゴリズムは、軸要素の決定に上記の 4. の方法を使用しています。

メソッド pivot() は、軸要素となるデータの番号を返します。もし、すべてのデータが同じ値を持つ場合、それ以上の分割は必要ないので -1 を返します。

メソッド partition() は、pivot() で得られた軸要素を使用してデータを2つのブロックに分割します。このメソッドは、分割した点の番号を返します。

そして、メソッド quickSort() は、与えられた配列 a[ ] の a[i]〜a[j] の範囲を並べ替えます。データを分割する毎に、再帰的にこのメソッドを呼び出すことで、データの並べ替えを行っています。

クイックソートの動作

クイックソートを可視化して行うアプレットを、下に示します。

これを見ると、まず全体が大きく上下に分割されて並べ替わり、さらに上側が2つに分かれて並べ替わり…という手順が繰り返されることがわかります。

計算時間の評価

クイックソートアルゴリズムでは、データを分割しながら、

の2つの処理を繰り返します。したがって、まず、これら2つの処理に要する時間量を求めます。

pivot(a,i,j) は、配列 a[ ] の i 番目から j 番目までの要素の中から、軸要素として使用するデータの番号を検索します。この処理は、i から j までを順番に検索しますから、検索する要素数分の O(j - i +1) の時間を要します。

partition(a,i,j,x) は、配列 a[ ] の i 番目から j 番目までの範囲を、前後から検索して交差するまで x を軸としてデータの入れ替えを行いますから、やはり、O(j - i +1) の時間を要します。

したがって、これらの処理にはどちらもデータ数に比例した時間がかかることがわかります。

データの分割がもっとも効率よく行われると、各データは2分割ずつされていきますから、クイックソートの分割の深さは、データ数を N をすると log(N) になります。このとき、各深さのデータ数はすべて N ですから、この場合のクイックソートの総時間量は O(N log(N)) になります。

しかし、分割がアンバランスになる場合もあります。最悪の場合は、分割が 1:N-1 に行われつづけた場合で、この場合、クイックソートの分割の深さは N となり、それぞれのデータの深さは N , N , N-1 , N-2 , … , 3 , 2 となります。したがって、この場合のクイックソートの総時間量は、

N + N + N-1 + N-2 + … + 3 + 2 = N2/2 + 3N/2 -1

となり、オーダーは O(N2) となります。

また、平均的な場合として、すべて異なる一様分布のデータに対しては、O(N log(N)) になることが知られています。

← prev | next →