分布数え上げソート（Pythonによるアルゴリズムとデータ構造）

本記事は、ソフトバンクパブリッシングから発行されている「定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)」を参考にPythonでアルゴリズムとデータ構造について学習していきます。

今回は、比較によらない整列である分布数え上げソート（Distribution Counting Sort）について学んでいきます。

分布数え上げソートとは
Pythonで分布数え上げソートを実装してみる
動作確認
参考書籍

分布数え上げソートとは

前回は比較によらない整列アルゴリズムであるビンソートについて学びました。

今回の分布数え上げソート（Distribution Counting Sort）もこの比較によらない整列アルゴリズムになります。

ビンソートでは、以下の2つの欠点がありました。

値の重複は認められない
値はある範囲に収まる整数でなければならない

上記の2は分布数え上げソートにもある欠点ですが、1に関しては改善されています。

原理としては、入力するデータの値の範囲だけ配列を用意し、入力する値をインデックスとする点はビンソートと同じですが、分布数え上げソートでは累積度数分布というものを作成し、出現頻度を数え上げます。

例えば0～4までの範囲の値をとるデータの並びとして、「2, 2, 1, 3」があった場合、分布数え上げソートの配列は以下のようになります。

分布数え上げソートは、ビンソートと同じく入力するデータの値のとる範囲分の配列が必要となるため、データの個数を $n$ 、データの範囲を $m$ とすると計算量は $O(n+m)$ となります。

$m$ が $n$ に比べて十分に大きくなければ、計算量は $O(n)$ で済みます。

なお、分布数え上げソートは安定な整列アルゴリズム（データの位置関係が保存される）になります。

Pythonで分布数え上げソートを実装してみる

それでは、Pythonで分布数え上げソートを実装してみます。

# distribution_counting_sort.py
import time
import pickle

size = 20000
count = [0 for _ in range(size+1)]

def distribution_counting_sort(lst):
    length = len(lst)
    sorted_list = [None for _ in range(length)]
    for i in range(length):
        count[lst[i]] += 1
    for i in range(size):
        count[i+1] += count[i]
    for i in range(length-1, -1, -1):
        count[lst[i]] -= 1
        sorted_list[count[lst[i]]] = lst[i]
    return sorted_list

with open('sample_data.pkl', 'rb') as f:
    lst = pickle.load(f)


start = time.time()
distribution_counting_sort(lst)
print("elapsed {} sec".format(time.time() - start))

動作確認

それでは上記で作成したスクリプトを実行してみます。

事前に1~20,000までの値からランダムに20,000個生成したリストをpickleデータとして保存しておき、これをロードします。

自環境で実行した結果を以下にまとめます。

**データ20,000個を整列した結果一覧**
アルゴリズム名	所要時間（秒）
Python 組込みメソッド（sort()）	0.015
Bubble Sort	72.979
Selection Sort	17.747
Insertion Sort	41.236
Shell Sort	0.253
Quick Sort	0.084
Merge Sort(List)	0.168
Merge Sort(Linked List)	0.092
Heap Sort	0.233
Distribution Counting Sort	0.017