Pythonでアルゴリズム「クイック・ソート」(2)：引数は２つでよかったの？

では、いよいよクイックソートのコードに取り組んでみましょう！前回の記事で、クイックソートのイメージはつかめました。丁寧に見ていけば今回もきっと分かるはず（と自分にも言い聞かせる😅）。

コードの全体像は、これだ！

まずは、コードの全体像をつかむことにしましょう。次の通りです。

「長いな～😭」

ですよね。でもでも、いつもの合言葉、「困難は分割せよ」により何とかしようじゃありませんか！全体を眺めてみると、課題の大半は、「qSort」という関数の定義にあることが分かります。

この関数の定義より下は、それを実行しているだけです。関数の定義の中に、各種制御文がありますが、一つ一つほぐしていきましょう😆。

関数の引数は２つでいいの？

では、関数の定義の出だしの部分、本日はここに全力で集中しますよ～。ループ処理が始まる前の下準備の箇所です。下の赤枠の部分です。まず、1行目については、何が分かりますか？

「うーん、関数『qSort』は、引数が２つありますね。引数の名前からして、『最初の数』『最後の数』っぽいですな🤔」

すばらしい。滑り出し順調でございます～。これらの引数２個を入れることで関数が実行されるのです。

「でも、リストは引数にしなくていいの？🤔」

おっしゃるとおり、リストを引数に加えてもいいです。が、今回は特定のリストを関数内で参照することにしました。その特定のリストは、関数の定義の次に記載されています。dataというリストです。

このリストdataがqSort関数に「参照渡し」されます。すなわち、このリストは、関数を実行することによって、要素などが更新されます。そう、リストは、「ミュータブル（変更可能）」なデータ型でしたね。

ということで、qSort関数の引数としては、startNumとendNumの２つを設定すればOKです！

ピボットをどう決めるのか？

次は、ピボットをどう決めるかを定義します。下の赤枠内がそれですね。

まず、ピボットを基準にソートするグループの「最初の番号」と「最後の番号」を入れて2で割ったときの商を求めます。この計算をすると、「グループの真ん中の番号」が得られますね（要素数が奇数なら左寄りの真ん中の値）。この番号に収まっている値がピボットになります。

次の通り、一番最初のピボットの番号は４、値は６になりますね。

グループの端の値を変数として準備

続いて、ピボットを基準に並べ替えられるグループの「左端」と「右端」の値を保持する変数「left」「right」を、qSort関数の引数で初期化します。

「となると、今回与える引数は何ですかね？🤔」

もっともな疑問です。それでは、関数を呼び出して実行するコードを確認しますか。関数の定義より下の方にあります。

「開始値の方は０で、終了値の方はなんだ？😑」

終了値は、リストDataの要素数から１を引いたもの、つまり、一番最後の要素の番号ですね。

絵で表すと次の通りです。

つまり、変数leftは「０」で、変数rightは、「８」で初期化されることにます。

これでループ処理が始まる前の準備作業のコードは終わりです。

次回以降は、ループ処理のコードを見ていきましょう！

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) 

では、ビーダゼーン！

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