クイックソートの習作

quicksort.rb

# coding: utf-8

$arr = [43,145,35,32,565,5,76,43,2,5,66,332,44,42,34,42,43,23,4,24,542,1,1,34,23]

p "arr:"
p $arr

def calc(mini, maxi)
  ai = mini
  bi = maxi
  pi = (mini + maxi) / 2
  ii = 0
  pivot = $arr[pi]

  loop do
    ai.upto(pi) do |i|
      ii = i
      break if($arr[i] > pivot)
    end

    ai = ii

    bi.downto(pi) do |i|
      ii = i
      break if($arr[i] < pivot)
    end

    bi = ii

    if(ai < pi && bi > pi)
      $arr[ai], $arr[bi] = $arr[bi], $arr[ai]
    elsif(ai == pi && $arr[bi] < pivot)
      $arr[pi], $arr[bi] = $arr[bi], $arr[pi]
      pi = bi
    elsif(bi == pi && $arr[ai] > pivot)
      $arr[pi], $arr[ai] = $arr[ai], $arr[pi]
      pi = ai
    end

    break if(ai >= pi && bi <= pi)
  end

  calc(mini, pi) if(ai > mini && mini < pi)
  calc(pi+1, maxi) if(bi < maxi && pi+1 < maxi)
end

calc(0, $arr.size - 1)

p 'result:'
p $arr