Pythonでアルゴリズム「クイック・ソート」(9)：再帰処理、左側の並びが先に決定！

はい、こんにちは。「クイックソート」の続きをやりましょう。前回記事では、外側のWhileループに続く、最初のIf文について解説しました。再帰処理を行うIf文です。

ピボットだった値の左側にある値のグループで、新たにピボットを作り、並べ替えを行うんでしたね。

今回は、前回の説明が中途半端に終わってしまったので、その続きをやりますよ～。

左側のグループの並びが先に確定

前回記事で、新たなピボットが、元ピボットで確定した値の左側に作られる話をしました。この後、いったい何が起こるのか見てまいります。

再帰した後の初期状態は、次の図のとおりです。

ピボット「４」の位置が確定しました。さらに再帰は続きます。ピボットは「３」になります。

「３」の位置が確定しました。

さらに×２、再帰して、左側最後の並び替えを行います。

はい、最初のピボットだった「６」より左側の並びが、右に先んじて完成しました～！😉

「もう再帰しないのですか🤔」

そうですね。left-1が「０」を下回ってしまうので、If文の条件式を満たさなくなってしまいます。つまり、左側にはもう並べ替える値が無くなってしまった、ということですね。

後は「６」の右側の並べ替えですね。が、それは次回に回しましょう。

では、ビーダゼーン！

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