クイックソート、再帰関数での戻り値

Question

このコードでのクイックソートについて質問です。sort()にdataが渡されて初めてfor文の処理が終わった後、left=[1,3,2,4,2,1]right=[]middle=[5]になるなど再帰関数が終わるまでの処理、そして、その後5は出てこないことも分かります。ここで質問なのですが、この5などmiddleに入った値をどのように最終的にクイックソートしたリストで戻り値として返してくるのかが分からないです。最初にでていった5はどこにいくのでしょうか。説明文が分かりにくくすみません。よろしくお願いします。

def sort(data):
    n = len(data)
    pivot = data[n//2]
    left,right,middle = [],[],[]
    for i in range(n):
        if data[i] < pivot:
            left.append(data[i])
        elif data[i] > pivot:
            right.append(data[i])
        else:
            middle.append(data[i])
        print("left = ",left)
        print("right=",right)
        print("middle= ",middle)
        print("-----------")
    if left:
        left = sort(left)
    if right:
        right = sort(right)
    return left + middle + right

data = [1,3,2,5,4,2,1]
data = sort(data)
print(data)

Answer 1

middleに入った値をどのように最終的にクイックソートしたリストで戻り値として返してくるのか

ppaulさんの回答と同じですが、最後の処理

    if left:
        left = sort(left)
    if right:
        right = sort(right)
    return left + middle + right

で、left は ソート済みのleftに入っていもの、rightはソート済みのrightに入っているものになり、

最後のreturnのところで、left 、 middle、 right の順につなげているからです。

Comments

[Giovannaaa]

ありがとうございました。

Answer 2

Visualize Python, Java, JavaScript, C, C++, Ruby code execution というサイトがあります。

ここのテキストボックスに Python スクリプトを貼り付けて Visualize Execution をクリックすると、スクリプトがステップ実行されてリストの内容の変化を視覚的に眺めることができます。

掲題のスクリプトは再帰関数なので 208 ステップにもなりますが、参考にしてみて下さい。

Comments

[Giovannaaa]

ありがとうございました。

Answer 3

リストの和をreturnしているからです。
リストの和とは以下のようなものです。

>>> left=[1,3,2,4,2,1]
>>> right=[]
>>> middle=[5]
>>>
>>> print(left + middle + right)
[1, 3, 2, 4, 2, 1, 5]

リストの和については、公式ドキュメント チュートリアル 3.1.3. リスト型 (list)や公式ドキュメント シーケンス型 --- list, tuple, rangeをお読みください。

Comments

[Giovannaaa]

回答ありがとうございます。リストの和は分かったのですが、1回目のif left:で[1,3,2,4,2,1]がsort(left)に入ると思うのですがここで５がなぜ関数が終わったあとに戻り値で返されるのかわからないです。すみません。

[Giovannaaa]

ありがとうございました。