ソート・ルーチン (4)クイック・ソート

今まで、「速いソート・ルーチン」としてシェル・ソートやコム・ソート、ヒープ・ソートを紹介してきました。今回は最後に残された「速いソート・ルーチン」として「クイック・ソート」を紹介します。クイック・ソートは、その名が示す通り現時点で最高速を誇るアルゴリズムとして知られ(補足1)、初期化の手間が要らず、細部の処理も簡潔であることからヒープ・ソートよりもさらに処理は速くなります。

1) クイック・ソートのアルゴリズム

「クイック・ソート(Quick Sort)」のアルゴリズムは、上にも書いたようにいたってシンプルです。

配列中の適当な要素を「ピボット(Pivot)」として選び、仮に x とする。
x より小さい要素を配列の先頭方向に、x より大きい要素を配列の末尾方向に移動して、配列を二つの区間に分割する。
各区間に要素がひとつしか含まれない状態になるまで、それぞれの分割した区間に対して 1, 2 を繰り返す。

配列の先頭位置を L、末尾位置を R とする。
先頭から末尾方向へ L を移動させながら順に走査して " x 以上" の要素を探す。
末尾から先頭方向へ R を移動させながら順に走査して " x 以下" の要素を探す。
L < R ならば、L の指す要素と R の指す要素を交換して 2 以降を繰り返す。
L ≥ R ならば、走査した位置がすれ違っているため分割は終了している。

x として全くでたらめな数値を使用してもアルゴリズムは正常に動きますが、配列中の値を使用するとその位置で必ず走査が停止するため「番人」の役割を持たせることになり、走査位置が配列の先頭(または末尾)に達したかをチェックする必要がなくなって処理を簡略化することができます。配列を分割する処理で x 以上(または x 以下)の値を探すようにしているのは、x が「番人」として働くようにするためです。

例を見れば分かるように、L と R がすれ違った時点で L は必ず x 以上の要素を持つ配列の先頭を、また R は x 以下の要素を持つ配列の末尾をそれぞれ示すことになります(但し、両者が「番人」と等しい同じ位置の要素を示す場合もあります)。

クイック・ソートのサンプル・プログラムを以下に示します。

/*
  QuickSort : クイック・ソートによるソート・ルーチン

  Ran first, last : ランダム・アクセス反復子(ソート開始と終了)
  Less less : 要素比較用関数オブジェクト(boolを返す二項叙述関数)
*/
template<class Ran, class Less> void QuickSort( Ran first, Ran last, Less less )
{
  // 反復子の要素の型
  typedef typename Ran::value_type value_type;

  if ( last - first <= 1 ) return;

  value_type x = first[( last - first ) / 2]; // ピボット
  Ran l = first;
  Ran r = last - 1;

  for (;;) {
    while ( less( *l, x ) ) ++l;
    while ( less( x, *r ) ) --r;
    if ( l >= r ) break;
    swap( l, r );
    ++l;
    --r;
  }
  QuickSort( first, l, less );
  QuickSort( l, last, less );
}

クイック・ソートのアルゴリズムは再帰的であり、コーディングも再起呼び出しを使用することですっきりとした形で記述できます。サンプル・プログラムの中では、分割したそれぞれの配列を処理するため最後の二行で自分自身を呼び出しています。
L は x 以上の要素を持つ配列の先頭を示すと同時に、x 以下の要素を持つ配列の末尾の次の要素を示すことにもなります。したがって再起呼び出し時には L のみを用いれば充分です。

2) さらなる高速化

一般に、高速化のために処理を複雑にしたソート・アルゴリズムの場合、要素数が少ない場合は単純なソート・アルゴリズムよりも遅くなる傾向にあります。クイック・ソートも例外ではなく、要素数が充分少ないときにはクイック・ソートではなくもっと単純なソート・ルーチン(例えば挿入ソート)を使用した方が処理は速くなります。
クイック・ソートは再帰的なアルゴリズムであるため、配列が細かく分割するにつれてその数も多くなり、処理速度が極端に下がってしまいます。そこで、処理を行う前に要素数をチェックして、充分小さい場合は単純なソート・アルゴリズムに切り替えることにより、処理は高速になります。

/*
  CombinedQuickSort : クイック・ソートによるソート・ルーチン(途中で他のソート法に切り替える)

  Ran first, last : ランダム・アクセス反復子(ソート開始と終了)
  Less less : 要素比較用関数オブジェクト(boolを返す二項叙述関数)
  void (*func)( Ran, Ran, Less ) : 切り替え用ソート・ルーチン
  typename Ran::difference_type min : 切り替えを行うデータ数最小値
*/
template<class Ran, class Less> void CombinedQuickSort( Ran first, Ran last, Less less, void (*func)( Ran, Ran, Less ),
                                                        typename Ran::difference_type min )
{
  // 反復子の要素の型
  typedef typename Ran::value_type value_type;

  if ( last - first <= min ) {
    func( first, last, less );
    return;
  }

  value_type x = first[( last - first ) / 2]; // ピボット
  Ran l = first;
  Ran r = last - 1;

  for (;;) {
    while ( less( *l, x ) ) ++l;
    while ( less( x, *r ) ) --r;
    if ( l >= r ) break;
    swap( l, r );
    ++l;
    --r;
  }
  CombinedQuickSort( first, l, less, func, min );
  CombinedQuickSort( l, last, less, func, min );
}

