クイックソートにやられた

Python

クイックソート。
アルゴリズム自体は簡単だけど、実装は微妙にめんどくさい。

inspire先↓
クイックソート : アルゴリズム

書いたコードはほぼリンク先と同じだけど、中身で何をしているかさっぱり
つまり、再帰が全く身についていないことが分かった。
これは大きな収穫。
どう動いているか理解するために、再帰呼び出しの深さとソートの途中の様子がわかるようにコーディングした。

# Quick Sort

import random

def QuickSort(numList, depth):
    depth += 1

    if len(numList) < 1:
        return numList

    pivot = numList[0]
    lower_pivot = []
    upper_pivot = []

    for num in numList[1::]:
        if num <= pivot:
            lower_pivot.append(num)
        else: # num > pivot
            upper_pivot.append(num)

    print "depth ->", depth
    print "pivot ->", pivot
    print "lower_pivot ->", lower_pivot
    print "upper_pivot ->", upper_pivot
    print

    lower_pivot = QuickSort(lower_pivot, depth)
    depth -= 1
    upper_pivot = QuickSort(upper_pivot, depth)
    depth -= 1
    pivot = [pivot]

    print "Sorting Step"
    print lower_pivot + pivot + upper_pivot
    print 

    return lower_pivot + pivot + upper_pivot



def main():
    N = 20
    numList = [random.randint(1,1000) for x in range(20)]
    print numList

    depth = 0
    QuickSort(numList, depth)

if __name__ == "__main__":
    main()

D:\workspace\Python\2-18>python q_sort.py
[865, 797, 573, 96, 443, 228, 925, 785, 642, 989, 465, 528, 952, 365, 879, 145,
482, 113, 268, 393]
depth -> 1
pivot -> 865
lower_pivot -> [797, 573, 96, 443, 228, 785, 642, 465, 528, 365, 145, 482, 113,
268, 393]
upper_pivot -> [925, 989, 952, 879]

depth -> 2
pivot -> 797
lower_pivot -> [573, 96, 443, 228, 785, 642, 465, 528, 365, 145, 482, 113, 268,
393]
upper_pivot -> []

depth -> 3
pivot -> 573
lower_pivot -> [96, 443, 228, 465, 528, 365, 145, 482, 113, 268, 393]
upper_pivot -> [785, 642]

depth -> 4
pivot -> 96
lower_pivot -> []
upper_pivot -> [443, 228, 465, 528, 365, 145, 482, 113, 268, 393]

depth -> 4
pivot -> 443
lower_pivot -> [228, 365, 145, 113, 268, 393]
upper_pivot -> [465, 528, 482]

depth -> 5
pivot -> 228
lower_pivot -> [145, 113]
upper_pivot -> [365, 268, 393]

depth -> 6
pivot -> 145
lower_pivot -> [113]
upper_pivot -> []

depth -> 7
pivot -> 113
lower_pivot -> []
upper_pivot -> []

Sorting Step
[113]

Sorting Step
[113, 145]

depth -> 5
pivot -> 365
lower_pivot -> [268]
upper_pivot -> [393]

depth -> 6
pivot -> 268
lower_pivot -> []
upper_pivot -> []

Sorting Step
[268]

depth -> 5
pivot -> 393
lower_pivot -> []
upper_pivot -> []

Sorting Step
[393]

Sorting Step
[268, 365, 393]

Sorting Step
[113, 145, 228, 268, 365, 393]

depth -> 4
pivot -> 465
lower_pivot -> []
upper_pivot -> [528, 482]

depth -> 4
pivot -> 528
lower_pivot -> [482]
upper_pivot -> []

depth -> 5
pivot -> 482
lower_pivot -> []
upper_pivot -> []

Sorting Step
[482]

Sorting Step
[482, 528]

Sorting Step
[465, 482, 528]

Sorting Step
[113, 145, 228, 268, 365, 393, 443, 465, 482, 528]

Sorting Step
[96, 113, 145, 228, 268, 365, 393, 443, 465, 482, 528]

depth -> 3
pivot -> 785
lower_pivot -> [642]
upper_pivot -> []

depth -> 4
pivot -> 642
lower_pivot -> []
upper_pivot -> []

Sorting Step
[642]

Sorting Step
[642, 785]

Sorting Step
[96, 113, 145, 228, 268, 365, 393, 443, 465, 482, 528, 573, 642, 785]

Sorting Step
[96, 113, 145, 228, 268, 365, 393, 443, 465, 482, 528, 573, 642, 785, 797]

depth -> 1
pivot -> 925
lower_pivot -> [879]
upper_pivot -> [989, 952]

depth -> 2
pivot -> 879
lower_pivot -> []
upper_pivot -> []

Sorting Step
[879]

depth -> 1
pivot -> 989
lower_pivot -> [952]
upper_pivot -> []

depth -> 2
pivot -> 952
lower_pivot -> []
upper_pivot -> []

Sorting Step
[952]

Sorting Step
[952, 989]

Sorting Step
[879, 925, 952, 989]

Sorting Step
[96, 113, 145, 228, 268, 365, 393, 443, 465, 482, 528, 573, 642, 785, 797, 865,
879, 925, 952, 989]

う〜ん、まだすっきり再帰の挙動が分かりきってないなぁ。
関数型言語とか勉強しようかなぁ。
とりあえず、実装としてはpivotが順番どおりに並んでいくんすな。
ふむふむ。