これは備忘録です

ホントに忘れそう

引用サイト

今回は先に整理するために拝見させていただいたサイトを紹介させていただきます

• アルゴリズム参考
• トレース参考

それぞれ少しだけアルゴリズム自体が違いますが同じクイックソートなので@muijpさんのアルゴリズムを元に整理させていただきます

プログラム

@muijpさんのクイックソートに先日@shiracamusさんからアドバイスをいただいたランダム配列のプログラムとデバッグ用の出力を入れました

def qSort(a):
    print(a)#デバッグ用
    if len(a) in (0, 1):
        return a

    p = a[-1]
    l = [x for x in a[:-1] if x <= p]
    r = [x for x in a[:-1] if x >  p]

    return qSort(l) + [p] + qSort(r)
a = r.sample(range(1,11),k=9)
qSort(a)
#出力＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
[3, 7, 1, 6, 9, 8, 2, 10, 4]
[3, 1, 2]
[1]
[3]
[7, 6, 9, 8, 10]
[7, 6, 9, 8]
[7, 6]
[]
[7]
[9]
[]
>>[1, 2, 3, 4, 6, 7, 8, 9, 10]

うん、プログラムが簡潔すぎて分からない。

分解して考える

まず注目するべきところは
return qSort(l) + [p] + qSort(r)
だと思う。
コレはクイックソートの特徴である「ピポット(注目しているセル)」の右と左に小さい数字(配列)と大きい数字(配列)を置く、という部分になる。　　　　

トレース参考
このサイトのgifを見ていくと
1. 真ん中ピポットを取る
2. 外側から順に左にある小さい数と右にある大きい数を交換する
3. 走査範囲を最小～ピポットに変え、中央にピポットを持ってくる
を繰り返してるのがわかる。

　　
　　
ただ、今回のプログラムでは
p = a[-1]
として、ピポットを最後の数に取っている
そして、
l = [x for x in a[:-1] if x <= p]
r = [x for x in a[:-1] if x > p]
で、ピポットより大きい数字とピポットより小さい数字に分け、それをreturnで(再起関数を呼びつつ)接合している。
　　
　　

最初の
if len(a) in (0, 1):
return a
は文字が1文字以下ならそれを再起関数の返り値として返している。

トレースし直す

以上を踏まえて先ほどの乱数でトレースしてみる

#出力＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
[3, 7, 1, 6, 9, 8, 2, 10, 4]
[3, 1, 2]
[1]
[3]
[7, 6, 9, 8, 10]
[7, 6, 9, 8]
[7, 6]
[]
[7]
[9]
[]
>>[1, 2, 3, 4, 6, 7, 8, 9, 10]

配列[3, 7, 1, 6, 9, 8, 2, 10, 4]
ピポット p　＝　4
小さい配列ｌ　＝｛３，１，２｝
大きい配列ｒ　＝｛７，６，９，８，１０｝
と分解する

小さい配列を再起し、
p=2
l={1}、r={3}
と分解

それぞれ1つまで分解されたので確定する

大きい配列を再起すると、今度のpは10で最大なので、
l={7,6,9,8} 、r={}
と分解される

その後すべての数を細分化していき

結合されたデータで返される

と、なってます。

さいごに

今回はほぼ丸パクリとなってしまいましたが、いかに自分が理解してないのかがわかってしましました。
このような機会があって本当に良かったです。