比較ソートと非比較ソート
比較ソートとは、コードに以下のような部分を含む、お互いの要素を比較することによって行われるソートです。
if array[i] < array[j]:
swap(array, i, j)
比較ソートは比較によって行われる以上、計算量の下界が\( \Omega ( N \log N) \) になります。
非比較ソートは、上のような比較・交換によらず行われるソートの総称で、計算量の下界を比較ソートより良くできる可能性があります。
バケットソート
非比較ソートの一つにバケットソートと呼ばれるソートがあります。
バケットソート（英: bucket sort）は、ソートのアルゴリズムの一つ。バケツソート、ビンソート（英: bin sort）などともいう。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
バケットソートとは、ソートしたい値のバケツを用意しておき、値をバケツに振り分けることでソートを行うアルゴリズムです。
用意することのできるバケツの個数により、いくつかの段階に分けてソートが行われます。
[29, 25. 3, 49, 9, 37, 21, 43] を2段階でソートすると以下のようになります。
まずは、10の桁の数によって、以下のようにバケツに振り分けます。
次にそれぞれのバケツ内でソートを行います。
最終的に全ての数字がソートされます。
疑似コードで表すと以下のようになります。
function bucketSort(array, k) is
buckets # バケツとして使われる k 個のリスト
M # 配列の中の最大値
for i = 1 to length(array) do
# floor(array [i] × (k / M))による値に応じてバケツに振り分ける
insert array[i] into buckets[floor(array [i] × (k / M))]
for i = 1 to k do
# nextSort でバケツ内のソートを行う
# バケットソート以外のソートを用いても良い
nextSort(buckets[i])
# 全てのバケツを結合するとソートされたリストになる
return the concatenation of buckets[1], ...., buckets[k]
計数ソート
バケットソートの中で、最初に対象となるデータを走査して値ごとの出現回数を数えておき、出現回数に応じてひとつの配列の中を値ごとに分割してバケツとして使う方法は、計数ソートと呼ばれます。
In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct key value, and using arithmetic on those counts to determine the positions of each key value in the output sequence.
From Wikipedia, the free encyclopedia
「計数ソートは、小さな整数をキーとして使うことで、ソートを行うアルゴリズムです。 つまり、整数ソートのアルゴリズムです。それぞれ異なるキーを持つオブジェクトの数を数えて、それらの数の和により、出力配列内の各キーの位置を決めます」
計算量はキーの数を\(K\)として\( O ( N + K) \) になります。
計数ソートは以下のような流れで行われます。
まず、整列用に k 個の要素を持つ配列をゼロで初期化します。ソートしたい配列を走査して、その値をインデックスとして整列用の配列を 1 増やします。次に整列用の配列を走査してその数値の数だけインデックスを出力すると、ソートされたものになります。
Python で実装
Python で0から9の整数をソートする計数ソートを実装します。
計数ソートの本質からはずれますが、出力用配列の作り方がちょっとわかりづらいです。
import random
def counting_sort(array, k):
# 結果を格納する配列
result_array = [-1 for _ in array]
# 要素の数を数える配列
counting_array = [0 for _ in range(k)]
# countirn_array[i]は、i と等しい要素の数を表す。
# array [1, 4, 0, 2, 0] だとすると、countirn_array [2, 1, 1, 0, 1]
for i in range(len(array)):
counting_array[array[i]] += 1
# counting_array[i]は、i 以下になる要素の数を表す。
# countirn_array [2, 3, 4, 4, 5]
for i in range(1, k):
counting_array[i] += counting_array[i-1]
# 後ろから配列を見ていくことで、安定ソートとなる。
# array [1, 4, 0, 2, 0] で countirn_array [2, 3, 4, 4, 5]
# array で 0 は 2個 あるので、result_array[-1, 0, -1, -1, -1] となる。
# 次の 0 を見る時は、これより前に入り、安定ソートになる。
for j in range(len(array)-1, -1, -1):
result_array[counting_array[array[j]]-1] = array[j]
counting_array[array[j]] -= 1
return result_array
if __name__ == '__main__':
random.seed(1)
array = [random.randrange(10) for i in range(20)]
print('未ソート', array)
# 未ソート [2, 9, 1, 4, 1, 7, 7, 7, 6, 3, 1, 7, 0, 6, 6, 9, 0, 7, 4, 3]
sorted_array = counting_sort(array, 10)
print('ソート済み', sorted_array)
# ソート済み [0, 0, 1, 1, 1, 2, 3, 3, 4, 4, 6, 6, 6, 7, 7, 7, 7, 7, 9, 9]
