ソート・ルーチン

(1) 遅いソート・ルーチン

今まで、図形描画に関するアルゴリズムをいくつか紹介してきましたが、今回はグラフィック関係から離れてソート(並び替え)のアルゴリズムを紹介したいと思います。
ソートは処理方法によってその実行時間が大きく変わるため、そのアルゴリズムについてはかなり古くから研究されてきたようで、すでに有名なものがたくさん存在しています。そのような中から、この章では比較的単純で実装が簡単なかわりに処理時間は長いアルゴリズムを紹介します。


1) 交換ソート(Exchange Sort)

データ列の二つの要素を比較・交換しながら並べ替える手法を総称して「交換ソート(Echange Sort)」といいます。最も基本的なアルゴリズムは「バブル・ソート(Bubble Sort)」と呼ばれるもので、遅いアルゴリズムとして有名です。しかし遅いと言っても、100 個程度のデータ列をソートするくらいなら充分実用的なものですし、単純なアルゴリズムなので実装も簡単です。

処理の流れとしては次のようになります。

  1. 配列先頭の二つの要素に注目し、大小関係が逆転していたらその位置を交換する。
  2. 注目する位置を一つ後ろにずらし、1 と同様の比較・交換作業を行う。
  3. 2 の操作を、配列の末尾に達するまで繰り返す。

ここまでを一回の"パス"とします。この時点では、配列の末尾にある要素は配列の最大値(降順の場合は最小値)となるので、次は末尾の要素を除いたデータ列について同様の操作を行います。以下、要素を末尾側から一つずつ減らしながら繰り返し比較・交換作業を行い、データ列の要素が一つになった時点でソートが完了することになります。

昇順でソートした場合の最初の"パス"の流れを例を使って示すと下図のようになります。下線の要素が比較対象で、太字は交換されたことを表しています。

5145116739812875|51 と 45 を比較
4551116739812875|51 と 45 を交換
4551116739812875|51 と 11 を比較
4511516739812875|51 と 11 を交換
4511516739812875|51 と 67 を比較
4511516739812875|67 と 39 を比較
4511513967812875|67 と 39 を交換
4511513967812875|67 と 81 を比較
4511513967812875|81 と 28 を比較
4511513967288175|81 と 28 を交換
4511513967288175|81 と 75 を比較
4511513967287581|81 と 75 を交換

以下、操作を繰り返すと上のデータ列は次のようにソートされていきます。例を見ると、ソートされた値が泡のようにデータ列の末尾へ浮かんでくるように見えるので、「バブル・ソート」と名づけられたようです。

5145116739812875|初期状態
45115139672875|81|1 パスめ
114539512867|7581|2 パスめ
1139452851|677581|3 パスめ
11392845|51677581|4 パスめ
112839|4551677581|5 パスめ
1128|394551677581|6 パスめ
11|28394551677581|7 パスめ
1128394551677581|ソート完了

バブル・ソートを用いたソート・ルーチンのサンプル・プログラムを以下に示します。

/*
  ランダム・アクセス反復子用 要素交換

  Ran r1, r2 : 要素交換対象の反復子
*/
template<class Ran> inline void swap( Ran r1, Ran r2 )
{
  typename Ran::value_type i = *r1;
  *r1 = *r2;
  *r2 = i;
}

/*
  BubbleSort : バブル・ソートによるソート・ルーチン

  Ran first, last : ランダム・アクセス反復子(ソート開始と末尾の次)
  Less less : 要素比較用関数オブジェクト(boolを返す二項叙述関数)
*/
template<class Ran, class Less> void BubbleSort( Ran first, Ran last, Less less )
{
  for ( Ran e = last ; e > first ; --e )
    for ( Ran s = first + 1 ; s < e ; ++s )
      if ( less( *s, *( s - 1 ) ) )
        swap( s - 1, s );
}

