整列の安定性と計数ソート
同じキーの順序を保つ条件と、値域を利用して並べる方法を学びます。
説明
安定な整列は、比較キーが等しい要素の元の順序を保ちます。値だけの配列では同じ数を見分けられないため、番号や名前を付けて確認します。計数ソートは小さな整数の値域を利用し、各値の出現回数から並びを作る方法です。
番号付きデータをキーだけで整列し、選択ソートの交換で同じキーの順序が変わる例を調べます。その後、0から3の度数表を作り、整数列と番号付きデータを再構成します。値域が広い場合に必要な領域も計算します。
1同じキーを番号で識別
データを(点数, 名前)で表します。点数だけで整列すると、点数2のA・C・Dの受付順が維持されます。
records = [(2, 'A'), (1, 'B'), (2, 'C'), (2, 'D')]点数と識別名; stable = sorted(records, key=lambda row: row[0])点数だけで整列; stable元の同点順を保持結果はB・A・C・Dです。Pythonのsortedは安定なため、同じ点数2のA・C・Dは元の順序です。名前を比較キーに含めた結果とは意味が違います。
2安定でない交換の例
2A・2B・1Cから最小値1Cを先頭へ交換します。交換の影響で同じ点数2の順序が変わります。
selected = [(2, 'A'), (2, 'B'), (1, 'C')]同点のA・Bを用意; selected[0], selected[2] = selected[2], selected[0]最小値と先頭を交換; selected同点順が逆転した結果結果は1C・2B・2Aです。点数としては昇順ですが、AとBの順序が逆転しました。整列の正しさと安定性は別に確かめる必要があります。
3小さい値域の度数
整数0から3だけを扱います。各値の個数を配列の対応する位置へ記録します。
values = [3, 1, 2, 1, 0, 3, 1]値域0〜3の入力; counts = [values.count(value) for value in range(4)]各値の個数; list(enumerate(counts))値と度数0は1個、1は3個、2は1個、3は2個です。このコマンドは度数の意味を示すためcountを値ごとに呼んでいます。入力を1回走査して度数を増やす実装は次で作ります。
4入力一回の走査で数える
度数表を0で初期化し、各値の位置を1増やします。入力長nと値域幅kに対して、初期化と走査は合計でn+kに比例します。
def frequencies(values, width):入力と値域幅
result = [0] * width度数表を初期化
for value in values:入力を一回走査
result[value] += 1その値の度数を加算
return result度数表を返す値を添字に使うため、この関数は0以上width未満という条件で使います。負数や値域外をそのまま受け入れると、別の添字を参照したり範囲外になったりします。
5度数から昇順を再構成
小さい値から、その個数だけ出力します。元データが整数だけなら、度数表から同じ多重集合を再現できます。
counts = frequencies(values, 4)一回の走査で度数を取得; ordered = [value for value, count in enumerate(counts) for _ in range(count)]各値を度数分出力; counts, ordered, ordered == sorted(values)度数と結果の照合0・1・1・1・2・3・3となります。値の個数は保存されていますが、元の各1に名前が付いていた場合、その名前は度数だけでは復元できません。
6番号付きデータの開始位置
キー0・1・2のレコードを安定に並べます。度数の累積和から各キーが始まる出力位置を作ります。
tagged = [(2, 'A'), (1, 'B'), (2, 'C'), (0, 'D'), (1, 'E')]名前付き入力; counts = frequencies([row[0] for row in tagged], 3)キーの度数; starts = [sum(counts[:i]) for i in range(3)]各キーの開始位置; counts, starts度数と開始位置度数は1・2・2なので、開始位置は0・1・3です。キー1の2個は添字1と2、キー2は3と4へ入ります。
7入力順に空き位置へ置く
入力を先頭から走査し、各キーの次の空き位置へ置いて、その位置を1進めます。同じキーは受付順に配置されます。
def place(records, positions):レコードと開始位置
out = [None] * len(records)出力領域
next_slot = positions.copy()次の空き位置
for row in records:元の順に走査
out[next_slot[row[0]]] = rowキーの空き位置へ配置
next_slot[row[0]] += 1そのキーの位置を進める
return out整列済みレコードpositionsをコピーするので、開始位置の表を保持できます。各レコードを一度ずつ置く処理です。前の段階の開始位置計算も、一般には累積和を一回で更新すれば値域幅に比例する時間で済みます。
8同点の並び順と値域によるメモリ使用量
配置結果を表示し、巨大な値域の度数表に必要な枠数を計算します。巨大な表そのものは作りません。
place(tagged, starts)安定な配置結果, len(values)入力の個数, (10**9 - 0 + 1)広い値域の枠数結果はD・B・E・A・Cです。キー1ではB→E、キー2ではA→Cの順が保たれます。一方、値が0から10億までなら度数表は10億1枠です。入力が7個でも値域全体の領域を使うため、小さい値域という条件が重要になります。
まとめ
安定性は比較キーが等しい要素の元の順序を保つ性質です。識別名を残して確認します。
計数ソートは値域に応じた度数表を使い、入力長と値域幅の両方が費用に関わります。
番号付きデータでは、度数だけでなく開始位置と入力順を使って安定に配置できます。
操作履歴と解説を振り返れます。
Python 3
records = [(2, 'A'), (1, 'B'), (2, 'C'), (2, 'D')]; stable = sorted(records, key=lambda row: row[0]); stable[(1, 'B'), (2, 'A'), (2, 'C'), (2, 'D')]
selected = [(2, 'A'), (2, 'B'), (1, 'C')]; selected[0], selected[2] = selected[2], selected[0]; selected[(1, 'C'), (2, 'B'), (2, 'A')]
values = [3, 1, 2, 1, 0, 3, 1]; counts = [values.count(value) for value in range(4)]; list(enumerate(counts))[(0, 1), (1, 3), (2, 1), (3, 2)]
def frequencies(values, width):
result = [0] * width
for value in values:
result[value] += 1
return resultcounts = frequencies(values, 4); ordered = [value for value, count in enumerate(counts) for _ in range(count)]; counts, ordered, ordered == sorted(values)([1, 3, 1, 2], [0, 1, 1, 1, 2, 3, 3], True)
tagged = [(2, 'A'), (1, 'B'), (2, 'C'), (0, 'D'), (1, 'E')]; counts = frequencies([row[0] for row in tagged], 3); starts = [sum(counts[:i]) for i in range(3)]; counts, starts([1, 2, 2], [0, 1, 3])
def place(records, positions):
out = [None] * len(records)
next_slot = positions.copy()
for row in records:
out[next_slot[row[0]]] = row
next_slot[row[0]] += 1
return outplace(tagged, starts), len(values), (10**9 - 0 + 1)([(0, 'D'), (1, 'B'), (1, 'E'), (2, 'A'), (2, 'C')], 7, 1000000001)
演習完了