Pythonでアルゴリズム「クイック・ソート」(7)：待ち続けて最後に実行！ループを抜け出せ

本日も「クイックソート」です。前回の記事では、ピボットに左右の値がだんだん近づいてきた、結果、LeftとRightの値がすれ違ってしまうところまで紹介しました。

LeftとRightがすれ違った…

コードでいうと下の赤枠のところです。leftを1つ増やす、rightを一つ減らすを繰り返したらすれ違ってしまったのです。

このまま外側のwhileループを継続するわけにはいきませんね。でも、そのWhileループの条件式は？

「Trueでした…。無限ループしろって意味ですよね…。このままじゃループが止まりません😭」

でも、ループを止める仕組みがどこかにあるはずです。

「ああ、スキップした、あのIf文か！😮」

そうです！今回は、そのIf文に焦点をあててお話ししますよ～。

内側ループは、もはや実行されない

でも、一応、While True内部の先頭から見えてみましょう。

leftの値が「５」、rightの値が「４」の状態で再び、While true内部に突入したと思ってください。

内側の２つのwhileループの条件式は、真になりそうですか？

「うーん。Leftの位置は、ビボットの位置と同じだから『偽』ですね。それで、Rightの箱の値は、５ですから、これもやっぱり『偽』です🤔」

素晴らしい！もう内側の２つのWhileループは処理が実行されないことが分かりました。

となれば、次のIf文に突入することになります。

Breakでループを抜け出せ

さあ、If文です。条件式はなんと言っています？

「leftの値が、rightの値よりも大きい、または、等しいです。😆」

ついに来ました。このif文の条件式は、外側のループが何回転もしている間、ずっと「偽」と判定されてきました。rightの方がleftより大きかったのですから。

しかし！ついに、leftとrightの値の大きさに逆転が生じて、条件式が「真」と判定されるときが来たのです！

「ずっと無視されてきたけど、ここで役立つときが来たってかんじですか。😅」

ですね。そして実行することはただ一つ、Break、すなわち、ループの脱出です。ということで、LeftとRightの値の関係が、おかしくなってしまったところでループは、終了しました～。

これで、While true内の処理はおしまいです。峠を越えました。次回以降は、いよいよ「再帰処理」に入ります。お楽しみに～。

では、ビーダゼーン！

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