Created

Embed URL

HTTPS clone URL

SSH clone URL

You can clone with HTTPS or SSH.

Download Gist

Sample implementation of quicksort, mergesort and binary search in ruby

View sort.rb
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"

Thx

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.

it's good,

knappe commented

As @zetsubo pointed out, your quicksort algorithm is by definition going to run in n^2 time for already sorted arrays:

In very early versions of quicksort, the leftmost element of the partition 
would often be chosen as the pivot element. Unfortunately, this causes 
worst-case behavior on already sorted arrays, which is a rather common 
use-case

http://en.wikipedia.org/wiki/Quicksort#Choice_of_pivot

line 65, are you sure about the array.count - mid ?
shouldn't part_b be the full second half ?

forget about my previous comment about line 65, I get it ...

You need to add some return nil if from > to in the start of the binary search impl. Otherwise it will loop forever if the number is not in the array

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.