分布数え上げソート : アルゴリズム

分布数え上げソートはキーの重複に対応しているといいました。キーが重複しているのは 3 です。整列後のふたつの 3 の位置(配列のインデックス)は 「Y - X」 と 「Y - 1」 で計算できます。この例だと「3 - 2 = 1」と「3 - 1 = 2」になります。 実際のプログラミングでは重複したキーの位置の計算は、作業用配列Bにコピーする時に(手順4で)配列Aの後ろから前へコピーしていくことで簡単に実装できます。 図解 特徴 バケットソートと同じくソート対象のデータがとりうる値の範囲をあらかじめわかっていなければなりません。作業領域もキーの個数を数えるための領域と結果を格納する領域が必要になります。あまりに大きな範囲のデータを取り扱うには RAM などに限度があるので物理的に不可能になります。しかし大きな作業領域と引き換えにデータの大小を比較しなくてよいので高速な整列処理を実現できます

[kiyo_hiko]

「作業領域と引き換えにデータの大小を比較しなくてよい」