pythonクイックソートの比較回数と交換回数について

Question

前提・実現したいこと

pythonのクイックソートの関数を定義し、思うように動作できたのですが、比較回数と交換回数をカウントしようとあれこれやっているのですが、うまく動作せず試行錯誤しています。

発生している問題・エラーメッセージ

comp は比較回数、sort は交換回数として、実行すると以下のように途中から数字が乱れていきます。

-追記-
比較回数が正しいカウント数にならないです。
どこにインクリメント式を挿入していればいいのでしょうか？
クイックソートにおける比較箇所がいまいちわかりません。

comp = 1
comp = 2
comp = 3
comp = 4
comp = 5
comp = 6
comp = 7
sort = 1
comp = 8
comp = 9
comp = 10
comp = 11
comp = 12
sort = 2
sort = 3
comp = 13
comp = 14
comp = 15
sort = 4
comp = 16
sort = 5
sort = 6
sort = 5
sort = 2

該当のソースコード

カウントする処理を入れる前のクイックソートのソース

def quick_sort(arry):

    n = len(arry)
    if n <= 1:
        return arry

    center = arry[0]
    right=[]
    left=[]

    for i in range(1,n):
        if arry[i][2] >= center[2]:
            left.append(arry[i])
        else:
            right.append(arry[i])

    r = quick_sort(right)
    l = quick_sort(left)

    return l+[center]+r

カウント処理を加えてみたソース

def quick_sort(self, data, comp_count, sort_count):

    n = len(data)
    if n <= 1:
        return data

    center = data[0]
    right=[]
    left=[]

    for i in range(1,n):
        if data[i][2] >= center[2]:
            left.append(data[i])
        else:
            right.append(data[i])
        comp_count += 1
        print("comp = %s" %comp_count)

    sort_count += 1
    print("sort = %s" %sort_count)
    r = quick_sort(self, right, comp_count, sort_count)
    sort_count += 1
    print("sort = %s" %sort_count)
    l = quick_sort(self, left, comp_count, sort_count)

    self.comp_count = comp_count
    self.sort_count = sort_count

    return l+[center]+r

試したこと

再帰する際におかしくなっていると推測できたので、カウントの位置を変えたり引数を考えてみたりしましたが、これといった解決法が思いつきません。
カウントする際の変数は、データ構造？を使ってますが特にこだわりはありません。

補足情報（FW/ツールのバージョンなど）

python3.8.2のOS X Mojaveです。

Answer 1

sortが乱れている原因はこちら：

    sort_count += 1
    print("sort = %s" %sort_count)
    r = quick_sort(self, right, comp_count, sort_count)
    sort_count += 1
    print("sort = %s" %sort_count)

quick_sortの中でsort_countに足していたが、外のsort_countに反映されてません。グローバル変数を使うか、sort_countを戻り値に加えるか、どちらも解決できます。

クイックソートの比較回数はcenterの値によって、ベストケースO(nlogn)からワーストケースO(n^2)まで変動するので、計算する時にご注意ください。

Comments

[WindowppleMacin]

詳細な素早い回答ありがとうございます！！変動するのですか。知らなかったです。比較回数のインクリメントを挿入する位置はあっていますでしょうか？

[YufanLou]

変動するといっても、同じ入力は同じ比較回数です。ただ必ず n*log(n) 回ではありません。比較回数のインクリメント位置は合っていますが、sort_countと同じく、左右分岐の回数を集計していません。

[WindowppleMacin]

左右に分岐した箇所、
if data[i][2] >= center[2]:
left.append(data[i])
else:
right.append(data[i])
のifとelseの中にもカウントを入れるという事でしょうか？

[YufanLou]

はっきりではなかった、ごめんなさい。そこではありません。左右分岐というのは
r = quick_sort(self, right, comp_count, sort_count)
l = quick_sort(self, left, comp_count, sort_count)
です。
r, comp_count, sort_count = quick_sort(self, right, comp_count, sort_count)
l, comp_count, sort_count = quick_sort(self, left, comp_count, sort_count)
にして、そして最後に
return l+[center]+r, comp_count, sort_count
にすれば、グローバル変数を使わなくても大丈夫です。

Answer 2

これといった解決法が思いつきません。

グローバル変数に記録してみてはどうでしょうか。

Comments

[WindowppleMacin]

ありがとうございます！
数字がおかしくなることは無くなりました。
しかし、比較回数が正しいカウント数にならないです。
どこにインクリメント式を挿入していればいいのでしょうか？
クイックソートにおける比較箇所がいまいちわかりません。