引用サイト

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

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

プログラム

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

q_sort.py

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
小さい配列ｌ　＝｛３，１，２｝
大きい配列ｒ　＝｛７，６，９，８，１０｝
と分解する