この例では、データ数が min 以下になったら単純ソート・アルゴリズムでソートするように切り替えています。対象のソート・ルーチンは func で渡すようにして、任意のアルゴリズムに切り替えることができるようにしています。

3) 動作テスト

まずは、データ数に対する処理時間の計測結果を以下に示します。テスト回数は 20 回で、その平均値を示しています。

表 3-1. データ数に対する処理時間の推移
数列の種類	ソート法	数列のサイズ
数列の種類	ソート法	8000	16000	32000	64000	128000	256000
ランダムな数列	QuickSort	0.0017	0.0025	0.0047	0.0093	0.020	0.033
	std::sort	0.00056	0.0014	0.0027	0.0059	0.011	0.022
	std::stable_sort	0.0011	0.0029	0.0044	0.0073	0.016	0.033
ソート済みの数列	QuickSort	0.00034	0.00073	0.0014	0.0033	0.0049	0.0076
	std::sort	0.00016	0.00024	0.00050	0.00099	0.0017	0.0041
	std::stable_sort	0.00043	0.00062	0.0005	0.0011	0.0031	0.0090
逆ソートした数列	QuickSort	0.00020	0.00034	0.00081	0.0022	0.0044	0.0073
	std::sort	0.00065	0.00023	0.00060	0.00084	0.0016	0.0040
	std::stable_sort	0.00049	0.0012	0.0016	0.0019	0.0052	0.011
前要素が0	QuickSort	0.00028	0.00044	0.0019	0.0028	0.0060	0.012
	std::sort	0.000092	0.00018	0.00038	0.00095	0.0029	0.0047
	std::stable_sort	0.00064	0.00031	0.00071	0.0017	0.0035	0.0091

グラフ 3-1. データ数に対するクイック・ソートの処理時間

グラフ 3-2. STL の sort / stable_sort との処理時間比較

ランダムな数列に対しては、前回の「ヒープ・ソート」とほぼ同程度の速度という結果になりました。比較用のソート法として、Standard Template Library(STL) にある sort と stable_sort (補足2) の両関数に対して処理したときの時間もあわせて示してありますが、こちらはさらに短い時間で処理することができます。

クイック・ソートの処理時間は、ヒープ・ソートの場合と同様に、平均的にはデータ数 N に対して N・log₂N にほぼ比例します。したがって、グラフはほぼ直線を描いています。ソート済みの配列は交換作業がほとんどなくなり、逆ソートされた配列ははじめのパスでソート済み配列になるので、どちらもランダムな数列に比べて処理時間が短くなっています。
クイック・ソートを使用する場合、データ列の並び方によっては処理時間が N² にまで落ち込むことも考えられます。これはピボット x の取り方に大きく依存し、もし一回のパスでデータ列の最小値(または最大値)を選んでしまった場合、最小値(または最大値)だけからなるデータ列と、残り全ての要素を持つデータ列に分割されます。これが全てのパスで繰り返されると 1 パスごとに最小値(または最大値)を選ぶことになり、「バブル・ソート」などの遅いソート処理と変わらなくなってしまい、処理時間は N² のオーダーとなります。このようなことは滅多に起こることはありませんが、クイック・ソートにはこのような「最悪のケース」もあることを知っておく必要があります。このような現象を避けるために、ランダムに要素を選択した上でそのメディアン値(中央値)をピボットとして採用するなどの手法が考えられています。

途中で他のソート・ルーチンに切り替えた場合の計測結果を以下に示します。いずれも、データは乱数列でそのサイズは 256000、テスト回数は 20 回としています。

上側のグラフ 3-3 は、単純なソート法へ切り替えるときのデータ数を最大 100 まで変化させた場合の処理時間を示しています。0.033 付近にあるラインは通常の(切替を行わない)クイック・ソートによる処理時間になります。どのソート法を利用しても、データ数が 40 程度になるまでに切り替えれば、通常のクイック・ソートよりも速くなるという結果が得られました。特に効果が高いのが挿入ソートを使った場合で、切替時のデータ数が 15 から 100 になるまでの間、処理時間が変化しないという特有の現象も見られます。その処理速度は、STL の場合とほぼ同等なレベルとなっています。

下側のグラフ 3-4 は、切替時のデータ数をさらに大きくした場合の処理時間の推移を示しています。データ数が大きくなるに従い、単純なソート法の処理時間がデータ数の二乗のオーダーで増加することから急激に遅くなる傾向が見られ、たとえ挿入ソートを利用しても逆効果となります。以上から、切替時のソート法には挿入ソートを使い、データ数 50 程度を目安に切り替えるのが最も効率のよい手法であるという結果となりました。

補足1) バケット・ソート(Bucket sort)

今まで紹介したソート・ルーチンは「真面目に」処理を行うアルゴリズムばかりでしたが、対象とする要素に制限を加えれば、今まで紹介したアルゴリズムより処理速度の速いものも存在します。

