👌

小数のリストをバケットソートする

1 min read

問題

次のようなリストがあるとします: 〈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

参考