sorts.rb

module Sort

  def self.sort_bead(tab)
    @c = 0
    tab = _sort_bead_columns(
      _sort_bead_columns(
        tab.map{|e| [1] * e.abs}
      )
    ).map(&:size)
    return { complexity: @c, result: tab.reverse }
  end

  def self._sort_bead_columns(tab)
    y = tab.size
    x = tab.map(&:size).max
    return ::Array.new(x) do |line|
      @c += 1
      ::Array.new(y) { |col| tab[col][line] }.compact
    end
  end

end
module Sort

  def self.sort_bubble(tab)
    c = 0
    n = tab.size
    n.times do |j|
      1.upto(n - j - 1) do |i|
        if tab[i] < tab[i - 1]
          tab[i], tab[i - 1] = tab[i - 1], tab[i]
        end
        c += 1
      end
    end
    return {complexity: c, result: tab}
  end

end
# coding: utf-8
module Sort

  def self.sort_insertion(tab)
    c = 0
    n = tab.size - 1

    1.upto(n) do |i|
      j = i
      loop do
        break if j == 0
        c += 1
        break if tab[j] < tab[j - 1]
        tab[j], tab[j-1] = tab[j-1], tab[j]
        j -= 1
      end
    end

    return {complexity: c, result: tab.reverse}
  end

end
# coding: utf-8
module Sort

  def self.sort_merge(tab)
    @c = 0
    tab = _sort_merge(tab)
    return {complexity: @c, result: tab}
  end

  def self._sort_merge(tab)
    return tab if tab.size <= 1
    middle = tab.size / 2
    left = _sort_merge(tab[0...middle])
    right = _sort_merge(tab[middle..-1])
    return _sort_merge_combi(left, right)
  end

  def self._sort_merge_combi(left, right)
    result = []
    loop do
      break if left.empty? or right.empty?
      @c += 1
      result << (left.first <= right.first ? left : right).shift
    end
    return result + left + right
  end

end
module Sort

  def self.sort_pancake(tab)
    c = 0
    (tab.size - 1).downto(1) do |end_idx|
      c += 1
      r = tab[0..end_idx]
      max = r.max
      max_idx = r.index(max)
      c += max_idx + 1
      next if max_idx == end_idx

      c += 1
      if max_idx > 0
        tab[0..max_idx] = tab[0..max_idx].reverse
      end

      tab[0..end_idx] = tab[0..end_idx].reverse
    end
    return { complexity: c, result: tab }
  end

end
module Sort

  def self.sort_patience(tab)
    c = 0
    stacks = []
    tab.each do |i|
      idx = stacks.index{|stack| c+=1; stack.last <= i}
      if idx.nil?
        stacks << [i]
      else
        stacks[idx] << i
      end
    end

    results = []
    loop do
      break if stacks.empty?
      c += stacks.size
      first = stacks.map(&:first)
      idx = first.index(first.min)
      result = stacks[idx].shift
      results << result
      stacks.delete_at(idx) if stacks[idx].empty?
    end
    return { complexity: c, result: results }
  end

end
module Sort

  def self.sort_quick(tab)
    @c = 0
    tab = _sort_quick(tab)
    return {complexity: @c, result: tab}
  end

  def self._sort_quick(tab)
    return tab if tab.size < 2

    pivot = tab.first
    greater, less = [], []
    @c += tab.size - 1
    tab[1..-1].each do |e|
      if e >= pivot
        greater << e
      elsif e < pivot
        less << e
      end
    end

    greater = _sort_quick(greater)
    less = _sort_quick(less)

    return less + [pivot] + greater
  end

end
module Sort

  def self.sort_radix(tab, base=10)
    c = 0
    top = tab.map(&:abs).max
    rounds = Math.log(top) / Math.log(base)
    rounds = rounds.floor + 1
    rounds.times do |i|
      buckets = (2 * base).times.map{ [] }
      base_i = base**i
      tab.each do |value|
        c += 1
        digit = (value / base_i) % base
        digit += base unless value <= 0
        buckets[digit] << value
      end
      tab = buckets.flatten
    end
    return {complexity: c, result: tab}
  end

end
# coding: utf-8
module Sort

  def self.sort_selection(tab)
    c = 0
    n = tab.size - 1

    0.upto(n) do |i|
      small = i
      (i+1).upto(n) do |j|
        c += 1
        if tab[j] < tab[small]
          small = j
        end
      end
      tab[i], tab[small] = tab[small], tab[i]
    end

    return {complexity: c, result: tab}
  end

end
module Sort

  MID_DIV = 5.0 / 11.0
  def self.sort_shell(tab)
    c = 0
    mid = tab.size / 2
    n = tab.size - 1
    loop do
      break if mid.zero?
      mid.upto(n) do |i|
        save = tab[i]
        loop do
          c += 1
          break unless i >= mid and tab[i - mid] > save
          tab[i] = tab[i - mid]
          i -= mid
        end
        tab[i] = save
      end
      mid = (mid == 2 ? 1 : mid.to_f * MID_DIV).to_i
    end
    return { complexity: c, result: tab }
  end

end