読者です 読者をやめる 読者になる 読者になる

亀岡的プログラマ日記

京都のベッドタウン、亀岡よりだらだらとお送りいたします。

バケツソート、ですか。

凄い既視感がある…このネタ。気のせいかなあ・・・

とはいえ、シンプルすぎて楽しくなるバケツソート。@dankogaiさんの実装は大体わかったんだけれど、眠くなってきたのでとりあえず超簡単なのをね。

一応解説。バケツソートってのは

  1. ソートしたいものに適当に番号を振っておく
  2. 番号がついたバケツを用意する
  3. ソートしたいものの番号がついたバケツにそれを放り込む
  4. 必要があればバケツの中身を同じやり方でソートする
  5. 番号順にバケツの中身をぶちまける

プログラミング言語で言うところの番号がついたバケツってのは配列のことです。つまり、ソートしたい数字を、その数字がインデックスになっている配列の中身に放り込んでいく、ってことです。

まぁ、百聞一見。

 int[] bucket = new int[input.Max() + 1];
 foreach(var ele in input)
 {
      bucket[ele]++;
}

んね。個々は超乱暴に、入力された数列の最大値の大きさの配列を確保して、あとはそのインデックスの場所に放り込んでいくわけです。

超楽ちんで、且つ早い。ただし、メモリをがっつり食う。でもこんくらい大丈夫でしょ、最近のPC向けなら。