ナポレオンソート～銃口ソートから発想を得たO(1)のソート～

銃口ソートからソートの哲学を感じた。

元記事は、ソートのテストコードに食わせてTrueが返却されればよいというのが銃口である。銃口に感じる一因に、ソート後のオブジェクトのクラス(挙動)が変わる点もあげられる。

また、銃口ソートは$O(N)$である。
$O(1)$ソートを実現したいが、もちろん全てを粛清はしたくない。

ソートの法則(銃口ソートとほぼ同じ)

i < j の場合

arr[i] <= arr[j]

かつ、

i > j の場合

arr[i] >= arr[j]

が成り立てばいいのだろう？

Rubyの世界で革命を起こす

Rubyの世界の(破壊的)ソートを$O(1)$にしてみせよう。

revolution_sort.rb

class Affected
  include Comparable

  def initialize org, revolution_number
    @revolution_number = revolution_number
    @org = org
  end

  def <=> o
    revolution_number <=> o.revolution_number;
  end

  def method_missing method, *args
    @org.__send__ method, *args
  end

  protected

  def revolution_number
    @revolution_number
  end
  
end

class Array
  def sort! # sort!をO(1)にオーバライド
    @revolution = true
    self
  end

  alias :__private_get :[]

  def [] i
    if @revolution
      Affected.new __private_get(i), i
    else
      __private_get i
    end
  end
end

a = [2,1,3]
puts a[0] <= a[1] # => false
puts a[0] >= a[1] # => true
puts a[1] <= a[2] # => true
puts a[1] >= a[2] # => false

a.sort!
puts a[0] <= a[1] # => true
puts a[0] >= a[1] # => false
puts a[1] <= a[2] # => true
puts a[1] >= a[2] # => false

$O(1)$のために、全てを粛清する必要はない。革命を起こせばいいのだ。

黒魔術による革命がもたらしたものは混沌

謝辞

当初元記事を読み誤り記事を書きましたが、計算量とmethod missing以外は元ネタと同じです。勝手にソート名を変えた

多分既出だと思うけどこんなもん既出かどうか調べている暇があったら寝なさい。

睡眠不足はいい仕事の大敵です。¹

寝不足になりました²

1. ソートってなんだよ(哲学) ↩

2. 余談ですが、当初method_missingではなく、オープンクラスでdefine_methodを使用して、revolution_numberをインスタンス変数に持たせる方針で動作確認したところ、can't modify frozen Integer (FrozenError)の回避策がわからず断念しました。 ↩