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 + # 再帰と結果のつなぎ合わせ
      [pivot] +                               ## select は配列から条件を合うものを選択
      select { |x| x >= pivot }.conceptual_quick_sort
    # 上記三行の代わり:
    # partition { |x| x < pivot }.            # 二つに分割
    #    map { |a| a.conceptual_quick_sort }. # それぞれに再帰的に適用
    #    flatten(1)                           # 二つの配列を一つに平板化
    # もう一つの書き方 (同値の値がある場合にも対応):
    # groups = group_by { |x| x <=> pivot }   # 小同大の三つのグループに分ける
    # groups.default = []                     # グループが空の場合に対応
    # groups[-1].conceptual_quick_sort +
    #    groups[0].conceptual_quick_sort +
    #    groups[1].conceptual_quick_sort
    # 前三行は次のようにも可能
    # (-1..1).map { |g| groups[g].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 (leftmost, rightmost)
    if leftmost < rightmost
      pivot = self[rightmost]
      left  = leftmost-1
      right = rightmost
      loop do                                 # loop: break までの繰返し
        while self[left += 1] < pivot do end  # 左側から pivot より大きいものを検索
        while right > leftmost and
              self[right -= 1] > pivot do end # 右側から pivot より小さいものを検索
        break if left >= right
        swap(left, right)
      end
      swap(left, rightmost)                   # pivot を真ん中に配置
      simple_quick_sort_recurse(leftmost, left-1)
      simple_quick_sort_recurse(left+1, rightmost)
    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 order(a, b)
    swap(a, b) if self[a] > self[b]
  end

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

  def quick_sort ()  dup.quick_sort!  end
end