リリース・改善中
Algorithm
ソートはデータを決まった順序に並べるアルゴリズムです。マージソート、クイックソート、ヒープソート、安定性、n log n の下界、組み込みソートを解説します。
ソート（整列）は、要素を数値順・辞書順・時刻順など決まった順序に並べ替えるアルゴリズムです。2 つの要素を比べて前後を決める比較ソート（バブルソート、挿入ソート、選択ソート、マージソート、クイックソート、ヒープソート）と、整数の値や桁を直接使う計数ソート・基数ソートのような比較しないソートに大きく分けられます。
ソートは二分探索、重複の除去、区間のマージ、ランキングなど多くの処理の前準備になるため、最初に学ぶ基本アルゴリズムの一つです。比較ソートは最悪の場合 Ω(n log n) 回より少ない比較では済まないという下界、安定ソートとインプレースソートの違い、そして Python の Timsort や多くの C++ std::sort 実装が採用するイントロソートといった組み込みソートの動きを知っておくと、実務でもコーディング面接でも適切な選択ができます。
学ぶときは、まず小さな配列で挿入ソート、マージソート、クイックソートの動きを手で追い、次にマージソートとクイックソートを自分で実装して最良・平均・最悪の計算量を比べるのがおすすめです。その後、キー関数や比較関数で組み込みソートを使う方法を身につけ、区間のマージや転倒数の計算のようにソートを応用した問題を練習しましょう。
マージソートは半分に分けてからマージし、クイックソートはピボットを基準に分割します。どちらも平均 O(n log n) で動きます。
安定ソートは同じキーを持つ要素の元の順序を保ち、インプレースソートは追加メモリをほとんど使いません。どちらが重要かは用途によって変わります。
決定木による議論から、比較だけで並べるソートは最悪の場合 n log n に比例する回数の比較が必要だとわかります。マージソートとヒープソートはこの下界に到達します。
計数ソートと基数ソートは、値の範囲や桁数が限られた整数を、要素同士を比較せずにほぼ線形時間で並べます。
merge_sort はリストを半分に分けてそれぞれを再帰的にソートし、2 つのソート済みリストの先頭を比べて小さいほうから取り出しながら 1 つにまとめます。値が等しいときは左側を先に取る（<=）ので安定ソートになり、入力にかかわらず O(n log n) で動きます。最後の行で、結果が組み込みの sorted() と一致するかを確かめます。
merge_sort.py
def merge_sort(items):
"""Return a new sorted list (stable, O(n log n))."""
if len(items) <= 1:
return list(items)
mid = len(items) // 2
left, right = merge_sort(items[:mid]), merge_sort(items[mid:])
merged, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # take the left one on ties: stable
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
return merged + left[i:] + right[j:]
if __name__ == "__main__":
data = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(data)) # [3, 9, 10, 27, 38, 43, 82]
print(merge_sort(data) == sorted(data)) # True
python merge_sort.pyインストールから ソート の中心となる考え方まで、6 章で順を追って学びます。
ソート について質問し、経験を共有し、意見を交わす場所です。
まだディスカッションはありません。最初の話題を始めましょう。
コメント 0件
ログイン · ログインするとコメントできます。
最初のコメントを書いてみましょう。