/*
  BubbleSort : バブル・ソートによるソート・ルーチン
               比較用関数オブジェクトとして less を利用する

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

ソート・ルーチンの引数は、STL(Standard Template Library) にある関数 sort() と合わせてあります。データ型が可変となるようテンプレートを使い、Ran はランダム・アクセス反復子(Random Access Iterator)を、Less は比較用関数オブジェクトをそれぞれ表します。反復子は、C 言語においてループ処理で用いるポインタを抽象化した概念で、次のような種類があります。

表 1-1. 反復子の種類
分類(略語)出力(Out)入力(In)前方(For)双方向(Bi)ランダム・アクセス(Ran)
読み出し(x = *p)不可
要素内へのアクセス(p->x)不可可 (p[]も)
書き込み(*p = x)不可
反復++++++++,--++,--,+,-,+=,-=
反復子の比較不可==,!===,!===,!===,!=,<,>,<=,>=

反復子の中で最も多くの演算子をサポートしているのが「ランダム・アクセス反復子」です。反復子 p の指し示す要素は *p を使って読み書きすることが可能で、p->x とすれば p の指し示すオブジェクトの x というメンバ変数やメンバ関数へ間接参照することもできます。ランダム・アクセス反復子はさらに p[i] を使って p から i 番目にある要素へアクセスすることも可能です。また、通常の反復子が次の(または前の)要素へ一つずつ移動させる手段しかないのに対して、ランダム・アクセス反復子は任意の位置にある要素の参照へ移動する手段を持ち、さらに反復子どうしの位置関係を調べるときに大小関係を含めた確認もできます(通常の反復子はせいぜい同値であるかを確認することしかできません)。
ランダム・アクセス反復子が利用できるコンテナ・クラスとしては、vectordeque や通常の配列などが挙げられます。また、文字列を扱うときに利用する string クラスも、文字列内の文字にアクセスするためにランダム・アクセス反復子を使うことができます。
ソート・ルーチンには、ソート対象のデータ列に対して開始と末尾の次の要素を示す反復子を渡します。末尾ではなくその次の要素に対する反復子であることに注意してください。これは STL の方式に合わせるためである他に、データ列全体に対してソートする場合は begin()end() の二つのメンバ関数をそのまま利用すれば済むようにできるからです。

* 反復子の具体的な利用方法については「ペイント・ルーチン (3)ペイント・ルーチンの応用」のサンプル・プログラムでも「コンテナ・クラス」と併せて紹介しています。

比較用関数オブジェクト Less には、bool を戻り値とする二項叙述関数(引数を二つ持つ関数)を定義する必要があります。二項叙述関数を持つ関数オブジェクトを定義するための規定クラスとしては binary_functionSTL に用意されています。また、以下に示すような要素比較用の汎用関数オブジェクト lessbinary_function の派生クラスとして STL にて定義されています。

template<class T> struct less : public std::binary_function<T,T,bool>
{
  bool operator()( const T& t1, const T& t2 ) const { return( t1 < t2 ); }
};

比較対象要素が演算子 < をサポートしている場合、あらかじめ用意された less オブジェクトを利用することができます。しかし、t1 < t2 の形で大小比較をすることができない要素を並べ替えたい場合(例えば、vector オブジェクトが要素となっている場合など)や、特殊な比較手段を用いたい場合(例えば文字列を、大文字・小文字は区別せずに比較したい時など)は、専用の比較用関数オブジェクトを用意してそれを呼び出すようにする必要があります。このとき、BubbleSort の中で operator() を呼び出していることからわかるように利用する関数オブジェクトは必ず operator() を必要とします。サンプル・プログラムの中では、比較用関数オブジェクトとして less をデフォルトで呼び出す形のルーチンも用意してあります。こちらは二つの反復子だけを渡すだけで利用することができます。
例として、データを逆順に並べ替える場合の実装方法を紹介します。この場合、t1 > t2 ならば true を返す関数オブジェクトを用意すればいいので、それを more クラスとして

template<class T> struct more : public std::binary_function<T,T,bool>
{
  bool operator()( const T& t1, const T& t2 ) const { return( t1 > t2 ); }
};

と定義します。あとは、

vector<unsigned int> data;

// データ列の作成
  :

BubbleSort( data.begin(), data.end(), more<unsigned int>() )

と実装すれば、逆順でのソートが可能になります。

n 個のデータ列をバブル・ソートを使って並べ替えた場合、要素を比較する回数は 1 から n - 1 までの和、即ち n( n - 1 ) / 2 になります。また、要素交換は大小関係が逆転している場合のみ発生するため、もしすでにソートされた状態であれば回数はゼロになりますが、逆順にソートされていれば比較回数と等しくなります。これは、バブルソートの処理速度がデータ列の要素数の二乗にほぼ比例することを意味しています。よって要素数が二倍になれば、処理速度は最大約 4 倍になります。


ところで、上にあげた例では計 7 パスで処理が完了していますが、データ列を見るとすでに 5 パス目で正しくソートされた状態になっています。このように、実際には途中で処理が完了する場合があるため、これを早めに検知できれば無駄な処理を省いて実行時間を短縮させることができます。
さらに、最後に交換が行われた位置を同時に記憶しておくことで、無駄な処理の省略が可能となります。というのも、最後に交換された位置より末尾側のデータ列はすでにソートされた状態であるため、比較・交換作業を行う必要がないからです。

この手法を用いてソート処理してみた場合の例を以下に示します。

1925315749738591|
19253149|57738591
|1925314957738591

上の例では、通常 7 パスの処理を必要としていたのに対して 2 パスで処理が完了しています。

この処理を加えた場合のコーディング例を以下に示します。

/*
  BubbleSort2 : バブル・ソートによるソート・ルーチン(改良版)

  Ran first, last : ランダム・アクセス反復子(ソート開始と終了)
  Less less : 要素比較用関数オブジェクト(boolを返す二項叙述関数)
*/
template<class Ran, class Less> void BubbleSort2( Ran first, Ran last, Less less )
{
  // 最後に要素を交換した位置(後ろ側を指す)
  Ran sorted;

  for ( Ran e = last ; e > first ; e = sorted ) {
    sorted = first; // 先頭の位置で sorted を初期化
    for ( Ran s = first + 1 ; s < e ; ++s ) {
      if ( less( *s, *(s - 1) ) ) {
        swap( s - 1, s );
        sorted = s;
      }
    }
    // 一度も交換がなければ終了
    if ( sorted == first ) break;
  }
}

