Seki's Diary は 移転しました

_ [misc]クイックソートが5行で書けるなんて

そういえば、私も昔F-BASICでバブルソートを書いたことがあったかもしれない、などと思いつつ、ちょっと調べてみました。WikipediaのQuicksortには、いくつかの言語でのクイックソートが記述されています。Ruby でも5行のようです。

def sort(array)
  return [] if array.empty?
  left, right = array[1..-1].partition { |y| y <= array.first }
  sort(left) + [ array.first ] + sort(right)
end

Pythonだと4行、そしてJoyという言語だと3行らしいです。

DEFINE sort == [small][]
               [uncons [>] split]
               [[swap] dip cons concat] binrec .

さらに、Quicksort implementationsでもっといろいろな言語でのクイックソートが記述されています。Jでも3行ですが、これは記号ばかりでなんだかすごい言語ですね。

sort =: ]`(($:@: ((}.<:{.)#}.)) 
             ,{., 
            ($:@: ((}.> {.)#}.)))  @. (*@#)