マージソートとクイックソート
小さい配列へ分ける過程と、整列結果を組み合わせる方法を学びます。
説明
マージソートは配列を二つへ分け、それぞれを整列してから小さい値を順に取り出して併合します。クイックソートは基準値であるピボットより小さい値と大きい値へ分け、それぞれを整列します。分ける基準と、結果を作る段階が異なります。
6・2・5・1・4・3を使い、マージソートでは整列済みの左右から併合する処理を、クイックソートではピボットによる分割を表示します。最後にピボット選択が偏る入力を調べます。ここでは過程を表示するため新しい配列を作る実装を使います。
1位置で二つに分ける
マージソートの最初の分割では値の大小を使いません。中央の位置で左と右に分けます。1要素以下なら既に整列済みなので分割を止めます。
values = [6, 2, 5, 1, 4, 3]入力; middle = len(values)//2中央位置; values[:middle], values[middle:]左右の部分配列左は6・2・5、右は1・4・3です。各部分をさらに分け、1要素から併合していけば左右それぞれの整列済み配列を得られます。
2整列済みの左右を用意
最終併合の直前では左が2・5・6、右が1・3・4です。ここでは併合だけを先に調べるため、その状態を用意します。
left = [2, 5, 6]; right = [1, 3, 4]整列済みの左右; i = j = 0; merged = []左右の読取り位置と出力; left[i], right[j]先頭同士を比較先頭同士は2と1なので、まず右の1を選びます。どちらの配列も整列済みという条件があれば、残りの全要素を毎回調べる必要はありません。
3小さい先頭から取り出す
右の1、左の2、右の3、右の4を順に選びます。選んだ側の位置だけ進めます。
merged.append(right[j]); j += 1右の1; merged.append(left[i]); i += 1左の2; merged.append(right[j]); j += 1右の3; merged.append(right[j]); j += 1右の4; merged, (i, j)出力と読取り位置出力は1・2・3・4、左の位置1、右の位置3です。右を全て使い切ったので、左の残り5・6をそのまま続けられます。
4片側の残りを続ける
左右のどちらかが空になったら、もう片方の未使用部分を連結します。
merged.extend(left[i:])左の残り5・6; merged.extend(right[j:])右の残りは空; merged, merged == sorted(values)結果を照合1から6の昇順になりました。併合は各要素を一度ずつ出力するので、合わせる要素数に比例する処理です。分割の各段でこの併合を繰り返します。
5ピボットで三つに分ける
クイックソートでは値4をピボットにします。4未満、4と等しい、4より大きい値へ分けます。等しい値も独立させると重複があっても縮小できます。
pivot = 4基準値; lower = [x for x in values if x < pivot]小さい値; equal = [x for x in values if x == pivot]同じ値; upper = [x for x in values if x > pivot]大きい値; lower, equal, upper三つの部分小さい側は2・1・3、大きい側は6・5です。分割した段階では両側の内部はまだ整列されていません。ただし、小さい側の全てがピボットより前へ来ることは確定します。
6左右を整列して連結
小さい側と大きい側をそれぞれ整列すると、ピボットの前後へそのまま連結できます。この段階では併合時の大小比較が要りません。
sorted(lower) + equal + sorted(upper)整列済みの左右とピボットを連結, len(lower), len(upper)左右の大きさ結果は同じ昇順です。ここでは左右の整列にsortedを使い、クイックソートの分割と連結に焦点を当てました。クイックソート自身では同じピボット分割を左右へ再帰的に適用します。
7分割を繰り返す
配列中央にある値をピボットとして再帰する関数を定義します。要素数が1以下ならそのまま返し、それ以外は小・同・大へ分けます。
def quick(a):再帰的な分割
if len(a) <= 1: return a終了条件
p = a[len(a)//2]中央位置の値を基準に
low = [x for x in a if x < p]小さい側
same = [x for x in a if x == p]等しい値
high = [x for x in a if x > p]大きい側
return quick(low) + same + quick(high)両側を再帰して連結ピボットと同じ値は再帰から外れるため、全要素が同じ場合でも止まります。この実装は新しいリストを複数作るので、配列内で交換する実装とはメモリの使い方が違います。
8重複と空配列で実行
通常の配列に加え、同じ値だけの配列と空配列でも実行します。
quick(values)初期配列, quick([4, 4, 4])全要素が等しい, quick([])空配列昇順、4・4・4、空配列が返ります。全要素がピボットと等しい場合、小さい側と大きい側がともに空になり、再帰が終わります。
9先頭ピボットが偏る例
昇順配列で常に先頭をピボットにすると、小さい側が空、大きい側が残り全てになります。未確定部分の大きさとピボット以外との比較回数を計算します。
sizes = list(range(6, 1, -1))片側へ残る部分の大きさ; sizes, [n-1 for n in sizes], sum(n-1 for n in sizes)各段と総比較回数大きさ6・5・4・3・2に対して5・4・3・2・1、計15比較です。分割が均等なら深さは対数程度ですが、偏り続けると二乗程度になります。中央位置の値を選んでも、常に中央値が得られるわけではありません。
まとめ
マージソートは位置で分割し、整列済み部分を先頭同士の比較で併合します。
クイックソートは値の大小で分割し、左右を整列してピボットの前後へ連結します。
終了条件と分割の偏りが処理回数を左右します。新しい配列を作る実装では追加メモリも必要です。
操作履歴と解説を振り返れます。
Python 3
values = [6, 2, 5, 1, 4, 3]; middle = len(values)//2; values[:middle], values[middle:]([6, 2, 5], [1, 4, 3])
left = [2, 5, 6]; right = [1, 3, 4]; i = j = 0; merged = []; left[i], right[j](2, 1)
merged.append(right[j]); j += 1; merged.append(left[i]); i += 1; merged.append(right[j]); j += 1; merged.append(right[j]); j += 1; merged, (i, j)([1, 2, 3, 4], (1, 3))
merged.extend(left[i:]); merged.extend(right[j:]); merged, merged == sorted(values)([1, 2, 3, 4, 5, 6], True)
pivot = 4; lower = [x for x in values if x < pivot]; equal = [x for x in values if x == pivot]; upper = [x for x in values if x > pivot]; lower, equal, upper([2, 1, 3], [4], [6, 5])
sorted(lower) + equal + sorted(upper), len(lower), len(upper)([1, 2, 3, 4, 5, 6], 3, 2)
def quick(a):
if len(a) <= 1: return a
p = a[len(a)//2]
low = [x for x in a if x < p]
same = [x for x in a if x == p]
high = [x for x in a if x > p]
return quick(low) + same + quick(high)quick(values), quick([4, 4, 4]), quick([])([1, 2, 3, 4, 5, 6], [4, 4, 4], [])
sizes = list(range(6, 1, -1)); sizes, [n-1 for n in sizes], sum(n-1 for n in sizes)([6, 5, 4, 3, 2], [5, 4, 3, 2, 1], 15)
演習完了