この改良は、処理時間がデータ列の内容に大きく左右されてしまいます。極端な話、すでにソートされたデータに対して両者を比較した場合、後者の改良版の方が圧倒的に処理時間は短く、逆に降順でソートされたデータ列では両者のパスの回数は変わらないので、余計な処理が入っているだけ改良版の方が遅くなってしまいます。


バブル・ソートはアルゴリズム上の偏りがあり、比較・交換処理の進む方向によっても処理時間が左右されます。例えば

601020304050

のようなデータ列を「改良版バブル・ソート」ルーチンでソートした場合、配列の先頭から始める場合は 1 パス目でソートが完了し、2 パス目でソートが完了していることを確認してループを抜けるから、計 2 パスで処理が終わりますが、配列の末尾から比較・交換処理を始め、最小値が配列の先頭に浮き上がるようにした場合、5 パス分の処理が必要になります。逆に

203040506010

では、配列の先頭から処理を始める場合は 5 パス分、配列の末尾からの場合は 2 パス分となります。

そこで、一回のパスごとに処理の方向を切り替えてこの偏りをなくせば、平均的な性能は今より向上するのではないかと考えられます。
この発想のもとに生まれたバブル・ソートの変形版を「シェーカー・ソート(Cocktail Shaker Sort)」といいます。以下にサンプル・プログラムを示します。

/*
  ShakerSort : シェーカー・ソートによるソート・ルーチン

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

  Ran sorted;            // 最後に要素を交換した位置
  Ran s = first;         // 開始位置で s を初期化
  Ran e = sorted = last; // 末尾位置で e と sorted を初期化

  while ( e > s ) {
    /* 配列先頭からバブル・ソート */
    for ( Ran r = s ; r < e ; ++r ) {
      if ( less( *(r + 1), *r ) ) {
        swap( r, r + 1 );
        sorted = r;
      }
    }
    if ( sorted == s )
      break;
    else
      e = sorted;

    /* 配列末尾からバブル・ソート */
    for ( Ran r = e ; r > s ; --r ) {
      if ( less( *r, *(r - 1) ) ) {
        swap( r - 1, r );
        sorted = r;
      }
    }
    if ( sorted == e )
      break;
    else
      s = sorted;
  }
}

改良版バブル・ソートを、先頭から末尾への方向と末尾から先頭への方向に交互に繰り返しているだけの処理なので、難しいところはないと思います。


交換ソートには他に「奇偶転置ソート(Odd-even Transpotation Sort)」というものがあります。バブル・ソートやシェーカー・ソートが比較・交換処理を一方向または双方向に順次行うのに対して、奇偶転置ソートは奇数・偶数の添字を持つ隣りあった要素をペアとして比較・交換処理を行います。以下に例を示します。

51 4511 6739 8128 75
4551116739812875
4551 1167 3981 2875
4511513967288175
45 1151 3967 2881 75
1145395128677581
1145 3951 2867 7581
1139452851677581
11 3945 2851 6775 81
1139284551677581
1139 2845 5167 7581
1128394551677581

最初は一番目と二番目、三番目と四番目、という形でペアを作り、それぞれで比較・交換処理を行い、次に二番目と三番目、四番目と五番目、という形で同じように処理を行います。これを繰り返すと、だんだんとソートされていく様子がこの例からも分かります。交換したペアが一つもなくなれば、全ての値がソートされたことになり処理は完了です。

以下に、奇偶転置ソートのサンプル・プログラムを示します。

/*
  OddEvenSort : 奇偶転置ソートによるソート・ルーチン

  Ran first, last : ランダム・アクセス反復子(ソート開始と終了)
  Less less : 要素比較用関数オブジェクト(boolを返す二項叙述関数)
*/
template<class Ran, class Less> void OddEvenSort( Ran first, Ran last, Less less )
{
  bool sorted = false; // ソートが完了したか
  while ( ! sorted ) {
    sorted = true;
    /* 偶・奇ペアでのソート */
    for ( Ran r = first + 1 ; r < last ; r += 2 ) {
      if ( less( *r, *(r - 1) ) ) {
        swap( r - 1, r );
        sorted = false;
      }
    }

    /* 奇・偶ペアでのソート */
    for ( Ran r = first + 2 ; r < last ; r += 2 ) {
      if ( less( *r, *(r - 1) ) ) {
        swap( r - 1, r );
        sorted = false;
      }
    }
  }
}

奇偶転置ソートの場合、N 個ある要素を偶奇または奇偶ペアで比較・交換するのに約 N / 2 回の処理が行われます。これを一パスとしたとき、パスの数が最も多くなるのは逆順で並んだデータ列を並べ替える場合で N なので、処理回数は最悪の場合、約 N2 / 2 程度となり、バブル・ソートと変わりません。奇偶転置ソートの利点は、要素を比較・交換するペアは一つのパスの中で独立なので並列処理が実現可能である点になります。


最後に紹介する交換ソートは「ノーム・ソート(Gnome Sort)」です。ノーム・ソートの処理の流れは次のようになります。

  1. ある位置にある隣接した要素を比較し、必要であれば交換する。
  2. 要素を交換した場合、処理対象の要素の位置を一つ前にずらす(但し、すでに先頭が対象である場合は一つ後ろにずらす)。
  3. 要素を交換しなかった場合は位置を一つ後ろにずらす。
  4. これらの処理を繰り返し、末尾の位置まで要素の交換が発生しなかった場合は処理完了とする。

以下に例を示します。

5145116739812875|1, 2 番目の要素を比較
4551116739812875|1, 2 番目の要素を交換
4551116739812875|先頭なので一つ後ろの 2, 3 番目の要素を比較
4511516739812875|2, 3 番目の要素を交換
4511516739812875|交換したので一つ前の 1, 2 番目の要素を比較
1145516739812875|1, 2 番目の要素を比較
1145516739812875|先頭なので一つ後ろの 2, 3 番目の要素を比較
1145516739812875|交換不要なので一つ後ろの 3, 4 番目の要素を比較
1145516739812875|交換不要なので一つ後ろの 4, 5 番目の要素を比較
1145513967812875|4, 5 番目の要素を比較
1145513967812875|交換したので一つ前の 3, 4 番目の要素を比較
:(以下、繰り返し)

交換処理を行ったとき、それによって大小関係が崩れる可能性があるのは、交換したペアの前側とその直前の要素か、ペアの後ろ側とその直後の要素のいずれかになります。先頭から順に比較・交換処理をするならば、交換処理が発生した場合は今までソート済みだった前方のデータ列をもう一度確認し、問題がないことが確認できた場所から後ろ側の処理を再開するようにすれば、末尾まで達した段階でソートは完了していることになります。

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

/*
  GnomeSort : ノーム・ソートによるソート・ルーチン

  Ran first, last : ランダム・アクセス反復子(ソート開始と終了)
  Less less : 要素比較用関数オブジェクト(boolを返す二項叙述関数)
*/
template<class Ran, class Less> void GnomeSort( Ran first, Ran last, Less less )
{
  for ( Ran r = first + 1 ; r < last ; ++r ) {
    do {
      if ( ! less( *r, *( r - 1 ) ) ) break;
      swap( r - 1, r );
      --r;
    } while ( r > first );
  }
}

サンプル・プログラムを見れば分かるように、実装は非常に単純になります。データ列全体を走査して処理を行うのではなく、比較・交換処理を行う位置を前後に移動しながら処理を行うようになっているので、データ列を読み込んでいる間に並列で並べかえを行うような処理も可能です。そのような場合、読み込まれた要素の末尾まで達したらいったん処理を中断し、ある程度データが追加されたら処理を再開するようにすればよいわけです。

ノーム・ソートは、2000 年に Hamid Sarbazi-Azad によって紹介されたのが最初のようで、その時は Stupid Sort と名付けられていました。その後、Dick Grune によって Gnome Sort と改名されています。Hamid によれば、ソート・アルゴリズムには

の二種類があって、ノーム・ソートはそのいずれにも当てはまらない新しいアルゴリズムであると紹介しています。しかし実際には、ノーム・ソートは後述する「単純挿入法」によく似た処理方法を持っています。なお、ループは一つだけで足りるという特徴を持っていますが、サンプル・プログラムでは二重ループの形になっています。前方・後方の移動の切り替えを別のやり方にすれば、ループを一つにすることは簡単にできます。


2) 選択ソート(Selection Sort)

「選択ソート(Selection Sort)」は、配列の最大値(あるいは最小値)を配列の末尾へ移動して一つずつ配列の要素数を減らしていくところはバブル・ソートと同じですが、二要素ずつ比較しながら最大値を順に移動させるのではなく、配列から最大値を検索してその値と末尾の要素を交換することで実現させているところが異なっています。例をあげると下図のようになります。

