Rubyでアルゴリズムやらデータ構造やらのお勉強（Quick Sort / ほぼ直訳）

quick_sort.rb

# -*- coding: utf-8 -*-

# Cで書かれたアルゴリズムやらデータ構造なりを、自分なりにRubyで表現してみるお勉強PJ。
# 参考書籍（プログラミングの宝箱 アルゴリズムとデータ構造）
# Ruby1.9.3で動作確認済み

# ・・・と思ったけど、早速理解に時間がかかった。
# 再帰部分を切り出したり代入をRubyっぽくしたり以外、ほぼ書籍直訳状態
# さらにwhileの構文でひっかかり、結局下記のサイトを参考にして脱出した・・・うーん、要・再チャレンジ
# 参考サイト: http://www.jamboree.jp/cms/archives/47

$VERBOSE = true

class Array

  def quick_sort!
    _quick_sort! self, 0, length - 1
    self
  end

  private

  def _quick_sort!(data, bottom, top)
    return if bottom >= top

    div = data[bottom]
    
    lower = bottom
    upper = top

    while lower < upper
      while (lower <= upper && data[lower] <= div)
        lower += 1
      end

      while (lower <= upper && data[upper] > div)
        upper -= 1
      end

      if lower < upper
        data[lower], data[upper] = data[upper], data[lower]
      end
    end

    data[bottom], data[upper] = data[upper], data[bottom]

    _quick_sort! data, bottom, upper - 1
    _quick_sort! data, upper + 1, top
  end

end

# Overview

list = (-50..50).to_a.shuffle
p list
p list.object_id
p list.quick_sort!
p list.object_id