Sort Algorithms Implemented in Ruby

insertion-sort.rb

require 'minitest'
require 'minitest/autorun'
require 'benchmark/ips'

def sort(list)
  new_list = list.dup

  idx = 0
  while idx < list.size
    i = idx + 1
    key = new_list[i] # => comparing value
    break unless key
    o = idx
    while o >= 0
      break unless new_list[o]
      if new_list[o] > key
        new_list[o + 1] = new_list[o]
        new_list[o] = key
      end
      o -= 1
    end
    idx += 1
  end
  new_list
end

SAMPLE_SET = (1..100).to_a
EXAMPLE = SAMPLE_SET.shuffle
Benchmark.ips do |x|
  x.report("insert sort") do
    sort(EXAMPLE)
  end
  x.report("ruby sort") do
    EXAMPLE.sort
  end
end

class SortingTest < Minitest::Test
  def test_sorting_works
    100.times do
      assert_equal EXAMPLE.sort, sort(EXAMPLE)
    end
  end
end

mark-sort.rb

require 'minitest'
require 'minitest/autorun'
require 'benchmark/ips'

def mark_sort(array)
  array_max = array.max
  array_min = array.min
  markings = [0] * (array_max - array_min + 1)
  array.each do |a|
    markings[a - array_min] += 1
  end

  res = []
  markings.length.times do |i|
    markings[i].times do
      res << i + array_min;
    end
  end

  res
end

SAMPLE_SET = (1..100).to_a
EXAMPLE = SAMPLE_SET.shuffle
Benchmark.ips do |x|
  x.report("mark sort") do
    mark_sort(EXAMPLE)
  end
  x.report("ruby sort") do
    EXAMPLE.sort
  end

  x.compare!
end

class SortingTest < Minitest::Test
  def test_sorting_works
    100.times do
      assert_equal EXAMPLE.sort, mark_sort(EXAMPLE)
    end
  end
end

quicksort.rb

require 'minitest'
require 'minitest/autorun'
require 'benchmark/ips'

def quicksort(ary)
  ary = ary.dup
  return [] if ary.empty?

  pivot = ary.delete_at(rand(ary.size))

  left, right = [], []

  ary.each do |val|
    target = val <= pivot ? left : right
    target << val
  end

  quicksort(left)
    .concat([pivot])
    .concat(quicksort(right))
end

SAMPLE_SET = (1..100).to_a
EXAMPLE = SAMPLE_SET.shuffle
Benchmark.ips do |x|
  x.report("quicksort") do
    quicksort(EXAMPLE)
  end
  x.report("ruby sort") do
    EXAMPLE.sort
  end
  x.compare!
end

class SortingTest < Minitest::Test
  def test_sorting_works
    100.times do
      assert_equal EXAMPLE.sort, quicksort(EXAMPLE)
    end
  end
end