クイックソート（Ruby）

いわゆる「K&R」本（『プログラミング言語C 第2版 ANSI規格準拠』p.106）に載っている配列のクイックソートを、Ruby に移植してみました。メソッド（C言語では関数）の再帰呼び出しの例として使われています。コードは殆ど本そのままですが、C言語よりは読みやすくなっていると思います。

アルゴリズムは、配列を真ん中の数字で分割して左右に振り分けるというのを、再帰させています。でも、やっていることはなかなかむずかしい。例を作って１ステップずつゆっくりと追ってみると確かにソートされるけれど、何だか魔法みたい。

class Array
  def qsort(left, right)
    return self if left >= right
    swp(left, (left + right).div(2))
    last = left
    for i in (left + 1)..right
      if self[i] < self[left]
        last += 1
        swp(last, i)
      end
    end
    swp(left, last)
    qsort(left, last - 1).qsort(last + 1, right)
  end

  def swp(i, j)
    self[i], self[j] = self[j], self[i]
  end
end

p [5, 4, 3, 2, 1].qsort(0, 4)

結果

[1, 2, 3, 4, 5]

もちろん組み込みメソッドの

p [5, 4, 3, 2, 1].sort

と同じことです。

途中経過を出力させてみると、例えば

[10, 8, 3, 6, 7, 1, 4, 9, 2, 5]
[5, 3, 6, 1, 4, 2, 7, 9, 8, 10]  #7の左右に分割した
[2, 3, 5, 1, 4, 6, 7, 9, 8, 10]  #6
[4, 3, 2, 1, 5, 6, 7, 9, 8, 10]  #5
[1, 2, 3, 4, 5, 6, 7, 9, 8, 10]  #3
[1, 2, 3, 4, 5, 6, 7, 9, 8, 10]  #1
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]  #8
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]  #9

というふうになります。

追記

Wikipedia の実装例も Ruby に移植しておきます。（10/14）

class Array
  def qsort(left, right)
    a = self
    return a if left >= right
    i = left; j = right
    pivot = med3(a[i], a[i + (j - i) / 2], a[j])
    loop do
      while a[i] < pivot do i += 1 end
      while pivot < a[j] do j -= 1 end
      break if i >= j
      a[i], a[j] = a[j], a[i]
      i += 1; j -= 1
    end
    qsort(left, i - 1).qsort(j + 1, right)
  end
end

def med3(x, y, z)
  if x < y
    if y < z then y elsif z < x then x else z end
  else
    if z < y then y elsif x < z then x else z end
  end
end

p [2, 5, 1, 3, 4, 3].qsort(0, 5)    #=>[1, 2, 3, 3, 4, 5]

　
ここの Java 版を Ruby に移植したもの。

class Array
  def pivot(i, j)
    a = self
    k = i + 1
    while k <= j and a[i] == a[k] do k += 1 end
    return nil if k > j
    return i if a[i] >= a[k]
    k
  end
  
  def partition(i, j, x)
    a = self; l = i; r = j
    while l <= r
      while l <= j and a[l] < x  do l += 1 end
      while r >= i and a[r] >= x do r -= 1 end
      break if l > r
      a[l], a[r] = a[r], a[l]
      l += 1; r -= 1
    end
    l
  end
  
  def qsort(i, j)
    return self if i == j
    if q = pivot(i, j)
      k = partition(i, j, self[q])
      qsort(i, k - 1).qsort(k, j)
    end
    self
  end
end

p [3, -1, 1, 0, 4, 0].qsort(0, 5)   #=>[-1, 0, 0, 1, 3, 4]

　
Ruby らしい、非常に短い実装がネット上にありました。ここからコピペです。すごいですね。これに尽きているような感じです。

class Array
  def qsort
    return self if size < 2
    pivot = shift
    partition {|num| num < pivot}.map(&:qsort).insert(1, pivot).flatten
  end
end

p [3, 2, 5, 4, 1].qsort     #=>[1, 2, 3, 4, 5]

　
色んな実装がありますね。なお、上のすべての qsort メソッドは破壊的です。

※追記（2017/6/16）
いちばん素直な実装はこうではないですかね。関数型プログラミングに近いのではないかと思います。ゆえにこの実装ではメソッドは破壊的ではありません。

class Array
  def qsort
    return [] if empty?
    x, xs = first, drop(1)
    xs.select{|i| i <= x}.qsort + [x] + xs.select{|i| i > x}.qsort
  end
end

p [5, 3, 4, 1, 2, 7, 4].qsort    #=>[1, 2, 3, 4, 4, 5, 7]