比較しないソートの作成 in Ruby DouKaku?

ソート対象のデータ同士で一切比較などを行わずにソートし、ソート結果を出力するプログラムを作成してください。条件は以下の通り。
・最低値・最大値・個数・並び替え対象の4つを引数として受け取る
・最大値と最低値はあくまで取りうる可能性であり、実際に出現することを保障するものではない。
・同値が複数出現することがある。
・入出力方法及びフォーマットは自由、関数として実装し引数に渡す形でも良い。
・小数点以下の数値が渡されることはないが、負の数は渡される可能性がある。
・最大値や最低値を元に算出した数値との比較は使用しても問題ありません。
・出来るだけ多様な条件のデータをソートできるアルゴリズムを使ってください(データが多少多いときや一定の並び順だとソート失敗するものはダメ)
・昇順降順はどちらでもかまいません

以下サンプル入出力
>>入力
-1 10 10
-1 9 4 8 9 6 3 9 5 2
>>出力
-1 2 3 4 5 6 8 9 9 9

バケットソートって知らなかったのでやってみました。

でもこの実装だと要素作り直しててソートつーのかなんだか。

def bucket_sort(ary, min, max);
  bucket = Array.new(max-min+1, 0)
  ary.each{|num|
    bucket[num-min]+=1
  }

  ret = []
  bucket.each_with_index{|count, index|
    ret += [index+min] * count
  }
  ret
end

ary = [-1,9,4,8,9,6,3,9,5,2]
p bucket_sort(ary, ary.min, ary.max)

こんなのでもいいのかな. マッチしたオブジェクトを格納するようなメソッドってなかったっけ.

def main(min, max, num, ary)
  [*min..max].map{|i| ary.select{|j| i == j}}.flatten
end
min, max, num = 1, 10, 10
p ary = num.times.map{(rand*(max-min)).round+min}
p main(min, max, num, ary)

DouKaku?

比較しないソートの作成

Posted feedbacks - Ruby

Index

Feed

Other

Link

Pathtraq