クイックソート

Haskellをかじりはじめました。
この本で勉強しています。

【楽天ブックスならいつでも送料無料】ふつうのHaskellプログラミング [ 青木峰郎 ] 価格：3,024円（税込、送料込）

2006年のものなのでちょっと古いのかもしれませんが、初心者にはとてもわかりやすいです。
ありがとうございます。
本でつかっているghcのバージョンは6.2.2でいまの最新は7.8.4のようです。
本文中のimportのところは下記のように読み替えると大丈夫でした。
import System -> import System.Environment
import List -> import Data.List

qsort [] = []
qsort (p:xs) = qsort lt ++ [p] ++ qsort gteq
                where
                  lt   = [x | x <- xs, x < p]
                  gteq = [x | x <- xs, x >= p]

慣れないうちはなんのことやら？　だったのですが、上くらいのことがわかるようになるとクイックソートのことがすっきりとわかるようになりました。


Rubyで書いてみました。

def qsort(ary)
 ary.empty? ?
     [] :
     qsort(ary.drop(1).select{|n| n < ary[0]}) + [ary[0]] + qsort(ary.drop(1).select{|n| ary[0] <= n})
end
p qsort([10, 9, 8, 7, 6, 5, 1000, 0]) # ①
p qsort(%w|hello goodby こんにちは 6 5 1000 0 Ruby Python Haskell C C++ Java|) # ②

①はNumericの配列のソートです。

②はStringの配列のソートです。

まったく同じメソッドがそのまま使えます。

これはFixnumクラス、Stringクラスがmodule Comparableをincludeしていて、

<=>演算子(メソッド)を定義しているので各要素の比較が可能であるためです。

ポリモーフィズムというやつです。

Array#drop(n)はnが1だったら[4,5,6] -> [5,6]を返すメソッドです。nは落とす個数を指定するらしいです。

drop(1)はHaskellのtailと同じ意味あいになるかとおもわわれます。

Arrayにモンキーパッチしてみました。
上の例はpivotを必ず先頭から選んでいますが、ランダムに選ぶようにしてみました。

class Array
  def qsort(ary=self)
    ary.empty? ?
      [] :
      (ary = ary.dup
       pivot = ary.delete_at(rand(ary.length))
       qsort(ary.select{|n| n < pivot}) + [pivot] + qsort(ary.select{|n| pivot <= n}))
  end
end

ary = [10, 9, 8, 7, 6, 5, 1000, 0]
p ary.qsort
p ary # 上の例では新しいArrayインスタンスを返しているので、元の並び順は変更されません。

結局こうすればよいのかもしれません。

module TorifukuModule
  extend self

  def qsort(ary=self)
    ary.empty? ?
      [] :
      (ary = ary.dup
       pivot = ary.delete_at(rand(ary.length))
       qsort(ary.select{|n| n < pivot}) + [pivot] + qsort(ary.select{|n| pivot <= n}))
  end
end

class Array
  include TorifukuModule
end

ary = [10, 9, 8, 7, 6, 5, 1000, 0]
p ary.qsort
p TorifukuModule.qsort(ary)

$ ruby -v

ruby 2.0.0p645 (2015-04-13 revision 50299) [x86_64-darwin14.4.0]

enjoy!

2015/07/27追記
ary=selfがなんか変だなあとおもっていました。
こうすればいいのかもしれません。

module TorifukuModule
  def qsort
    empty? ?
      [] :
      (ary = dup
       pivot = ary.delete_at(rand(ary.length))
       ary.select{|n| n < pivot}.qsort + [pivot] + ary.select{|n| pivot <= n}.qsort)
  end
end

class Array
  include TorifukuModule
end

ary = [10, 9, 8, 7, 6, 5, 1000, 0]
p ary.qsort