python 再帰関数について

Question

再帰関数を使用してクイックソートを行う処理についての質問です。
①if leftの条件式
for文を処理してif文に入るところまでは流れを追うことが出来たのですが、
if文に入った際、if(条件式)のところがif leftになっているのですが、left部分の条件式は
どのようになっているのでしょうか。
②最後のif leftとif rightの再帰関数の流れ
なぜ、if rightの処理を終えた後にif leftの関数を呼び出しているのでしょうか。

再帰関数の初歩的な部分だと思うのですが、いまいち流れが掴めません。
教えていただきたく思います。
よろしくお願いします。

実行結果
⑥ pivot 5
0 回目
① left 1 [1]
1 回目
① left 3 [1, 3]
2 回目
① left 2 [1, 3, 2]
3 回目
③ middle 5 [5]
4 回目
① left 4 [1, 3, 2, 4]
5 回目
① left 2 [1, 3, 2, 4, 2]
6 回目
① left 0 [1, 3, 2, 4, 2, 0]
⑥ pivot 4
0 回目
① left 1 [1]
1 回目
① left 3 [1, 3]
2 回目
① left 2 [1, 3, 2]
3 回目
③ middle 4 [4]
4 回目
① left 2 [1, 3, 2, 2]
5 回目
① left 0 [1, 3, 2, 2, 0]
⑥ pivot 2
0 回目
① left 1 [1]
1 回目
② right 3 [3]
2 回目
③ middle 2 [2]
3 回目
③ middle 2 [2, 2]
4 回目
① left 0 [1, 0]
⑥ pivot 0
0 回目
② right 1 [1]
1 回目
③ middle 0 [0]
⑥ pivot 1
0 回目
③ middle 1 [1]
⑤ right [1]
④ left [0, 1]
⑥ pivot 3
0 回目
③ middle 3 [3]
⑤ right [3]
④ left [0, 1, 2, 2, 3]
④ left [0, 1, 2, 2, 3, 4]
[0, 1, 2, 2, 3, 4, 5]

コード
```def sort(data):
    n = len(data)
    pivot = data[n//2]
    print("⑥ pivot", data[n//2])
    left,right,middle = [],[],[]
    for i in range(n):
        print(i,"回目")

        if data[i]<pivot:
            left.append(data[i])
            print("① left",data[i],left)
        elif data[i]>pivot:
            right.append(data[i])
            print("② right", data[i],right)
        else:
            middle.append(data[i])
            print("③ middle", data[i],middle)
    if left:
        left = sort(left)
        print("④ left", left)
    if right:
        right = sort(right)
        print("⑤ right", right)
    return left + middle + right
data = [1, 3,2,5,4,2,0]
data = sort(data)
print(data)

Answer 1

qnoirさんの回答で充分と思いますが、再帰は難しいので別観点で。

①if leftの条件式

leftとrightはpivotより小さいものと大きいものがそれぞれ入ったリストですよね。 リストそのものを条件式に入れるのはよくやる書き方で、[]がfalseと判定されることを利用しています。

if left ！= []:

と書くのと同じです。

②最後のif leftとif rightの再帰関数の流れ

pivotを選び、それより小さいものをleftに、大きいものをrightに入れる
leftが空でなければ
    leftの中身を「ソートする」
    (空ならそのまま)
rightが空でなければ
    rightの中身を「ソートする」
    (空ならそのまま)
left + pivot + right がソート済みのリスト

こうなっています。
まずは、これでソートできることがわかるでしょうか。

そして再帰になっているのは、「ソートする」の部分です。
そこの部分を追いかけなければ、それで終りです。

しかし、関数の出力を追いかけようとするとそうはいかず、leftの中身をソートするには、「pivotを選んで...」のように、深い方にどんどん進んでいくので、わかりにくいのです。 枝分かれの枝をどんどん先にたどることになるので、把握しにくいと思います。

適当な図があればわかりやすいのですが、このサイトですが、方式が少し違うのでまったく同じではにのですが、真ん中あたりの図の青い矢印が実際の処理の順番を表わしています。 実行したときに表示されるものはこういうような経路での出力だということです。

Answer 2

①if leftの条件式
for文を処理してif文に入るところまでは流れを追うことが出来たのですが、if文に入った際、if(条件式)のところがif leftになっているのですが、left部分の条件式はどのようになっているのでしょうか。

[] （空っぽのリスト）は Falsy といって「False」と同じ扱いです。

left の中身がない[] の場合
if left は False と評価されます。

left に中身がある場合　たとえば[1] 等の場合
if left は True と評価されます。

②最後のif leftとif rightの再帰関数の流れ
なぜ、if rightの処理を終えた後にif leftの関数を呼び出しているのでしょうか。

コードから察するに「> なぜ、if leftの処理を終えた後にif rightの関数を呼び出しているのでしょうか。」
の誤りでしょうか？
ここは、下記のようにleftとrightを入れ替えて、if rightの処理を終えた後にif leftの処理を行っても結果は変わりません。

    if right:
        right = sort(right)
    if left:
        left = sort(left)

この処理の本質は、
pivotを基準として小さい数をleftに集める。
pivotを基準として大きい数をrightに集める。
pivotと等しい数をmiddleに集める。
集まった要素の数が1つになるまで繰り返す。
→要素の数が１つであれば必ずその数がmiddleに格納され、left、rightが空リスト[]になる
→left middle right が連結されたリストが、呼び出し元に返される
....
の再帰的動作でソートすることにあります。

leftとrightの処理の定義が一貫していれば、leftとrightの処理の順番は結果に影響を及ぼしません。

Comments

[yu_jin]

リストで条件判定が出来るのは知りませんでした。ありがとうございます。