ソート・ルーチンのアルゴリズムは、どれも「データの比較」と「データの交換」を行うことで並べ替えを実現していましたが、ここで紹介するアルゴリズムでは「データを数える」ことでソートを行います。例えば、要素の範囲が 0 から 255 であるデータ列をソートする場合、

とすることでソートはできてしまいます。このようなアルゴリズムを「バケット・ソート(Bucket Sort)」または「分布数えソート(Distribution Counting Sort)」といい、このように比較を必要としない(データの分布を利用してソートする)手法を「分布ソート(Distribution Sort)」というようです。アルゴリズムを見ればわかるように、この方法では要素の種類があらかじめ分かっているデータのソートしかできませんし、確保しなければならないカウンタ配列の大きさは要素の種類の数に依存することになります。しかし、取りうる要素を限定すれば(例えば文字列中に含まれる文字のソートを行うなど)、処理が単純でしかも処理速度がデータ数 N に比例するため圧倒的に早い処理が可能になります。

バケット・ソートのサンプル・プログラムを以下に示します。

/*
  BucketSort : バケット・ソートによるソート・ルーチン

  Ran first, last : ランダム・アクセス反復子(ソート開始と終了)
*/
template<class Ran> void BucketSort( Ran first, Ran last )
{
  // 反復子の要素の型
  typedef typename Ran::value_type value_type;

  vector<unsigned int> cnt( std::numeric_limits<value_type>::max(), 0 );

  for ( Ran r = first ; r < last ; ++r )
    ++cnt[*r];

  for ( unsigned int i = 0 ; i < cnt.size() ; ++i ) {
    for ( unsigned int j = 0 ; j < cnt[i] ; ++j ) {
      if ( first == last ) return;
      *first++ = i;
    }
  }
}

テンプレートを利用して任意の型のデータ列を処理可能としていますが、実際には符号なしの整数値で範囲の小さいもの、例えば unsigned char や unsigned short int 程度にしか利用できません。しかし、処理も単純なため処理速度は非常に速く、unsigned char 型の 256000 個のデータ列を処理する時間はクイック・ソートの 1 / 10 以下になります。

補足2) 安定なソート(Stable sort)

ソート処理の中で行われる比較処理において「等しい」と判断される要素が複数あったとき、元のデータ列の中での順序を保持する場合とそうでない場合があります。前者の場合は「安定なソート(Stable Sort)」といいます。したがって、後者は「安定でないソート」ということになります。安定なソートになるためには、等しい要素の前後関係が処理中に逆転しないことが必要になります。

単純なソートは全て安定なソートにすることができますが、安定なソートになるかどうかは比較方法に依存します。バブル・ソートをはじめとする交換ソートは、要素の配置を大小関係で判断して入れ替えることで並べ替えを行っているので、等しい場合も並べかえをしてしまえば安定なソートにはなりません。また、選択ソートの場合は、配列の末尾(または先頭)にあたる要素を探してから末尾(または先頭)と交換する処理を繰り返すので、末尾(または先頭)側に近い要素を優先して採用しないと安定なソートにはなりません。挿入ソートの場合、先頭から順にソートするのであれば、等しい要素が見つかった場合にその直後に挿入すれば安定なソートになります。
しかし、サイクル・ソートの場合だけは例外で、交換処理によって前後関係が逆転する可能性があるため安定なソートにすることはできません。例えば、交換処理によって未ソートな列の先頭に移動した要素が、未ソート列の中の最小値(昇順に並べていると仮定して)であった場合、それ以上移動することはありません。このとき、交換した要素の間にも最小値があれば、前後関係が逆転したままソートが完了することになります。

「(1) 遅いソート・ルーチン」で紹介したソート法で示したサンプル・プログラムの中では、選択ソートとサイクル・ソート以外は全て「安定なソート」になっています。

「シェル・ソート」「コム・ソート」「ヒープ・ソート」「クイック・ソート」といった速い部類のソートは通常全て「安定でないソート」になります。「シェル・ソート」や「コム・ソート」は適当な飛び幅を決めてソートしていることから前後関係は逆転する可能性があり「安定なソート」にはなりません。また「ヒープ・ソート」も要素をふるい落とす時や末尾と根を交換する時に順序が逆転することを避けることができません。「クイック・ソート」の場合、前後にあるデータを入れ替えるときに順序が変わってしまいます。
「クイック・ソート」の場合、前方と後方の要素を交換するのではなく他のバッファに登録して(このとき、空になった位置は除外する必要があります)、走査位置がすれ違ったらその位置に空き領域を作って、その中に元の並び順を保った状態で挿入すれば前後関係は保つことができます。しかし、処理速度を犠牲にすることは避けられなくなります。

安定なソートでなければならない場面はそれほど発生することはありません。すでにある規則にしたがってソートされていたとして、等しい要素の順序はそのままに別の方法でソートする場合に利用することになりますが、そのときは前の規則も含めて比較処理を行えば済みます。比較処理時間が極端に長くなる場合や、比較処理自体に制限がある場合に安定なソートが必要となる可能性があります。