Skip to content

Instantly share code, notes, and snippets.

@mdespuits
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.
Sort Algorithms Implemented in Ruby
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
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
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment