public
Last active

Sample implementation of quicksort, mergesort and binary search in ruby

  • Download Gist
sort.rb
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134
# Sample implementation of quicksort and mergesort in ruby
# Both algorithm sort in O(n * lg(n)) time
# Quicksort works inplace, where mergesort works in a new array
 
def quicksort(array, from=0, to=nil)
if to == nil
# Sort the whole array, by default
to = array.count - 1
end
 
if from >= to
# Done sorting
return
end
 
# Take a pivot value, at the far left
pivot = array[from]
 
# Min and Max pointers
min = from
max = to
 
# Current free slot
free = min
 
while min < max
if free == min # Evaluate array[max]
if array[max] <= pivot # Smaller than pivot, must move
array[free] = array[max]
min += 1
free = max
else
max -= 1
end
elsif free == max # Evaluate array[min]
if array[min] >= pivot # Bigger than pivot, must move
array[free] = array[min]
max -= 1
free = min
else
min += 1
end
else
raise "Inconsistent state"
end
end
 
array[free] = pivot
 
quicksort array, from, free - 1
quicksort array, free + 1, to
end
 
def mergesort(array)
if array.count <= 1
# Array of length 1 or less is always sorted
return array
end
 
# Apply "Divide & Conquer" strategy
 
# 1. Divide
mid = array.count / 2
part_a = mergesort array.slice(0, mid)
part_b = mergesort array.slice(mid, array.count - mid)
 
# 2. Conquer
array = []
offset_a = 0
offset_b = 0
while offset_a < part_a.count && offset_b < part_b.count
a = part_a[offset_a]
b = part_b[offset_b]
 
# Take the smallest of the two, and push it on our array
if a <= b
array << a
offset_a += 1
else
array << b
offset_b += 1
end
end
 
# There is at least one element left in either part_a or part_b (not both)
while offset_a < part_a.count
array << part_a[offset_a]
offset_a += 1
end
 
while offset_b < part_b.count
array << part_b[offset_b]
offset_b += 1
end
 
return array
end
 
# Search a sorted array in O(lg(n)) time
def binary_search(array, value, from=0, to=nil)
if to == nil
to = array.count - 1
end
 
mid = (from + to) / 2
 
if value < array[mid]
return binary_search array, value, from, mid - 1
elsif value > array[mid]
return binary_search array, value, mid + 1, to
else
return mid
end
end
 
a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15].shuffle
# Quicksort operates inplace (i.e. in "a" itself)
# There's no need to reassign
quicksort a
puts "quicksort"
puts a
 
b = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15].shuffle
# Mergesort operates in new array
# So we need to reassign
b = mergesort b
puts "mergesort"
puts b
 
offset_3 = binary_search a, 3
puts "3 is at offset #{offset_3} in a"
 
offset_15 = binary_search b, 15
puts "15 is at offset #{offset_15} in b"

binary search gives stack level too deep errors

On line 13, you'll need to return array, unless you're purely doing an in-place sort on an existing array.
i.e. If you want to call quicksort([1,3,2,5,9,1]) and print an answer, return the sorted array.

"Both algorithm sort in O(n * lg(n)) time"

Quicksort is actually O(n^2), though on average this is very rare if it's well implemented.

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.