5145116739812875|
51451167397528|81
514511673928|7581
5145112839|677581
39451128|51677581
392811|4551677581
1128|394551677581
11|28394551677581
|1128394551677581

下線で示した要素が交換対象で、太字になっているのが最大値です。処理の最後の方で、すでに最大値が未ソート列の末尾にあるのが見られますが、この場合は交換処理は不要ということになります。この例からわかるように、選択ソートは交換作業が一パスの中で一回だけになるので、バブル・ソートよりは高速に処理することができるようになります。


以下にコーディング例を示します。

/*
  SelectionSort : 選択ソート

  Ran first, last : ランダム・アクセス反復子(ソート開始と終了)
  Less less : 要素比較用関数オブジェクト(boolを返す二項叙述関数)
*/
template<class Ran, class Less> void SelectionSort( Ran first, Ran last, Less less )
{
  for ( Ran e = last - 1 ; e > first ; --e ) {
    Ran max = first;
    for ( Ran s = first + 1 ; s <= e ; ++s )
      if ( less( *max, *s ) )
        max = s;
    swap( e, max );
  }
}

最大値が末尾にある場合は交換処理は不要と書きましたが、サンプル・プログラムでは無条件に交換処理を行っています。これは、比較処理を毎回行うコストを考えたとき、最大値が末尾にある可能性が低ければ比較しないほうが処理量が少なくなると判断したためです。


3) 挿入ソート(Insertion Sort)

「挿入ソート(Insertion Sort)」は、配列をソート済みの部分とそうでない部分に分けて、未ソートの部分からひとつ要素を取り出してはソート済み部分の適切な(ひとつ前の要素より大きく、すぐ後ろの要素より小さくなるような)位置に挿入する操作を繰り返してソートする方法です。処理の流れとしては

  1. 配列先頭の一要素のみをソート済み、残りを未ソートと考える。
  2. 未ソートな配列の先頭要素(はじめは配列の二番目にある要素)を抜き出して、ソート済みの配列の適切な位置に挿入する。この操作で、ソート済みの配列は要素がひとつ増え、逆に未ソートの配列要素はひとつ減る。
  3. 上記の操作を、未整理な配列の要素がゼロになるまで繰り返す。

となります。抜き出した要素をソート済み配列に挿入する処理は、ソート済み配列の末尾から順に要素同士を比較して、抜き出した要素よりソート済み配列の要素の方が小さくなるまでデータをひとつずつ後ろにずらしていき、ソート済み配列の要素の方が小さくなった時点で空いた場所へ抜き出した要素を挿入することで実現できます。
要素を挿入する処理と、単純挿入法を使ったソート処理の様子を下図に示します。

要素をソート済み配列に挿入する
ソート済み|未ソート
19253147|29639133
1925312947|639133
1925293147|639133
単純挿入法によるソート処理
51|45116739812875
4551|116739812875
114551|6739812875
11455167|39812875
1139455167|812875
113945516781|2875
11283945516781|75
1128394551677581|

この方法なら、バブル・ソートよりも比較・交換作業を減少させることができるので、その分処理が早くなります。最悪の場合は逆順にソートされたデータ列をソートする場合でしょう。この時は比較・交換回数がバブル・ソートと同数になってしまいます。逆にすでにソートされたデータ列なら、一パスにつき一回の比較のみで処理が終わるので、処理はかなり高速になります。

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

