1. ホーム
少しでも分かりやすく伝えたい基数ソート

皆さんこんにちは！！
今回は基数ソートについて説明していきたいと思います！

基数とは

「基数ソート」なんて言われるだけあって「基数」というキーワードが重要になってきます。
例えば、普段用いる10進数がありますね。10進数は、桁が一つ増えると値が10倍になりますね。

基数は1桁上がるまでにある数のことで10進数ならば0~9までの数字が当てはまり、合計した「10」が10進数の基数となります。

基数ソートとは

本題の基数ソートについて説明していきます。
基数ソートは下の桁からソートを行っていくソートになります。
10進数の基数ソートなら、

1の位のソート
↓
10の位のソート
↓
100の位のソート…

のように桁を増やしながらソートしていく方法になります。
「基数ソートのやり方」にてソートの詳しい方法について説明していきます。

基数ソートのやり方

では基数ソートのソートの手順について説明していきます！

1.データを用意する

まずは、データを用意します。

今回は上のようなデータを用意しました。このデータを基にソートを行っていきます！

2. 1の位のソートを行う

まず1の位のソートを行っていきます。
1の位のみのソートを行うと以下の通りになります。(左から昇順で並べています)

3.一つ上の桁のソートを行う

1の位のソートが済んだら次は1つ上の10の位のソートを行います。
今回も1の位の時と同様にソートを行います。

10の位のソートを行うと以下の通りになります。

少し並んできましたね。
これと同じ作業を上の桁がある限り続けていきます。

100の位なら以下の通りになります。

これでソートが完了しました。

他のソートとの比較

基数ソートの時間計算量はO(kn)となっています。
※kは桁数、nは入力サイズ
桁数が含まれるソートは中々珍しいですが、実際に他のソートと計算時間を比較してみます。
例として、5桁の入力サイズが10のデータの集まりをソートを行っていくと、

代表的なソートをいくつか挙げましたが、データ数より桁数が多くない限りは選択ソート等よりかは早そうです。

まとめ

1の位、10の位と順番にソートしていくソートの方法です！
桁数がソート時間に含まれる珍しいソートですので、とっつきづらいと感じる方もいるかもしれませんが、方法はかなりシンプルですのでぜひ試してみてください！