Created
January 14, 2014 22:46
-
-
Save TGOlson/8427444 to your computer and use it in GitHub Desktop.
Ruby sorting algorithms.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def bubble_sort(list) | |
sorted = false | |
until sorted | |
sorted = true | |
(0...list.length).each do |i| | |
if !list[i + 1].nil? && list[i] > list[i + 1] | |
list[i], list[i + 1] = list[i + 1], list[i] | |
sorted = false | |
end | |
end | |
end | |
list | |
end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def merge_sort(list) | |
return list if list.length <= 1 | |
left = list[0...list.length/2] | |
right = list[list.length/2..-1] | |
left = merge_sort(left) | |
right = merge_sort(right) | |
merge(left, right) | |
end | |
def merge(left, right) | |
result = [] | |
until left.empty? || right.empty? | |
if left.first <= right.first | |
result << left.shift | |
else | |
result << right.shift | |
end | |
end | |
result += left if right.empty? | |
result += right if left.empty? | |
result | |
end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def quick_sort(list) | |
return list if list.length <= 1 | |
pivot = list.pop | |
less = [] | |
greater = [] | |
list.each do |i| | |
less << i if i <= pivot | |
greater << i if i > pivot | |
end | |
quick_sort(less) + [pivot] + quick_sort(greater) | |
end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def radix_sort(list) | |
passes = (list.max == 0) ? 1 : Math.log10(list.max).to_i + 1 | |
new_list = [] | |
passes.times do |i| | |
buckets = make_buckets | |
list.each do |n| | |
digit = get_digit(n, i) | |
buckets[digit] += [n] | |
end | |
new_list, buckets = buckets.flatten, make_buckets | |
end | |
new_list | |
end | |
def make_buckets | |
Array.new(10,[]) | |
end | |
def get_digit(n, i) | |
n % (10 ** (i + 1)) / (10 ** i) | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment