[ネタ？]Rubyでボゴソートを実装

ボゴソートとは

ボゴソート - Wikipedia

簡単に説明すると、トランプを順に並べたいとき

1. トランプの束を放り投げる。
2. 無作為に拾う。
3. 見事ソートできていれば終了。できていなければ、1に戻る。

トランプを例に出すと絶対ありえないようなソートの仕方ですが、このソートは無限の猿定理の別例のようなもので、このソート法に不可能はありません。クイックソートより早いときだってある

コード

再帰を用いました。コード自体は割とすっきりしたかな。実行結果ではソート結果、かかった時間を簡易的ですが表示しています。

bogo.rb

def bogo(array,ans,time)
# 第一引数：ソートしたい配列
# 第二引数：ソート結果の参照用
# 第三引数：開始時間

  sfarray = array.shuffle #ランダムで配列の要素を入れ替え

  if sfarray.eql?(ans)
    p sfarray #ソート結果
    ft = Time.now #ソート終了時の時刻
    puts ft - time #処理時間を算出
  else
    bogo(sfarray,ans,time) #シャッフル後のものをもう一度
  end

end

st = Time.now #開始時刻

puts "配列の要素を入力（スペース区切り）"
*ary = gets.split(" ").map!{|n| n.to_i}
ansary = ary.sort #正しい結果
bogo(ary,ansary,st)

実行結果

$ ruby bogo.rb
配列の要素を入力（スペース区切り）
56 34 9 94 27 11 2
[2, 9, 11, 27, 34, 56, 94]
32.033958

改善点

(追記：@scivolaさんによるloopを用いた実装例がこの問題を全て解決してくれました。ありがとうございます！)

• 配列の要素数が8以上だとstack level too deep (SystemStackError)が発生します。再帰を用いたのが原因です。まあ運任せなので確かになあと言う感じです。どうにか解決したい…。

• 処理時間周りをもっとなんとかしたい。

• いつかクイックソートも実装してボゴソートの方が早いぞ、な瞬間を見たい

終わりに

勉強したくなさすぎて現実逃避した結果、こんなものを作ってみました。やっつけな部分が多々ありますので、改善箇所などありましたらぜひコメントよろしくお願いします。