小さい順に並べ替え: クイックソート

選択ソートよりも「速い」並べ替えのアルゴリズムをひとつ紹介しましょう.

このアルゴリズムは「クイックソート」 というもので,そのおおまかな手順は

      データを小さいグループと大きいグループに2分し,
      小さいグループを左側に,大きいグループを右側に置く.
      この操作をできた2つのグループそれぞれに適用する.
      以下この操作をできる小グループにどんどん適用する
      ...
というものです.

選択ソートと比べてどのくらい速いか,手っ取り早く見てみたい人は 選択ソートとクイックソートの比較   を見てください.

例えば,次のような棒を短い順に並べ替えることを考えます.

まず,任意の棒を1本選びます.例えば,以下の白の矢印の棒を選んだとします. そして,棒全体を,選んだ棒以下の長さを持ったもの(赤色で示してあります) それより長いもの(緑) の2つに分け,

短いグループを左側に,長いグループを 右側に移動させます.

これで,短いグループ長いグループ2つのグループができました. こんどは,この2つのグループそれぞれに,同じことを繰り返します.つまり,それぞれの グループからひとつずつ任意に棒を選び(白い矢印)

それぞれのグループを短いものと長いものの2つのグループに分けます.これで, 合計4つのグループができたことになります.

今,ピンクのグループ以外は,ちゃんと小さい順に 並んでいるので,これらはもう移動する必要はありません.

そこで,ピンクのグループだけに同じ分割を繰り返します. そのグループ内から任意の棒を選び(白矢印),

そのグループを短いものと長いものの2つのグループに分けます.

これで,短い順に並べ替えられました.

このような手順による並べ替えを「クイックソート」 といいます.選択ソートよりもずいぶん面倒な感じですね?

実は,このアルゴリズムは名前に「クイック」とついていることからもわかるように, 選択ソートに比べてかなり高速な並べ替えのアルゴリズムになっています. それを実際に比較実験してみましょう.

選択ソートとクイックソートの比較   最初のページに戻る