Skip to content

Instantly share code, notes, and snippets.

@mdespuits

mdespuits/insertion-sort.rb

Last active August 29, 2015 14:08
Show Gist options
  • Save mdespuits/6287c8320868b453b97b to your computer and use it in GitHub Desktop.
Save mdespuits/6287c8320868b453b97b to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. @mattdbridges mattdbridges revised this gist Oct 29, 2014. 1 changed file with 43 additions and 0 deletions.
    43 changes: 43 additions & 0 deletions mark-sort.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,43 @@
    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

  2. @mattdbridges mattdbridges revised this gist Oct 29, 2014. 1 changed file with 42 additions and 0 deletions.
    42 changes: 42 additions & 0 deletions quicksort.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,42 @@
    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

  3. @mattdbridges mattdbridges created this gist Oct 29, 2014.
    45 changes: 45 additions & 0 deletions insertion-sort.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,45 @@
    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