再帰関数を使用してクイックソートを行う処理についての質問です。
①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)
回答2件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。