STEP 2.2 クイックソート (quick sort) - Pythonの例

解答例
import random

# 下のコードはインデントに要注意です。どのコードブロックに関係する行かはインデントで決まります。
def quick_sort(array):
    if array == []:  # 停止条件 []
        return array
    else:
        pivot = array[0] 
        left = []   # 小さいもの
        pivots = [] # 同じ値のもの (自分自身も比較される)
        right = []  # 大きいもの

       for val in array:               #ここが、partition操作にあたる。3つのリストに分けている
           if val < pivot:
               left.append(val)
           elif val == pivot:
               pivots.append(val)
           else:
               right.append(val)

       return(quick_sort(left) + pivots + quick_sort(right))

<実行例>

[tsuchiya@www1 python]$ python3 quick_sort.py
before = [47, 15, 55, 54, 71, 68, 42, 97, 47, 89]
after  = [15, 42, 47, 47, 54, 55, 68, 71, 89, 97]

[tsuchiya@www1 python]$ python3 quick_sort.py
before = [76, 93, 97, 62, 70, 43, 4, 46, 6, 46]
after  = [4, 6, 43, 46, 46, 62, 70, 76, 93, 97]