基数ソート

基数ソートはソートアルゴリズムの中の変わり種です。2つの値のどちらが大きいかを一度も問いません。数値を1桁ずつ読み、10個のバケットを使って1桁ずつ並べ替えます。この考え方はコンピューターより古く、パンチカードの分類機がこの方法で動いていました。

リストの棒の下に0〜9のラベルが付いた10個のバケットが並び、値が最後の桁のバケットに落ちていく様子
リストの棒の下に0〜9のラベルが付いた10個のバケットが並び、値が最後の桁のバケットに落ちていく様子

考え方

数値を一の位だけで並べ替えます。次に十の位で並べ替えますが、十の位が同じ数値は最初のパスでついた順序を保つようにします。百の位でも同じようにします。最後のパスの後、リストは整列しています。百の位がまず順序を決め、百の位が同じものはすでに十の位の順に、そこも同じものは一の位の順に並んでいるからです。

バケットを使った1パス

各パスでは0〜9の数字ごとに1つ、計10個のバケットを使います。リストを最初から最後までたどり、各数値をその数字のバケットの、すでに入っている数値の後ろに移します。次に、バケット0から順にバケットを空けてリストに戻します。リストの順に数値を動かし、バケットの末尾に追加することで、パスが安定になります。このアプリでは先に数字ごとの個数を数えるので、バケットを1行に並べ、それぞれを直前のバケットのすぐ後ろから始められます。これが1つの桁での計数ソートです。

例

170, 45, 75, 90, 802, 24, 2, 66 を例にとります。一の位で:170, 90, 802, 2, 24, 45, 75, 66。十の位で:802, 2, 24, 45, 66, 170, 75, 90。十の位がどちらも0の802と2は、最初のパスの順序を保っている点に注目してください。百の位で:2, 24, 45, 66, 75, 90, 170, 802。8個の数値に3パスで、読んだ桁は24、移動は48回、比較は1回もありません。

どのくらい速い?

各パスですべての数値の1桁を読み、すべての数値を2回移動するので、d桁の数値n個では作業量が n · d に比例して増えます。比較ソートは最悪の場合に少なくとも約 n log₂ n 回の比較が必要です。n! 通りの並びを、はい・いいえで答える質問1つずつで見分けなければならないからです。基数ソートはそうした質問をしないので、この制約を受けません。1,000未満の数値100万個のように短いキーが多い場合、3パスは比較ソートに必要な約2000万回の比較よりはるかに少ない作業です。キーが長い場合や値が少ない場合は、この利点はなくなります。

LSDとMSD、そして歴史

ここで示すのは最下位桁(LSD)から始める方式です。逆に最上位桁から始める方式(MSD)では、最初の桁でリストをバケットに分け、各バケットを別々に並べ替えます。長さの異なる文字列に向いています。基数ソートの起源は、1890年の米国国勢調査に使われたHerman Hollerithの集計機に続いて登場したパンチカード分類機にさかのぼります。分類機はある列の穴の位置で各カードを10個のポケットのどれかに落とし、オペレーターは最後の列から始めて、列ごとにカードの束を1回ずつ通しました。

コンピュータ歴史博物館のホレリス穿孔カード集計機。1890年の米国国勢調査で使われた種類。操作者はデッキを列ごとに一度ソーターに通し、これが基数ソートの祖先である。
コンピュータ歴史博物館のホレリス穿孔カード集計機。1890年の米国国勢調査で使われた種類。操作者はデッキを列ごとに一度ソーターに通し、これが基数ソートの祖先である。

試してみよう

アプリを開いて「ステップ」を押してください。各パスではまず桁を数え、リストの下の行に0〜9のバケットの範囲が決まります。次に数値が1つずつバケットに落ち、使用中のバケットが強調表示され、それから書き戻されます。上の例のように999までの数値を自分で入力すると、3つのパスすべてを見られます。

よくある質問

基数ソートの時間計算量は?

固定の基数でd桁のキーn個なら O(n · d) で、これに各パスのバケットのコストが加わります。バケットを置くバッファのために O(n) の追加メモリが必要です。

基数ソートは安定ですか?

LSD基数ソートは安定でなければなりません。どのパスでも同じ数字を持つ値が入ってきた順序を保つからこそ成り立つ方式です。そのため最終結果も安定です。

基数ソートで負の数や小数を扱えますか?

そのままでは扱えませんが、工夫すれば扱えます。負の数をずらしてすべて正にするか、負の数だけ別に並べ替えて逆順にします。浮動小数点数は、少し変換すればビットパターンで並べ替えられます。

なぜ10進数を使うのですか?

わかりやすいからです。コンピューターではふつう8ビットか16ビットずつ並べ替えるので、32ビットの数値は4パスか2パスで、バケットは256個か65,536個になります。

試してみますか?

ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。

基数ソートを試す