順序・安定性・元データ

並べ替えが正しいかは、値が昇順になっただけで判断できるのでしょうか。同じ値の注文の順序や、空のデータ、使えるメモリも確認が必要です。まず、何をどの順序で並べるかを決めます。

事例：優先度が同じ注文は受付順を守る

受付順に並ぶ注文は(3,A)、(1,B)、(3,C)、(2,D)です。括弧内は優先度と注文IDで、数値が小さい注文を先にします。同じ優先度では受付順を維持する要件があります。

並べ替え後は(1,B)、(2,D)、(3,A)、(3,C)です。AとCは同じ3ですが、受付順がA→Cなのでこの順を残します。注文IDの文字順で並べる要件とは別です。

順序・安定性・元データ

ソートの検証では三つの条件を確認します。

比較するキーと、安定性を分ける

キー
順序を決める値。この例では優先度です。
安定
同じキーの要素が、ソート前と同じ相対順序で残る性質です。
追加キー
受付番号を比較条件に加える方法。安定性の利用とは実現方法が異なります。

安定性は、同じ値の要素がある場合の順序の要件です。すべての値が異なるテストだけでは、安定性の欠陥を見つけられません。比較キーと期待結果を文章で固定してから算法を選びます。

挿入ソートは、どこまで整列済み？

先頭の一要素を整列済みとし、次の要素をその中の正しい位置へ入れます。挿入位置より大きい値を右へずらし、最後に取り出した要素を置きます。

ループ開始時、先頭からi-1番目までが整列済みです。この範囲を保ったままi番目を挿入すると、先頭i番目までが整列済みになります。この繰返しの条件が正しさの根拠です。

挿入する注文	処理後の全体	整列済み範囲
B	1B・3A・3C・2D	先頭2件
C	1B・3A・3C・2D	先頭3件
D	1B・2D・3A・3C	先頭4件

Cを入れるとき、キーが等しいAは右へずらしません。比較を「大きい」から「大きいか等しい」へ変えると、同値の注文を追い越し、安定性が失われる場合があります。

短い実装で、空配列と重複も確かめる

python

def insertion_sort(items):
    a = list(items)
    for i in range(1, len(a)):
        item = a[i]
        j = i - 1
        while j >= 0 and a[j][0] > item[0]:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = item
    return a

このPythonコードはキーを組の最初の値とし、元の入力をコピーして返します。j>=0の判定を先に置くので、範囲外の位置を比較しません。配列長が0か1なら外側のループは実行されません。

取り出したitemを保存せずに右へずらすと、その値を上書きして失うことがあります。ソート後の値が並んでいても、入力の要素数や個数が保たれたかを別に確かめます。

マージソートは、なぜO(n log n)？

列を二つに分け、各部分を整列してから結合します。整列済みの二列の先頭を比べ、小さい方を結果へ移すので、一回の結合は要素数に比例します。

分割の段数はおよそlog₂nで、各段で合計n個程度を結合します。配列の標準的な実装では時間O(n log n)、結合用にO(n)の追加領域を使います。実装やデータ構造で領域の扱いは変わります。

分けてから、整列済みの列を結合する

1. 左を整列
2. 右を整列
3. 左の先頭を比較
4. 右の先頭を比較

例の入力を二分し、整列した左右から小さい先頭を順に選びます。

キーが等しいとき左側を先に取り出せば、左右内部の安定性と合わせて元の順序を維持できます。左右を結合しただけで自動的に安定になるのではなく、同値時の選び方も条件です。

クイックソートや選択ソートと比較する

クイックソートは基準値で分けて部分列を整列します。適切な分割なら平均的な時間はO(n log n)ですが、偏った分割が続くとO(n²)になります。一般的なその場で分割する実装は安定ではありません。

