Pythonでアルゴリズム「クイック・ソート」(3)：ピボットより大きい値を探しまくる！？

前回記事では、関数定義のうち、ループ処理の下準備のコードを確認しましたね。

今回は、赤枠内のWhileループに取り組むことにしましょう。

「Whileが３つもある…😑。」

もう見た目がおっかないですね…。でも、何とか解きほぐしていきましょう。いきますよ～。

「while True」で無限ループ？

では、最初のWhile文に注目しましょう。while文は、whileの次に記述する条件式を満たす限りループするのでしたね。この場合、条件って何でしょう。

「Trueとしか書いてない。これって条件か？🤔」

ご指摘のとおり、条件になっていないですよね。ずーと、真になってしまうので、無限にループさせることになります。

「ダメじゃん😭」

だめです、、と応じたくなるところです。どうしましょうね？実は、ループを止める条件がWhile文の処理内容の方に記述してあれば、その条件を満たした時点でループは止まります。

「そんな処理あったかな、、、あった！breakが！😄」

ありましたね！Breakは、ループを抜け出す処理のことでした。このBreakがあるから、無限ループしてコンピュータがうなり声をあげる（すでに何回か経験済み）こともないんですね～😄。ということで、このBreakが処理されるまでは、While文内の処理は継続します。

まずは、最初のwhileはOKですね。

ピボットより大きい値を探せ！

では、その外側のループ内の処理に突入します。すぐに別のwhile文が始まりますね～。

「やな感じ～😑」

まあ、そうおっしゃらず…。このwhile文が何を言っているのかよく見てみましょう。

まず、leftの初期値は、グループ内の一番左側の位置でした。ならば、data[left]は、次の値を指していますね。

このdata[left]とpivotの値を比較します。data[left]の値がpivotより小さいなら、leftを一つ増やします。すなわち、data[left]は、元のleftの位置の右隣りの値を指し示すようになります。

ということは、ピボットより大きい値が見つかるまで、左端から右方向へ探しまくるわけですね～。

「ピボットより大きい値は、ないのか～と😅」

ですです。が、最初のループでdata[left]の値が「9」なので、data[left]は、pivotより大きい、すなわち、ループの条件式を満たしません。したがって、leftは上書きされません。leftの値は確定しました。このLeftの位置の値「９」が、あとでピボット右側にある値との交換の対象になるのです。

おっとここで時間切れです。続きは次回。次のwhileループを見てみましょうね。

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) 

では、ビーダゼーン！

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