🐌

実用度の低いソートアルゴリズム

2023/08/12に公開

Ruby

ボゴソート - 運を天に任せる

https://ja.wikipedia.org/wiki/ボゴソート

def sort(a)
  a.tap do |a|
    until a.each_cons(2).all? { |a, b| a <= b }
      a.shuffle!
    end
  end
end

a = 10.times.collect { rand(10) }  # => [8, 2, 5, 6, 5, 1, 3, 5, 2, 2]
sort(a)                            # => [1, 2, 2, 2, 3, 5, 5, 5, 6, 8]

ググると「シャッフルしてから確認する」コードを紹介している記事がいくつもでてくるのはいただけない。野暮なことを言うと順序が逆で「ソートされていなければシャッフルする」としないといけない。そうしないと天和を見逃してしまう。

重複なし要素数Nと時間の関係

N	時間	シャッフル回数
0	0秒	0
1	0秒	0
2	0秒	0
3	0秒	1
4	0秒	2
5	0秒	357
6	0秒	629
7	0秒	2510
8	0秒	36579
9	0秒	678770
10	1秒	1979481
11	11秒	15717718
12	1分11秒	99328631
13	8時間4分42秒	15597635494

13 からが厳しい。

ストゥージソート - 見掛け倒しな遅さを発揮？

https://ja.wikipedia.org/wiki/ストゥージソート

def sort(a, l = 0, r = a.size.pred)
  if a[r] < a[l]                # 最後 > 先頭 なら
    a[l], a[r] = a[r], a[l]     # 入れ替え
  end
  n = r - l + 1                 # 部分列のサイズ
  if n < 3
    return
  end
  t = n / 3                     # t は全体の 1/3
  sort(a, l, r - t)             # 先頭 2/3 をソート
  sort(a, l + t, r)             # 末尾 2/3 をソート
  sort(a, l, r - t)             # 先頭 2/3 をソート (再度)
  a
end

a = 10.times.collect { rand(10) }  # => [2, 9, 4, 5, 3, 3, 6, 1, 1, 0]
sort(a)                            # => [0, 1, 1, 2, 3, 3, 4, 5, 6, 9]

遅いだけだとあまりネタという感じがしないのだけど速そうなことをしてそうに見えて実はめちゃくちゃ遅いというところが評価ポイントなのかもしれない。

スリープソート - 値に比例して待つ

def sort(a)
  [].tap do |values|
    a.collect { |e|
      Thread.start do
        sleep e * 0.001
        values << e
      end
    }.each(&:join)
  end
end

t = Time.now
a = 10.times.collect { rand(10) }  # => [7, 9, 9, 0, 6, 3, 7, 5, 8, 8]
sort(a)                            # => [0, 3, 5, 6, 7, 7, 8, 8, 9, 9]
Time.now - t                       # => 0.011513

値をそのまま秒換算の sleep に渡すとかなり待たされるので単位を小さくした方がいい。ただ、小さくしすぎると順番が少しずれたりする。

単なる配列要素のソートには使いづらいが、各スレッドが持つ情報を元にスレッド間の優先度を調整するアイデアは Puma の高速化に寄与したらしい。

ビーズソート - 速度は環境次第

縦横にビーズを並べて垂直落下させると半分の山の形ができるので頂上から幅を数える方法。Wikipedia の図がわかりやすい。

def sort(a)
  width = a.max                 # 横幅
  height = a.size               # 縦幅

  field = {}                    # 二次元領域

  # ビーズを配置する
  a.each.with_index do |count, y|
    count.times do |x|
      field[[x, y]] = true
    end
  end

  # 落下させる
  loop do
    fall_down = false
    width.times.each do |x|
      (height - 2).downto(0) do |y| # 重ならないように地面に近い方から
        from = [x, y]               # ここに
        if field[from]              # ビーズがあって
          to = [x, y.next]          # 移動先が
          if !field[to]             # 空いていたら
            field[to] = field[from] # 移動する
            field.delete(from)
            fall_down = true
          end
        end
      end
    end
    # すべてのビーズが接着したら終わる
    unless fall_down
      break
    end
  end

  # 上の層からビーズを数える
  height.times.collect do |y|
    width.times.count { |x| field[[x, y]] }
  end
end

a = 10.times.collect { rand(10) }  # => [1, 9, 9, 8, 9, 4, 8, 7, 7, 2]
sort(a)                            # => [1, 2, 4, 7, 7, 8, 8, 9, 9, 9]

本来は特殊な装置などを用意して行う (とのこと)
物理的な環境がビーズの落下速度に影響して実行速度が変わる
負の値を含むソートはできない (ということになっている)
- ビーズの個数を現実的に表せないため