基数ソート（Pythonによるアルゴリズムとデータ構造）

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

今回は、比較によらない整列である基数ソート（Radix Sort）について学んでいきます。

基数ソートとは
Pythonで基数ソートを実装してみる
動作確認
参考書籍

基数ソートとは

前回までで学んだ整列アルゴリズムのビンソートと分布数え上げソートでは、値の範囲（キーの種類）が多いと、 $O(n)$ の計算量とはかけ離れたものとなってしまう欠点がありました。

今回の基数ソート（Radix Sort）では、これらの欠点をカバーすることができます。

基数ソートは古くからあるアルゴリズムで、かつてはパンチカードで使用されていたようです。

基数は10進数など、どれでも良いのですが、コンピュータは2進数での処理が得意なのでここでは2進数で考えていきます。

例えばデータ「6, 4, 3, 2」を整列させるために、2ビット単位で分割して整列をさせた場合、以下のfig1のようになります。

実際には前回で学んだ分布数え上げソートを組み合わせて、分割したビットをインデックスとして値を格納していきます。

計算量としては、キーの種類はキー長を基にし、データ数（ $n$ ）に比べると十分に小さいと言えます。

またキーを $a$ 個に分割した場合は、分布数え上げソートを $a$ 回実行するため、計算量は $O(an)$ となりますが、 $a$ も十分に小さいため、最終的には $O(n)$ の計算量となります。

Pythonで基数ソートを実装してみる

それでは、Pythonで基数ソートを実装してみます。

# radix_sort.py
import time
import pickle

mask = 0xff
size = 255

def radix_sort(lst):
    length = len(lst)
    tmp = [None for _ in range(length)]
    for bit in range(0, 32, 8):
        count = [0 for _ in range(size+1)]
        for i in range(length):
            count[(lst[i]>>bit) & mask] += 1
        for i in range(size):
            count[i+1] += count[i]
        for i in range(length-1, -1, -1):
            count[(lst[i]>>bit) & mask] -= 1
            tmp[count[(lst[i]>>bit) & mask]] = lst[i]
        for i in range(length):
            lst[i] = tmp[i]

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

start = time.time()
radix_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
Radix Sort	0.078