Rubyでボゴソート

なんとなくボゴソートを書いてみました。

ボゴソート

ボゴソートは配列の要素がソートされるまで、配列の要素のシャッフルを繰り返すアルゴリズムです。計算量がかなり膨大。( O(n*n!) )

def sort_checker(array)
  for i in 0..(array.size-2)
    return false if array[i] > array[i+1]
  end 
  return true
end

(2).upto(10) do |num|
  start_t = Time.now

  array = (1..num).to_a.shuffle

  until sort_checker(array)
    array.shuffle!
  end 

  end_t = Time.now 

  puts "Array size #{num} : #{end_t - start_t}sec"
end

Array size 2 : 1.4e-05sec
Array size 3 : 6.0e-06sec
Array size 4 : 3.0e-06sec
Array size 5 : 7.1e-05sec
Array size 6 : 0.000623sec
Array size 7 : 0.0009sec
Array size 8 : 0.012798sec
Array size 9 : 0.254477sec
Array size 10 : 0.466737sec

10要素までならなんとか1秒以内で終わりますが、それ以降の要素数では終わる気配がありませんでした。