👌
小数のリストをバケットソートする
問題
次のようなリストがあるとします： 〈0.82、0.31、0.44、0.17、0.53〉
バケットソートでリストに並べ替えます。
まず、districution直後にバケット内のキーの状態一覧を書いてください。 （一部のバケットが空のままの場合は、文字Eを入力します。要素は適切なバケットのリストの先頭に挿入されます。）
- bucket 0: ?
- bucket 1: ?
- bucket 2: ?
- bucket 3: ?
- bucket 4: ?
また、最終的な結果までのプロセスも書いてください。
解き方
(リストの値 x リストの個数)の整数部分の値をもつバケットにリストの要素を割り振ります。
例えば、0.82であれば
0.82 x 5 = 4.1
と計算できて、4.1の整数部分は4であることからバケット4にいれます。
リストのすべての要素で計算します
-
0.31 x 5 = 1.55 -> 1
-
0.44 x 5 = 2.2 -> 2
-
0.17 x 5 = 0.85 -> 0
-
0.53 x 5 = 2.65 -> 2
-
bucket 0: 0.17
-
bucket 1: 0.31
-
bucket 2: 0.53,0.33
-
bucket 3: Empty
-
bucket 4: 0.82
バケット2には要素が2つあるので、それら2つでソーティングを行います。
0.33,0.53という順番になります。
したがってバケットは最終的に以下のようになります。
- bucket 0: 0.17
- bucket 1: 0.31
- bucket 2: 0.33,0.53
- bucket 3: Empty
- bucket 4: 0.82
bucket0から順に取り出し並び替えるとソート完了です。
0.15,0.31,0.33,0.53,0.82
Discussion