クイックソート

アントニー・ホーア が発見したアルゴリズム。 ソートとは並べ替えること。クイックソートの基本は比べて入れ替えるだけ。9 つのビリヤードの玉をクイックソートで並べる場合を考えてみよう。
sort
単にクイックソートといってもルールが違うと,動きが少し変わってくる。今回は次のルールで説明する
ルール 1
基準値は中央のボールを選ぶ。グループに含まれるボールの数が偶数のときは,中央の 2 個のうち右側を選ぶ

ルール 2
基準のボールより左側のボールから,番号が基準値より大きいボールを探して一番右側に移動する。ボールを探すときは,左から順番に探して行く

STEP1を見て欲しい,1 番左に『6』 があるがこれは基準値である『3』より大きいので一番外側である『8』の右に移動させる。次に『5』は基準値である『3』より大きいので,一番外側である『6』の右に移動させる。

ルール 3
基準のボールより右側のボールから,番号が基準値より小さいボールを探して,一番左に移動する。ボールを探すときは,右から順番に探していく。

ルール 4
並び替えが完了したら基準値でグループを分割する。基準とするボールは右側のグループに含める

ルール 5
グループが1個のボールになるまで,並び替え,分割を繰り返す

基準となる青いボールのことを ピボット という。

quicksort

  • このエントリーをはてなブックマークに追加

コメントをどうぞ

メールアドレスが公開されることはありません。