[ソート] 基数ソート

基数ソート

基数ソート（きすうソート、英: radix sort）は、「比較によらないソート」^[1]のアルゴリズムの一つで、位取り記数法で表現可能な対象について、下の桁から順番にソートしてゆき、最後に最上位桁でソートすると、全体が順序通りに並ぶ、という手法である。
出典: フリー百科事典『ウィキペディア（Wikipedia）』

基数ソートとは、桁毎に繰り返しソートを行うことで、最終的に配列がソートされるアルゴリズムです。

ここで言う「基数」は、数学の基数 ‘Cardinal Number’ ではなく、‘Radix’ の基数です。

Nをデータの数、kを桁数として、計算量のオーダーは\(O(N \times k) \) になります。

安定ソートです。

日本語の wikipedia には、「下の桁から」とありますが、英語の wikipedia には、「右の桁から見ていく」’Least significant digit’ と「左の桁から見ていく」’Most significant digit, forward recursive’ の2つがあります。

Python で実装

3桁の整数の ‘Least signigicant digit ‘ 基数ソートを Python で記述します。

桁のソートには、計数ソートを用います。

import random

def counting_sort_digit(array, digit):
    """
    digitの位の数に基づき計数ソートを行う。
    例えば、array = [17, 72, 97, 8, 32, 15, 63, 97, 57, 60] において、
    counting_sort_digit(array, 1)は、
    [60, 72, 32, 63, 15, 17, 97, 97, 57, 8]
    counting_sort_digit(array, 10)は、
    [8, 17, 15, 32, 57, 63, 60, 72, 97, 97]
    をそれぞれ返す。
    """
    result_array = [0 for _ in array]
    counting_array = [0 for _ in range(0, 10)]
    
    for i in range(len(array)):
        index = array[i] // digit
        counting_array[index % 10] += 1
    
    for i in range(1, 10):
        counting_array[i] += counting_array[i-1]
    
    for j in range(len(array)-1, -1, -1):
        index = array[j] // digit
        result_array[counting_array[index % 10]-1] = array[j]
        counting_array[index % 10] -= 1
    
    return result_array

def radix_sort(array, radix):
    max_num = max(array)
    
    digit = 1
    while max_num // digit > 0:
        array = counting_sort_digit(array, digit)
        digit *= radix

    return array


if __name__ == '__main__':
    random.seed(1)
    array = [random.randrange(1000) for i in range(20)]
    print('未ソート', array)
    # 未ソート [137, 582, 867, 821, 782, 64, 261, 120, 507, 779, 460, 
    #          483, 667, 388, 807, 214, 96, 499, 29, 914]
    sorted_array = radix_sort(array, 10)
    print('ソート済み', sorted_array) 
    # ソート済み [29, 64, 96, 120, 137, 214, 261, 388, 460, 483, 499, 
    #           507, 582, 667, 779, 782, 807, 821, 867, 914]