Pythonでアルゴリズム「クイック・ソート」(10)：関数がこれで完結！

こんにちは！Pythonで「クイックソート」シリーズも今回で10回目、そして最終回でございます～。

前回記事では、再帰を行うことによって、最初のビボットの位置から左側の値が整列するところまで確認しました！

左側が整列した様子

そして、今回は、クイックソートの関数の最後のコードに取り組みますよ～😆。

ピボット右側の値を整列！

今回、分析する対処のコードは、次の赤枠内です。

「一つ上のif文と似ていますね🤔」

やろうとしていることは、ほぼ同じです。というか、ご想像のとおり、最初のピボットであった「６」の右側の値を並べるのがミッションです！

条件式で再帰をコントロール

まずif文の条件式に現れる２つの値、rightとendNumがどの位置を示しているか確認しましょう。次の図のとおりです。

rightは、（5番目の指していた）leftとすれ違ってしまったのでしたね。では、もう一度、次の赤枠の条件文をよく見てみます。

『「right + １」の値が、endNumより小さいなら』と言っています。「right + １」は、次の図のとおりですね。

この条件式は、「整列が進行してrightの値が増えていくところ、整列する対象の値が存在するのなら」と言っています。

「整列する対象の値が存在する限り、再帰が行われる？🤔」

はい！ビボットだった「６」より左側の値を整列させたときと同じですね～。

新たにピボットを設置して整列

では、if文の処理部を見てみましょう。下の赤枠の箇所です。

「right +1」を開始値に、endNumを終了値にして、再び関数の最初から処理が走ります。とすると、またビボットが作られますね！次の通りです。では、この状態から並べ替えましょう。

ピボットより小さい値「７」を右側に見つけたので、交換が起こります。

すると次の通りとなります。

「あ、すべて昇順に並びましたね！😆」

そうです。が、最後までやり切りますか。コードを走らせるコンピュータとしては、これで整列は終わっていませんから。

さらに、再帰した後、ピボットは、「８」になりますね。もう並んでいますから、なんの入れ替えもおきません。

もう1回再帰します。「right+1」は、1つ増えるものの、再帰したところで並べ替えはおきません。

「この次は？🤔」

「right +1」と「endNum」の値が一致し、ifの条件文を満たさくなりますから、これで再帰は止まります。並べ替え完成です！

「長かった…。けれども、終わりました😭」

はい、これで関数の定義が終わりました。残りのコードでは、整列対象のリストを準備し、関数を呼びだします。これは、特に説明は不要ですね。なお、関数の開始値として「０」、終了値として「リスト最後の要素の番号」をセットします。

終わりです！よかった。本当によかったです。説明している本人が、クイックソートを説明できるか不安でしたから…。まあ、説明不足な箇所や、説明が適切でない箇所があろうかと思いますが、どうぞ多めに見ていただきたくよろしくお願い致します！

ここまで読んでくださり、ありがとうございました！次回は、、、何をやろうかな。「マージソート」かな。検討いたします。

あ、一応コード全体を再掲しますね。

def qSort(startNum, endNum):
    pivot = data[(startNum + endNum) // 2]
    left = startNum
    right = endNum
    
    while True:
        while data[left] < pivot:
            left += 1
        while pivot < data[right]:
            right -= 1
        if left >= right:
            break
        
        tmp = data[left]
        data[left] = data[right]
        data[right] = tmp
        
        left += 1
        right -= 1
        
    if startNum < left-1:
        qSort(startNum, left-1)
    if right + 1 < endNum:
        qSort(right+1, endNum)

data = [9, 7, 4, 8, 6, 5, 1, 3, 2]

qSort(0, len(data)-1)

print(data)     

では、ビーダゼーン！

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