クイックソートのプログラミングについて Python

Question

平素よりお世話になっております。
クイックソートのプログラミングについて質問させて頂きます。
クイックソートは、リストの先頭の要素を基準に、小さいものと大きいもの振り分ける行為を振り分け要素数が１になるまで繰り返し整列させて結合させるものだと理解しています。
ただ、それに伴うプログラムが各所わからなかったので質問させていただきます。
本は、
書名：Pythonで体験してわかるアルゴリズムとデータ構造
著者：西澤弘毅、森田光
出版日：２０１８年６月３０日初版
出版社：近代科学社
を使っています。

def sort(A):
    if len(A)<2:
       return A
    p=A[0]
    X,Y=divide(p,A[1:])
    return sort(X)+[p]+sort(Y)

def divide(p,A):
    if len(A)<1:
       return ([],[])
    X,Y= divede(p,A[1:])
    a=A[0]
    if a<p:
       return ([a]+X,Y)
    else:
       return (X,[a]+Y)

１つめの質問
上記のソースの５行目
X,Y=divide(p,A[1:])
X,Yに対して関数でアンパックというのが意味わかりません。関数からX,Yそれぞれに代入できる複数の値が出力されるのでしょうか？

２つめの質問
５行目で変数の呼び出し→９~１０行目では条件を満たさな場合、１１行目
X,Y= divede(p,A[1:])
に移行すると思うのですが、無限ループするのでは？と思うのですが、ここの考え方がよくわかっていないので動き方について教えてください。

３つめの質問
a=A[0]
if a<p:
return ([a]+X,Y)
else:
return (X,[a]+Y)
が何をやっているのかわかりません。

...
とあげればきりがないほど全体の流れが理解できていません。回答のほどお願いします。

Answer 1

１つめの質問
上記のソースの５行目
X,Y=divide(p,A[1:])
X,Yに対して関数でアンパックというのが意味わかりません。関数からX,Yそれぞれに代入できる複数の値が出力されるのでしょうか？

初心者はその捉え方でもいいですが、うるさいことを言うと返す値は1つで、pythonのアンパックという機能でそれぞれの変数に代入されるわけですね。

    if a<p:
       return ([a]+X,Y)
    else:
       return (X,[a]+Y)

返り値は([a]+X,Y)または(X,[a]+Y)というタプルなのですが、これの各要素がXとYに代入されます。

>>> tup = (1, 2)
>>> a, b = tup
>>> a
1
>>> b
2

詳細はシーケンスアンパックとかで検索すれば色々出てくると思います。

---

２つめの質問

５行目で変数の呼び出し→９~１０行目では条件を満たさな場合、１１行目
X,Y= divede(p,A[1:])
に移行すると思うのですが、無限ループするのでは？と思うのですが、ここの考え方がよくわかっていないので動き方について教えてください。

sort関数の引数のAとdivide関数の引数のAは別物なので、同じように見えるA[1:]という式でも結果が違います。具体的には、再帰呼び出しのたびに先頭の要素がなくなったリストが渡されています。

---

３つめの質問

a=A[0]
if a<p:
return ([a]+X,Y)
else:
return (X,[a]+Y)
が何をやっているのかわかりません。

上では最初の要素を除外したリストを2つに分割していますね。

最初の要素をどっち側にいれるかべきかをここで決めています。

Comments

[mau]

２つ目の質問についてもう少し詳しく知りたいので質問させていただきます。関数の性質上sort(A)もdivide(p,A)もローカル変数なので違うものであることは承知してます。聞きたいのはこのことではなく、もう少し詳しい流れをお聞きしたいのです。具体的に話を進めるため、今回A=[4,8,2,9,6,3,5,1,7]と仮定させていただきます。このとき、sort(A)での処理でA[0]=4をpに代入し、A[0]以外の他のリストをdivide(p,A[1:])で処理を行うことをしていますよね！？そのあと、divide(p,A[1:])の処理を進めると、
if len(A)<1:
return ([],[])
というところにいき、このときlen(A)は8なので条件を満たさないのでスルーする。このあと、
X,Y= divede(p,A[1:])
にたどりつき
pの値と要素数が変化しないと思いました。そのため無限ループなのでは？と考えたのですが、ここでの処理は具体的にどのように動いているのでしょうか？

[hayataka2049]

そこまでわかっておられるにも関わらず、「pの値と要素数が変化しないと思いました。」と判断された理由がよくわかりません。
ローカル変数のA（値は[8,2,9,6,3,5,1,7]）に対してA[1:]は[2,9,6,3,5,1,7]になるので、ちゃんと短くなります。

Answer 2

プログラムの実行環境はありますか？
分からなければ実際に動かして、print関数等でステップ毎に変数の中身などを確認しましょう。

Answer 3

質問1:

if a<p:
       return ([a]+X,Y)
    else:
       return (X,[a]+Y)

の部分がdivide()の返却ですので、
この二つの値をそれぞれX, Yに代入している形式です。

質問2:
devide()は再帰呼び出し(関数の中で同名の関数が呼び出される)になっていますが、再帰が深くなるごとに配列Aの要素数は1ずつ小さくなっているので、いつかは必ず
if len(A) < 1
に引っかかり、無限ループはしません。

質問3:配列Aの先頭要素A[0]と基準値pを比較し、A[0]がpより小さければ一つ目の配列(X)に、pより大きければ二つ目の配列(Y)に格納されるようなロジックになっています。