/*
  InsertionSort : 挿入ソート

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

  for ( Ran e = first + 1 ; e < last ; ++e ) {
    value_type v = *e;     // 未ソート列の先頭の要素を取得
    bool inserted = false; // v が挿入されたか
    for ( Ran s = e - 1 ; s >= first ; --s ) {
      if ( less( v, *s ) ) {
        *(s + 1) = *s;
      } else {
        *(s + 1) = v;
        inserted = true;
        break;
      }
    }
    // v が未挿入の場合は先頭に要素を代入
    if ( ! inserted ) *first = v;
  }
}

4) サイクル・ソート(Cycle-Sort)

「サイクル・ソート(Cycle-Sort)」は、1990 年の "The Computer Journal" の中で「B.K.Hadoon」によって発表された新しいソート方法です。この中では「巡回置換(Cyclic Permutation)」という概念が利用されています。

未ソートのデータ列 ( 5 3 2 1 4 ) を、( 1 2 3 4 5 ) の形に並べ替えたとき、両者を見比べると、未ソート列の先頭にある 5 を末尾の 4 の位置に移動し、4 を 1 の位置に、1 を 先頭の 5 の位置に順に置き換えることでこの三つの要素は並べ替えられた状態になります。さらに 3 と 2 を入れ替えれば全ての要素が並べ替えられ、ソートは完了したことになります。最初の、三つの要素を入れ替える操作を「巡回置換(Cyclic Permutation)」といい、

ρ = ( 5 4 1 )

と表します。左から右へ、順番に要素を置き換え、末尾の要素は先頭の要素の位置に置き換える形になるのが「巡回」と名付けられている理由です。3 と 2 を入れ替える操作は

τ = ( 3 2 )

と表され、これは二つの要素を入れ替えることになるので「互換(Transposition)」といいます。

任意のデータ列に対する巡回置換や互換の組み合わせはただ一通りに決まります。これを巡回置換の積といいます。さらに、巡回置換は互換の積に分解することができます。先の例では、( 5 4 1 ) に対して ( 5 4 ), ( 4 1 ) の二つの互換に分けられます。よって、( 5 3 2 1 4 ) を ( 1 2 3 4 5 ) に並べ替える場合、

( 5 4 1 )( 3 2 ) = ( 5 4 )( 4 1 )( 3 2 )

の三つの互換で実現可能となり、要素を交換する回数は三回で済みます。これがサイクル・ソートの原理になります。

ここで問題なるのが、どのように巡回置換の積を求めるかということです。前にも述べたように、データ列を並べ替える操作は互換の積で表すことができるので、必要な互換を順次求めることができれば実現できます。そこで、以下のような処理を行います。

  1. 入れ替える要素 a[i] に対し、それより後ろ側にある要素の中でより小さいものを数え cnt に代入する。
  2. cnt = 0 ならば、a[i] は先頭要素なので処理はしない。
  3. cnt > 0 の場合、a[i + cnt] の位置にある要素と入れ替える

例えば、データ列 ( 5 3 2 1 4 ) の先頭要素 5 よりも小さい要素の数を数えるとそれは 4 になるので、5 の位置から 4 つ後ろ側にある要素 4 と交換します。これを繰り返すと

53214|5 より小さい要素は 4 つ
43215|4 番目の "4" と入れ替える
43215|4 より小さい要素は 3 つ
13245|3 番目の "1" と入れ替える
13245|1 より小さい要素はゼロなので処理完了

となります。cnt は、対象の要素が本来あるべき位置を示しています。よって、入れ替えによってその要素はすでにソートされたことになります。代わりに先頭に移動した要素に対しても同じ操作を繰り返すと、やがて全ての要素の中の最小値に到達し、それは移動させる必要がないため処理は完了となります。上記結果を見ると、( 5 4 )( 4 1 ) の操作がなされたことになり、これはちょうど先ほど求めた互換の積と一致します。先頭の要素に対して処理が完了した時点で、先頭は最小値となっているので、その次の要素にシフトしてまた同じ処理を繰り返します。すでにソートされた要素であれば互換は発生せず、次の要素にシフトしますし、そうでなければまた二番目に小さい値が見つかるまで互換が繰り返されます。先の例では、3 と 2 が入れ替わり、2 は 二番目に小さな値なのでそこで処理が完了します。その後は全てソートされた状態なので、互換は発生せずに末尾まで達します。その時点で全てのデータ列はソートされたことになります。

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

/*
  CycleSort : サイクル・ソートによるソート・ルーチン

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

    // 未ソート列の中で、ソートされたときの位置を求める
    for ( Ran r = s + 1 ; r < last ; ++r )
      if ( less( *r, *s ) )
        ++idx;

    // 先頭要素にあたる場合はソート済み列に追加
    if ( idx == s ) {
      ++s;
      continue;
    }

    // 対象の位置に等しい要素があればスキップ
    while ( ( ! less( *s, *idx ) ) && ( ! less( *idx, *s ) ) )
      ++idx;

    swap( s, idx );
  }
}

サイクル・ソートを実装する上で問題となるのが、交換する要素が互いに等しい場合の対応です。等しい要素どうしの交換が発生した場合、その時点で同じ操作を無限に繰り返すことになってしまうため、そのときは交換する位置を変えなければなりません。サンプル・プログラムでは、等しい場合は後ろ側にシフトするようにしています。この処理の中で

while ( ( ! less( *s, *idx ) ) && ( ! less( *idx, *s ) ) )

と書かれているのは、*s < *idx でなく ( つまり *s ≥ *idx ) かつ *idx < *s でない ( つまり *idx ≥ *s ) ことをチェックすることで等しいかどうかを判断するためです。*s == *idx と書けばよさそうに見えますが、対象の要素は '==' をサポートしているとは限らないためこのように処理しています。また、このループの中で末尾に達していないかをチェックする処理がありませんが、これが必要となるのは等しい要素が末尾まで並んでいる場合で、このときは idx が示す位置は必ず等しい要素の並んだ列より前側になります(極端な例では、全てが等しい場合に s == idx となります)。よって、末尾まで到達してしまう場合は想定しなくても問題はありません。


5) 動作テスト

今まで紹介したサンプル・プログラムを使ってデータ列をソートしたときの処理時間を計測した結果、以下のようになりました(単位はsec)。いずれの場合も、処理を 10 回繰り返したときの平均時間を表示しています(*5-1)。

表 5-1. サンプル・プログラムによるソートの処理時間
データサイズ100020004000800016000
ランダムなデータ列(Random)バブル・ソート0.0037460.0112250.0311250.1163180.469145
バブル・ソート(改良版)0.0031290.0092310.0314740.1182070.468694
シェーカー・ソート0.0020960.0062250.0215250.0748560.296345
奇偶転置ソート0.0016080.0067340.0216900.0825830.332066
ノーム・ソート0.0019720.0030670.0102890.0384390.156896
選択ソート0.0006490.0035920.0110750.0416100.153302
挿入ソート0.0002630.0013290.0059960.0201550.080071
サイクル・ソート0.0030010.0082910.0298070.1127020.463155
ソート済みの数列(Sort)バブル・ソート0.0009060.0023310.0103050.0274820.108015
バブル・ソート(改良版)0.0000020.0000300.0000040.0000500.000042
シェーカー・ソート0.0000040.0000060.0000120.0000190.000028
奇偶転置ソート0.0000020.0000040.0000050.0000090.000021
ノーム・ソート0.0000020.0000030.0000050.0000300.000017
選択ソート0.0005860.0044070.0115090.0398500.152584
挿入ソート0.0000030.0000040.0000070.0000130.000022
サイクル・ソート0.0016280.0037700.0119710.0405040.152706
逆ソートした数列(Reverse)バブル・ソート0.0014740.0028270.0081490.0251060.104999
バブル・ソート(改良版)0.0007720.0000230.0000600.0000490.000021
シェーカー・ソート0.0000260.0000290.0000310.0000180.000042
奇偶転置ソート0.0000240.0000210.0000160.0000450.000344
ノーム・ソート0.0000590.0000210.0000070.0000120.000034
選択ソート0.0007960.0035380.0102690.0401750.150763
挿入ソート0.0000050.0000290.0000100.0000200.000034
サイクル・ソート0.0013510.0034920.0101160.0369950.149666
全要素が0(Zero)バブル・ソート0.0016520.0029930.0134750.0471840.230353
バブル・ソート(改良版)0.0009490.0054760.0161700.0629540.245817
シェーカー・ソート0.0019740.0047180.0154700.0618500.241895
奇偶転置ソート0.0006250.0033140.0130230.0452180.169411
ノーム・ソート0.0021050.0063900.0189200.0799030.319138
選択ソート0.0005810.0029190.0100860.0389200.148484
挿入ソート0.0006180.0027720.0095540.0375360.148387
サイクル・ソート0.0016390.0046890.0174220.0676090.258106

ランダムなデータ列をソートしたときの処理時間を各ソート法で比較したグラフは次のようになります。

図 5-1. 各ソートの処理時間(ランダムなデータ列)
各ソートの処理時間比較(Random)

どの手法も、処理時間はデータ量の二乗にほぼ比例しているように見えます。実際、データ量の比率に対する処理時間の増加率を計算すると以下の表のようになり、データ量が二倍になると処理時間がほぼ 4 倍に増加していることが分かります。

表 5-2. データの増加率に対する処理時間の増加率
データの増加率2000/10004000/20008000/400016000/8000
バブル・ソート3.002.773.744.03
バブル・ソート(改良版)2.953.413.763.97
シェーカー・ソート2.973.463.483.96
奇偶転置ソート4.193.223.814.02
ノーム・ソート1.563.353.744.08
選択ソート5.533.083.763.68
挿入ソート5.054.513.363.97
サイクル・ソート2.763.603.784.11

各ソートの処理時間を比較すると、バブル・ソートとサイクル・ソートが最も遅く、次いで奇偶転置ソート、シェーカー・ソートがほぼ同程度、ノーム・ソートと選択ソートも同程度、挿入ソートが最も速いという結果になっています。


データの傾向に対する各ソートの処理時間を示したグラフを以下に示します。

図 5-2. データの傾向に対する各ソートの処理時間
バブル・ソートバブル・ソート(改良版)
バブル・ソートバブル・ソート(改良版)
シェーカー・ソート奇偶転置ソート
シェーカー・ソート奇偶転置ソート
ノーム・ソート選択ソート
ノーム・ソート選択ソート
挿入ソートサイクル・ソート
挿入ソートサイクル・ソート

選択ソートを除き、全要素がゼロ、またソート済みのデータ列については通常より処理時間が短くなっています。特に、改良版バブル・ソートとシェーカー・ソート、奇偶転置ソート、ノーム・ソート、挿入ソートはほとんど処理時間がゼロに近い値となっています。これらはソートされていることが判明したらすぐに処理を完了するようになっているため、比較処理が一回のパスだけで済む上に交換処理が発生せず、非常に早く処理することができます。
逆順ソートは最も比較・交換処理が多くなり、従って最も処理時間が長くなるはずですが、ノーム・ソートと挿入ソートだけが予想通りの結果になっています。シェーカー・ソートと選択ソートはランダムなデータ列と同程度、バブルソートと奇偶転置ソート、サイクル・ソートは逆ソート列がランダムなデータ列の半分程度の処理時間となっており、原因まではわかりませんでした。
選択ソートはその処理の仕組みから、いかなるデータ列に対しても処理時間がほとんど変わりません。これは、どのような場合でも比較回数は変化しないためです。また、交換回数はデータ数を超えることがなく、よって最大でもデータ数に比例するため、処理時間は比較処理の時間に依存することになります。


交換処理にコストがかかるよう、vector を要素とするデータ列を作成して処理すると次のような結果が得られました。いずれも、要素数 100 のランダムな数値からなる vector を 1000 個持った配列に対して処理を行っています。また、比較処理が短くなるように、各要素(vector)の先頭の要素だけで大小判定をしています。

表 5-3. 交換処理にコストがかかる場合の各ソートの処理時間
ソート方法処理時間
バブル・ソート0.057340
バブル・ソート改良版0.054129
シェーカー・ソート0.054399
奇偶転置ソート0.055042
ノーム・ソート0.051860
選択ソート0.003710
挿入ソート0.014266
サイクル・ソート0.005848

ここでは、選択ソートとサイクル・ソートの処理時間が他と比較して非常に短いという結果が得られています。サイクル・ソートは比較的新しい手法なのにもかかわらず最初のテストではバブル・ソートと大差ない結果になっていましたが、このソート法は要素の交換回数が非常に少なくなるという利点を持っているため交換処理にコストがかかるような場合には非常に有効な手法になります。また、先にも述べたように、選択ソートの処理時間のほとんどは比較処理に依存するので、交換処理に時間がかかるような場合は選択ソートも有効な手法であることになります。

逆に、比較処理にコストがかかるような場合を想定して、数値そのものではなくその約数の数を比較させたときのソートの処理時間は次のようになりました。要素の数値範囲は 0 から 99 まで、データ列の要素数は 1000 としています。

表 5-4. 比較処理にコストがかかる場合の各ソートの処理時間
ソート方法処理時間
バブル・ソート0.100623
バブル・ソート改良版0.096855
シェーカー・ソート0.066899
奇偶転置ソート0.104951
ノーム・ソート0.088157
選択ソート0.101191
挿入ソート0.041339
サイクル・ソート0.242117

比較処理に使った関数は次のようなものになります。

// 処理時間の長い比較関数オブジェクト(約数の個数を比較する)
struct slow_less : public std::binary_function<unsigned int,unsigned int,bool>
{
  bool operator()( const unsigned int& i1, const unsigned int& i2 ) const
  {
    unsigned int c1 = 0, c2 = 0;

    for ( unsigned int i = 2 ; i <= i1 / 2 ; ++i )
      if ( i1 % i == 0 ) ++c1;
    for ( unsigned int i = 2 ; i <= i2 / 2 ; ++i )
      if ( i2 % i == 0 ) ++c2;

    return( c1 < c2 );
  }
};

サイクル・ソートは、順位を求めるために比較処理を数多く行います。そのため、比較処理に時間がかかるような場合はかなり不利です。このようにサイクル・ソートは非常に癖のある性質を持ったソート法で、利用する場面もかなり限られたところになります。

総合的に見て、今回紹介したソート法の中では挿入ソートが非常に安定した性能を持っていることがわかります。しかし、それでも処理時間がデータ数の二乗に比例するという性質は変わりません。よってデータ数が増えれば処理時間は急激に上昇していきます。次回はこの上昇カーブがずっと緩やかなソートアルゴリズムを紹介していきたいと思います。


* 5-1) テスト環境はかなり特殊で、Windows7 にある VirtualBox 上の Linux でテストしています。CPU は Intel Core i5 2.67GHz で 4 コアですが、ゲスト OS の Linux 上では 1 コアとして動作しています。従って、処理時間は参考程度と考えてください。環境によって全く異なる結果になるでしょう。しかし、データ量に伴い時間が二乗に比例して長くなるのは基本的には変わらないと思います。


<参考文献>
  1. 「X68000マシン語プログラミング <入門編>」 村田敏幸 著 (ソフトバンク)
  2. Newsletter (issue 599, 2 October 2000)
  3. "Cycle-Sort: A Linear Sorting Method", The Computer Journal (1990) 33 (4): 365-367.
  4. Cyclesort - a curious little sorting algorithm
  5. Wikipedia

[Go Back]前に戻る [Back to HOME]タイトルに戻る
inserted by FC2 system