Skip to content

Instantly share code, notes, and snippets.

@michaeldv
Created June 5, 2012 02:03
Show Gist options
  • Save michaeldv/2872022 to your computer and use it in GitHub Desktop.
Save michaeldv/2872022 to your computer and use it in GitHub Desktop.
Various sort algorithms in Ruby
# Plain bubble sort.
def bubble_sort(array)
loop do
swapped = false
(array.size - 1).times do |i|
if array[i] > array[i+1]
array[i], array[i+1] = array[i+1], array[i]
swapped = true
end
end
break unless swapped
end
array
end
array = Array.new(10) { rand(10) }
puts array.inspect
puts ">>>" + bubble_sort(array).inspect
# Bubble sort with lambda.
def bubble_sort(array)
swap = lambda { |arr, i, j| arr[i], arr[j] = arr[j], arr[i] if arr[i] > arr[j] }
loop do
swapped = false
(array.size - 1).times do |i|
swapped ||= swap[array, i, i+1]
end
break unless swapped
end
array
end
array = Array.new(10) { rand(10) }
puts array.inspect
puts ">>>" + bubble_sort(array).inspect
# Selection sort.
def selection_sort(array)
(array.size).times do |i|
index = array[i .. -1].each_with_index.min[1]
array[i], array[index+i] = array[index+i], array[i] if array[index+i] < array[i]
end
array
end
array = Array.new(20) { rand(20) }
puts array.inspect
puts ">>>" + selection_sort(array).inspect
# Merge sort.
def merge_sort(array)
return array if array.size < 2
middle = array.size / 2
head = merge_sort(array[0, middle])
tail = merge_sort(array.drop(middle))
# merged = []
# until head.empty? or tail.empty?
# merged << (head.first <= tail.first ? head.shift : tail.shift)
# end
# merged + head + tail
#
Array.new(head.size + tail.size) do |i|
if head.empty? || tail.empty?
head.shift || tail.shift
else
head[0] <= tail[0] ? head.shift : tail.shift
end
end
end
array = Array.new(20) { rand(20) }
puts array.inspect
puts ">>>" + merge_sort(array).inspect
# Quick sort.
def quick_sort(array)
return [] if array.empty?
pivot = array.shift
quick_sort(array.select{ |i| i <= pivot }) + [ pivot ] + quick_sort(array.select{ |i| i > pivot })
end
array = Array.new(21) { rand(21) }
puts array.inspect
puts ">>>" + quick_sort(array).inspect
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment