Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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
You can’t perform that action at this time.