Pythonでアルゴリズム「クイック・ソート」(8)：再帰処理、左グループと右グループどっちが先なの？

こんにちは！今回も「クイックソート」の続きです。そして、その「クイックソート」のコードの核である。「再帰処理」についてお話しさせてください！

「再帰関数」とは？

前回の記事までで、次の図のとおり、外側ループ1回目を完了させました。

値「６」の位置は確定し、その左側に「６」より小さい値、その右側には「６」より大きい値が存在しています。しかし、並べ替えは完了していませんね…。

ここは、何度かループさせて、リスト全体の要素を並べなくては…と思いますね。これ以降For文もWhile文もございません。次のような見慣れないIf文が２つ現れます。

「あれ、If文の処理部で、この関数自身を呼び出しています。🤔」

いいところに目を付けましたね！（打ち合わせ通りの発言ありがとうございます🧡）。まさに、ここのコードが、まさに再帰させる、すなわち、「再び帰らせる」命令をしているんです。自分自身を関数中で呼び出す関数のことを、「再帰関数」といいます。

「Left-1」は、確定した値の左隣り

それでは、具体的に、再帰を行うコードを見てみましょう！😆

まず、ループが終わったところでの、leftとrightの位置を確認しておきます。次の通りです。

「ああ、すれ違っちゃったんですね。🤔」

はい。leftとrightの位置関係が逆転している状態でループが止まってしまいました。そして、今回取り組むのは次のコードです。

再掲

「うーん、leftの左側とrightの右側、それぞれの位置が登場しますね。😮」

そうです！これがそれぞれどこを指しているか、を示すと次のとおりです。

ここでは、まず「left-1」が現れる一つ目のif文の条件式に着目しましょう！

左側の要素グループが先に整列対象になる

次の図の赤枠で囲まれているifの条件式ですが、これは一体何を言っているんでしょうね。

「left-1が示す位置が、ループの開始位置よりも大きいという条件を示しているようです。🤔」

ということは、startNumは「0」、left-1は「４」でしたから、再帰させる処理部は実行されますね。何が実行されますか？

「開始位置は「０」のまま、終了位置は「left-1」にして、再び関数が最初から実行されます。」

はい！では、それを絵にすることこうなります！

「おお、確定した『６』の左側のグループが今度は処理対象となるのですか！😄」

そうなんです！まずは、リスト全体を大きなグループとして処理しました。続いて、確定した値の「左側」にある値すべてを一つのグループとして処理するんです。

ということで、再帰処理のご紹介でした。次回（まは次々回で）完了させましょう。

では、ビーダゼーン！

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