算法の例	時間の目安	追加領域・性質
挿入ソート	最良O(n)、最悪O(n²)	その場の実装ならO(1)、同値を追い越さず安定
マージソート	標準実装でO(n log n)	配列の結合領域O(n)、同値時の選択で安定
クイックソート	平均O(n log n)、最悪O(n²)	再帰の深さにも依存、通常は不安定
選択ソート	基本実装でO(n²)	追加領域O(1)、交換で同値順が変わり得る

その場で並べ替える実装でも、再帰スタックまで不要とは限りません。また、このコードの挿入ソートは入力をコピーするため、関数全体ではコピーにO(n)領域を使います。条件を付けず「メモリは常に一定」と断定しません。

計算量から、実行秒数まで分かる？

O記法は入力が大きくなったときの増え方を表します。定数や小さい項を省くため、同じO(n log n)の算法が同じ秒数で終わるとは限りません。比較の重さ、コピー、メモリ配置も影響します。

挿入ソートの逆順入力では、キー比較が1+2+…+(n-1)=n(n-1)/2回になります。8件なら28回です。整列済みの入力では各挿入で一回のキー比較をして止まり、7回です。

平均・最悪・最良のどの条件かを示して比較します。少数件やほぼ整列済みのデータでは挿入ソートが使いやすい場合もあります。一般的なO記法だけで、実測した速度の大小を決めません。

演習1：安定な期待結果

条件：入力は3A・1B・3C・2Dで、同じ優先度は受付順を守ります。

問い：正しい出力を示してください。

解答例：1B・2D・3A・3Cです。

根拠：キーを昇順にし、同じ3のAとCは元の順序を保持します。

誤答の理由：1B・2D・3C・3Aは昇順ですが安定性の要件を満たしません。

演習2：一回の挿入

条件：1B・3A・3Cまで整列済みで、次に2Dを入れます。

問い：どの要素を右へずらしますか。

解答例：3Cと3Aをずらし、1Bの後ろへ2Dを置きます。

根拠：2より大きいキーだけをずらすため、1Bはそのままです。

誤答の理由：整列済み部分をすべて移動すると、挿入位置の条件を使えていません。

演習3：同値の比較

条件：挿入条件をa[j][0]>=item[0]へ変えます。

問い：同値の注文で何が変わりますか。

解答例：後から来た注文が同値の先行注文を追い越し、安定性が失われ得ます。

根拠：同値も右へ移すため、後の要素を前に挿入します。

誤答の理由：比較回数だけの違いと説明すると、出力順への影響を見落とします。

演習4：最悪の比較回数

条件：異なるキー8件を逆順から挿入ソートします。キー同士の比較だけを数えます。

問い：比較回数はいくつですか。

解答例：8×7÷2=28回です。

根拠：各挿入で既存の1件、2件、…、7件と比較します。

誤答の理由：64回はn²をそのまま回数とした値で、実際の比較回数ではありません。

演習5：領域の条件

条件：掲載関数はa=list(items)で入力をコピーします。

問い：関数全体の追加領域をO(1)といえますか。

解答例：いえません。コピーのためO(n)の領域を使います。

根拠：挿入の作業変数が一定でも、複製した列の領域が必要です。

誤答の理由：その場の算法という性質だけで、この実装の領域を決めるとコピーを見落とします。

演習6：偏った分割

条件：クイックソートで、毎回一方が0件、他方が残り全件になる分割が続きます。

問い：平均的なO(n log n)の速度を保証できますか。

解答例：保証できません。この条件では最悪O(n²)になり得ます。

根拠：分割の深さが大きくなり、多くの要素を繰返し処理します。

誤答の理由：算法名だけで平均計算量が全入力に当てはまると判断するのは不十分です。

出典と仕様を確認する

IPA：APシラバス Ver.7.2

MIT 6.006：整列と計算量

Python公式：キー指定と安定なソート

Princeton Algorithms：クイックソートの分割と性能

並べ替えは速さだけで選べる？｜ソート・計算量・安定性と境界条件