現状最速のソートアルゴリズム「クイックソート」とは?

  • 2016/08/09 14:43:02
目次
  • 1:クイックソートのアルゴリズム
  • 2:クイックソートの利点と欠点

クイックソートは交換ソートの一種ですが、現状最速のソートアルゴリズムだと言われています。

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

クイックソートは分割統治法をいう考え方を用いたアルゴリズムです。分割統治法をとは問題を解決したい対象をいくつかのグループに分け、そのグループの中で解決を図り、最終的に全体の問題の解決を図る方法です。

大きい数字だとなかなか暗算できませんが、小さい数字に分けて考えると容易に計算出来たりしますよね。このように対象を小さく(分割)すれば問題が単純になったり、簡単に解決できたりすることが往々にあります。

今回の例では以下の数値の配列をソートしたいものとします。

qs1

クイックソートではこの値より大きい、この値より小さいと言った風に、大小を大まかに分けていくことを繰り返して、ソートを行います。

そのため先ず基準となる値が必要になります。この基準値のことをピボットと呼びます。

ピボットを選ぶ基準はランダムや、配列の先頭といった風でもいいのですが、計算効率を考えると、できるだけ配列の中での中央値を選ぶのが良いとされています。

今回は基本的な「配列の先頭」をピボットにする方法で行ってみます。つまり13がピボットになります。
13より小さい値を13の直前へ、13より大きい値を配列の後ろに移動させます。

すると以下のようになりました。

qs2

この時点で13の配列上に位置は確定しますので、ソート対象からははずしてOKです。

今度は13より小さかった値グループと大きかった値グループそれぞれでピボットと決めて同じことを行います。

先ず13より小さかった値グループからですが、このグループの先頭が8なので、ピボットを8とします。

先ほどと同じように8より小さい・大きいで振り分けていきます。

すると以下のようになりました。

qs3

これで8の位置は確定しましたにでソート対象から外します。今度は

1 2 4 7と11 12のグループに分かれますが、見ての通りすでにソートが完了しているので、これらの値も位置が確定しました。

よって1 2 4 7 8 11 12はソート済みになりました。

では13をピボットにして大きかった値グループの処理を行います。

qs4

でしたね。

先頭の89をピボットにします。

しかし見ての通り、89はこの配列の中でも2番めに大きい値です。もし89を使うと分割がかなり偏ることがわかるかと思います。

先ほど説明したとおりできるだけ中央値をピボットにすると分割が偏らずに計算効率が上がります。

そこで、この配列の中央値は46.5なので、48をピボットにしてみます。このようにピボットの考え方を切り替えるのは有効ですが、実際にプログラミングするときに複雑になる可能性もあります。

今回は例を示すために配列先頭と中央値を持ちだしましたが、実装時には中央値だけをつかっても問題ないと思います。

qs5

この時点で48の位置が確定しましたので、ソートの対象から外します。

現状の状態を一度確認しておきましょう。今以下の値に関しては位置が確定しています。

qs6

さてまたグループが分かれました。先に48より小さかった値グループを処理してみます。

qs7

ですね。

ここも先ほど同じで、20はこの配列の中で2番めに小さい値です。そのため先ほどと同じように分割が偏ってしまいますので、やはり中央値を使います。

この配列の中央値は26なので、一番近い29をピボットにしてみます。

qs8

これで29の位置が確定しましたので、ソート対象から外します。現状では以下のようにソートが進行しています。

qs10-1

さて残りの値を処理します。まず20 23 16ですが、ここまで要素が少なくなった場合、単純挿入法のほうが処理が早い場合が多いです。実際のクイックソートでも要素数が十分小さくなった場合途中で基本挿入法に切り替えてソートする場合もあります。

そこでここでは基本挿入法でソートしてしまいましょう。

qs9

これで16 20 23 33 45の位置も確定しました。配列の2/3はソートが済みましたね。

qs10

さて最後は48より大きかった値グループが残っています。最後なので正直にピボットを決めてソートしてみます。

この配列では71が中央値になりますので71をピボットにします。

qs11

運良く全部ソートが完了しました。これで56 66 71 89 94 の位置が確定しましたので、配列全体のソートが完了しました。

qs12

このように少ない比較交換でソートが完了することがわかるかと思います。

クイックソートの利点と欠点

クイックソートの利点はなんと言っても速度です。現状のソートアルゴリズムの中では最速とされています。またアルゴリズムもそれほど複雑ではなく理解しやすいのも特徴かと思います。

しかし、厳密にはピボットのとり方等の方法で計算効率が悪くなる可能性もあるアルゴリズムと言われています。高速なソートを行うには実装時にいろいろな工夫が必要になってくるアルゴリズムとも言えます。

このソートアルゴリズムは安定ソートではありません。