クイックソート(非再帰版）

中央値ソートをベースに処理を簡単にしたソート。
平均計算量はO(nlogn)であるが、最悪時はO(n^2)となる。
アルゴリズムとしては分割統治法に分類される。

今回は高速化のため、以下の点に取り組んだ。
・再帰処理を省くためループで実装
・3つの値から中央値を選択する
・スタックの深さを小さくするため要素の小さい方からソートしていく

また、取り入れなかった手法は
・部分配列への挿入ソートの適用
である。

#最悪時はo(n^2)だがpivot選択で最悪の場合は回避

def quicksort!(array, head, tail)
  #ソート待ちスタックの生成
  #初回は配列全体がソート待ち状態
  stack = Array.new
  stack.push([head, tail])

  while stack.size > 0 do
    #ソート待ちスタックが空になるまで繰り返す

    #初期化処理
    #leftとrightの更新を忘れると分割範囲が配列全体となり無限ループ
    target = stack.pop
    pl = left = target[0]
    pr = right = target[1]

    #pivotの決定
    #分割の偏りを防ぐため、先頭、中央、末尾の中央値を取る
    pivot = 0
    begin
      a = array[pl]
      b = array[(pl + pr) / 2]
      c = array[pr]
      if a > c then
        pivot = (c > b ? c : (a > b ? b : a))
      else
        pivot = (c > b ? (a > b ? a : b) : c) 
      end 
    end

    #pivotを基準に要素の交換を行う
    begin
      while array[pl] < pivot do
        pl += 1
      end
      while array[pr] > pivot do
        pr -= 1
      end
      if pl <= pr then
        tmp = array[pl]
        array[pl] = array[pr]
        array[pr] = tmp
        pl += 1
        pr -= 1
      end
    end while pl <= pr

    #スタック使用量を減らすため要素が少ない方からソートできるようにする
    #分割した左部分の方が右部分よりも要素が多い場合は入れ替える
    if  pr - left < right - pl then
      tmpleft = pl
      tmppr = right
      pl = left
      right = pr
      left = tmpleft
      pr = tmppr
    end
    
    #配列を分割し、ソート待ちスタックにプッシュする
    #分割した右部分が先にソート対象となる
    if left < pr then
      stack.push([left, pr])
    end
    if pl < right then
      stack.push([pl, right])
    end
  end
end

data = Array.new
while input = $stdin.gets.to_i
  break if input < 0
  data << input
end

p data
quicksort!(data, 0, data.size - 1)
p data