クイックソートの再帰呼び出し回数について

Question

python3.xを用いてクイックソートの再起呼び出しの回数を調べる以下のコードを作りました。(リストの長さは10)

def simple_qsort(lst):
    global n
    n +=1
    if len(lst) <=1:
        return lst
    pivot =lst[0]
    lst1 =[x for x in lst if x < pivot]
    lst2 =[x for x in lst if x == pivot]
    lst3 =[x for x in lst if x > pivot]
    return simple_qsort(lst1) + lst2 + simple_qsort(lst3)
n=0
simple_qsort([10,2,6,1,3,4,5,8,7,9])
print(n)

上の数字の配列だとn=13となり再帰回数が13回であることを示しています。

現在再起呼び出し回数のできるだけ多いリストと少ないリストの配列を考えなければいけないのですが
どういった解き方をすればよいのか分かりません。ご教授いただければ幸いです。

Answer 1

まじめに理屈を考えるのには時間がかかるので、手抜きをして実験的にやってみました。

Angela_Nakasugiさんのコードを修正して、リストを与えると、それの再帰呼び出しの回数と結果を返す関数を作りました。

def simple_qsort(lst):
    if len(lst) <=1:
        return 1, lst
    pivot =lst[0]
    lst1 =[x for x in lst if x < pivot]
    lst2 =[x for x in lst if x == pivot]
    lst3 =[x for x in lst if x > pivot]
    n1, sq1 = simple_qsort(lst1)
    n3, sq3 = simple_qsort(lst3)
    return n1+n3+1, sq1 + lst2 + sq3

実行例

>>> print(simple_qsort([10,2,6,1,3,4,5,8,7,9]))
(13, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10])

次に、長さがlengthのリストを与えた時にその順列のそれぞれに対して再帰呼び出しの回数を計算して分類する関数を作ってみました。
戻り値は辞書で、再帰呼び出しの回数をキーとして、値はその回数となる順列のリストです。

import itertools

def count_qs(length):
    counter = {}
    for lst in itertools.permutations(list(range(1, length+1))):
        n, sq = simple_qsort(lst)
        if n in counter:
            counter[n].append(lst)
        else:
            counter[n] = [lst]
    return counter

結果が長くなって読みにくいので、リストを値として持つ辞書に対して、同じキーに対して値のリストの長さを返す関数を作りました。

def counter_count(counter):
    return {key: len(counter[key]) for key in counter}

実行例

>>> counter_count(count_qs(5))
{9: 16, 7: 88, 5: 16}

これは、[1,2,3,4,5]の順列を並べ替えるときの再帰呼び出しの回数が9となる順列は16通り、7となる順列は88通り、5となる順列は16通りであることを示しています。

2から8までの結果を並べてみると以下になります。

>>> counter_count(count_qs(2))
{3: 2}
>>> counter_count(count_qs(3))
{5: 4, 3: 2}
>>> counter_count(count_qs(4))
{7: 8, 5: 16}
>>> counter_count(count_qs(5))
{9: 16, 7: 88, 5: 16}
>>> counter_count(count_qs(6))
{11: 32, 9: 416, 7: 272}
>>> counter_count(count_qs(7))
{13: 64, 11: 1824, 9: 2880, 7: 272}
>>> counter_count(count_qs(8))
{15: 128, 13: 7680, 11: 24576, 9: 7936}

ここから、10の場合にはもっとも多い再帰呼び出しの回数が19でもっとも多い再帰呼び出しの回数が11となることが予想されます。

この予想が正しいとして、19と11となるリストを一つ出せるようにcount_qsを少し改造した以下の関数を作りました。

def count_qs_sample(length, m):
    counter = {}
    for lst in itertools.permutations(list(range(1, length+1))):
        n, sq = simple_qsort(lst)
        if n == m:
            return lst

これを使って実行してみると、

>>> count_qs_sample(10,19)
(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
>>> count_qs_sample(10,11)
(1, 3, 2, 5, 4, 7, 6, 9, 8, 10)

あとは、「10の場合にはもっとも多い再帰呼び出しの回数が19でもっとも多い再帰呼び出しの回数が11となることが予想されます。」は数値的には以下のように証明できています。

>>> counter_count(count_qs(10))
{19: 512, 17: 128512, 15: 1304832, 13: 1841152, 11: 353792}

しかし、一般化するためにはちゃんと説明する論理が必要ですね。

Comments

[Angela_Nakasugi]

私が想像していたよりも煩雑なものだったのですね・・・
流れが分かりやすい丁寧な説明、ありがとうございます！