Pythonでアルゴリズム「クイック・ソート」(6)：右と左が衝突、もとい、すれ違う？

はい、今回もクイックソートの続きでございます！前回の記事では、ピボットの右と左にある値を交換するコードを確認しましたね。下の赤枠部分が行う処理です。

再掲

今度は、その下の続きに取り組みますよ～。While True内の最後の処理です。今回も図解しますよ！よし、行ってみよ～😄。

左と右が接近する！？

下図は、data[left]とdata[right]の交換が終わったところです。さて、上の赤枠の処理を行うとどうなるでしょうか？

「コード自体は簡単だな。leftが1つ増えて、rightが一つ減る🤔」

ですねえ。だとすると、Whileループの最後の処理後はこうなりますね。

「おお！leftとrightが近づいた！😆」

はい！この状態でWhile Trueのループをもう1回転させると次の通りです。３と７が交換されました。

そして、赤枠の処理をすると次の通りとなります。さらに、leftとrightが接近してきましたよ～！

leftが１つスキップ

「ちょっと待って。2番の値「４」はピボットより小さいな。🤔」

いいことに気が付きました！となると、次のループの左側の交換対象は、「４」ではなく、右隣りの「８」ですね。結果、「８」と「１」が交換されます。

そして、またleftが1つ増え、rightが1つ減るとこうなります。

「おお、隣り合った！😄」

ピボットが動いた！？

次のループでは、ピボットとLeftが持つ値がイコールなので、Leftは変更せず確定します。Rightもピボットより小さいので、そのまま確定です。となればleft「６」とright「５」の両者が交換されます。

あらよっと。こうなります。

「うお、ピボットの位置が変わった😮」

そう、ピボットも交換対象なんですよ。ピボットは、位置を表すのではなく、「値」を表していますからね。

これで、ピボットだった「６」の位置は確定しました。「６」は、もう移動しません。「６」の左には「６」より小さい値しかなく、「６」より右には「６」より大きい値しかないのですから。

「『６』にとっては、『６』自身以外の並びがどうなるか、なんてもう知ったことじゃないと？🤔」

そうですね～。イチあがり～といったところですね。

左と右がすれ違う！？

あ、ところで、その後処理が残っていましたね。

「ああ、左を増やして、右を増やすやつですね。」

はい、実行するとこうなります。

「ああ！leftとrightがすれ違った～😭」

そうなんです。もう新しいピボットを作らないことには、困ったことになりますね…。ループは、ループは果たして止まるのでしょうか？

それについては、次回ご紹介しましょう！

では、ビーダゼーン！

※私のやる気アップとブログの品質向上につながりますので、記事が気に入られた方は、「ポチっ」と好きボタンを押してくださったり、フォローいただけますと、私が喜びます！🙇。