require '5sort.rb'                 # swap と insertion_sort を使用

# 何よりも小さいもの (番兵用)
class Smallest
  include Comparable                          # 他の比較演算子も使用可能に

  def <=> (other)
    -1                                        # Smallest のインスタンスは何よりも小さい
  end
end

class Array
  # 概念的なクイックソート
  def conceptual_quick_sort ()
    return self if length <= 1
    pivot = self[rand length]                 # 乱数で pivot 要素を決定
    select { |x| x < pivot }.conceptual_quick_sort + # 再帰と結果のつなぎ合わせ
      select { |x| x >= pivot }.conceptual_quick_sort## select は配列から条件を合うものを選択
    # 上記二行の代わり: partition { |x| x < pivot }.  # 二つに分割
    #                collect { |a| a.conceptual_quick_sort }.  # それぞれに再帰的に適用
    #                  flatten(1)                # 二つの配列を一つに平板化
  end

  def conceptual_quick_sort! ()
    replace conceptual_quick_sort             ## replace は配列自体を置換
  end


  # 単純なクイックソート
  def simple_quick_sort! ()
    simple_quick_sort_recurse(0, length-1)
    self
  end

  def simple_quick_sort_recurse (left, right)
    if left < right
      left_scan = left-1
      right_scan = right
      pivot = at(right)
      loop do                                 # loop: break までの繰返し
        while at(left_scan += 1) < pivot do end # 左側から pivot より大きいものを検索
        while right_scan > left and
              at(right_scan -= 1) > pivot do end # 右側から pivot より小さいものを検索
        break if left_scan >= right_scan
        swap(left_scan, right_scan)
      end
      swap(left_scan, right)                  # pivot を真ん中に配置
      simple_quick_sort_recurse(left, left_scan-1)
      simple_quick_sort_recurse(left_scan+1, right)
    end
  end

  def simple_quick_sort ()  dup.simple_quick_sort!  end
























  # 高速化されたクイックソート
  def quick_sort! ()
    unshift Smallest.new                            # 一番左に番兵を追加
    quick_sort_recurse(0, length-1)
    insertion_sort!                                 # 挿入ソートによる仕上げ
    shift                                           # 番兵の除去
    self
  end

  def quick_sort_recurse (left, right)
    while left < right-10          # while による末尾再帰; 10 項目以下は仕上げで整列
      left_scan = left-1
      right_scan = right
      center = (left+right).div 2                   # 三項目の中央値の決定
      swap(left, right) if at(left) > at(right)
      swap(right, center) if at(right) > at(center)
      swap(left, right) if at(left) > at(right)
      pivot = at(right)
      # ここで at(left) <= at(right)==pivot <= at(center)
      loop do
        while at(left_scan += 1) < pivot do end     
        while at(right_scan -= 1) > pivot do end    # 番兵のため、チェックは不要
        break if left_scan >= right_scan
        swap(left_scan, right_scan)
      end
      middle = left_scan                            # (分割点を明示)
      swap(middle, right)
      if middle-left > right-middle                 # 深いスタックへの対策
        simple_quick_sort_recurse(middle+1, right)  # 右の小さい方で実際に再帰
        right = middle -1                           # 左の大きい方で末尾再帰
      else
        simple_quick_sort_recurse(left, middle-1)   # 左の小さい方で実際に再帰
        left = middle+1                             # 右の大きい方で末尾再帰
      end
    end
  end

  def quick_sort ()  dup.quick_sort!  end
end