Pythonでクイックソートを実装してみました。
クイックソートは、分割統治法(divide-and-conquar)を使い一度分割し再度合体させることで高速なソートを実現します。
- 要素が1以下なら処理を行わない
- リストの1番左の値をピボットとして選択
- ピボット以下をサブリストleft,ピボットよりも大きい値をサブリストrightに分割する
- 分割した2つのサブリストに再帰的にソートを適用する
- 分割した2つのサブリストとピボットを合体して終了
具体的に流れを見ていきます。
1. 整列前のリストです。 [3, 9, 6, 1, 2] 2. 1番左の値をピボットに選択 pivot 3 3. サブリストrightを作成、クイックソートを適用し整列する [9, 6] 4. サブリストleftを作成、クイックソートを適用し整列する [1, 2] 5. 最後にleft,pivot,rightを合成して完成! [1, 2, 3, 6, 9]
コード例は以下の通り。
def QuickSort(num_list): n = len(num_list) if n <= 1: return num_list pivot = num_list[0] right=[] left=[] for i in range(1,n): if num_list[i] <= pivot: left.append(num_list[i]) else: right.append(num_list[i]) r = QuickSort(right) l = QuickSort(left) return l+[pivot]+r
おわり。