Pythonでアルゴリズム「クイック・ソート」(4)：今度は左方向！小さい値を探しまくる！！

はい！こんにちは。クイックソートの続きですよ～😄。前回の記事では、グループ中の値のうち、ピボットの左側にあるものについて、左端からピボットより大きい値を探していきましたね！

さあ、次にやることは予想がついていますか！？

「えー、分かんない（棒読み）😑」

そ、そうですか💦（素晴らしい反応です。打ち合わせ通りですね💛）。実は、同様のことをピボットの右側でもやるのですよ～。ということで、本日は、下図の赤枠内3つ目のwhile（内側ループの2つ目）に取り組みますよ～😆。

恐れるに足らず！やっていることは「左側」と同じ

ということで、下の赤枠のWhileループですね。これを解きほぐします～。

「なんか、上のWhile文と似てますね…。🤔」

そうですよ。上のWhile文と処理することは、ほぼ同じです。

まず、ピボットの値と「right」の位置にある値の大きさを比較していますね。rightの初期値は、リストの右端です。図示すると、次の通りです。

はい、どっちが大きいですか？

「Data[right]の方がピボットより小さいですね。とすると、こいつは左側に移動せず、ピボットの右側に留まるのですね！😆」

いや、違うんですん。ピボットより左側にある値の場合は、ピボットより大きい値を探すのでした。しかし、今回、ピボットより右側にある値の場合は、その反対となります。ようは、ピボットより小さい値を探すのです。

ということで、最初から左側に移動するべき値を見つけちゃった！、ということになります。

右から左へピボットより「小さい値」を探すのだ！

今、data[right]の方がピボットより小さいので、While文の条件式の答えは、「偽」となり、While文内の処理は実行されません。結果として、rightの値は、上書きされずに確定しました。

でも、もしdata[right]の方がピボットより大きかった場合は、どんな処理をするのでしょうか？

（再掲）

「うーん、rightの値が一つ増える、、、じゃない、一つ減るんですね🤔」

そうそう。rightは要素の位置を表す変数ですから、一つ左の位置を指し示すようになります。再びループ開始に戻り、その位置の値がやはりピボットより大きかったら、さらにrightは一つ左の位置を指し示すようになります。その繰り返しです。

「右から左へ、『ピボットより小さい値はどこじゃ～』と順番に探すのですか！？😄」

そうなります。ですから、このWhile文と一つ上のWhile文はペアになっているんですね～。この２つのループを通過することにより、交換の対象となる値を保持している位置、すなわち、「left」と「right」の値が確定します。

図示すると、次の通りです。

はい、本日は以上です！一日に40分くらいしか、このブログ執筆に時間を割けないんです。ゆっくりペースですが、許してください～（「クイック」ソートの解説が「クイック」でないよ～という、『ちょっといま、ぼく、旨いこと言っちゃいました！？』的なクレームは受け付けておりません🧡）。

次回は、これに続く「謎のif文」を紐解く、、つもりだったのですが、話の流れからして、if文をスキップして次に進みます。if文が真だったときの処理内容が「Break」（ループ停止）ですから、これはいったん保留して、ループが停止しないときの話をしたいのです。

では、ビーダゼーン！

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