Last active
April 3, 2025 12:24
-
-
Save aspyct/3433278 to your computer and use it in GitHub Desktop.
Ruby implementation of quicksort, mergesort and binary search
This file contains hidden or 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
| # 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" |
def binary_search2( arr, t,from=0, to=nil)
if to.nil?
to = arr.size - 1
end
return if from > to
mid = (from + to ) / 2
if arr[mid] > t
binary_search2 arr, t, 0, mid - 1
elsif arr[mid] < t
binary_search2 arr, t, mid + 1, to
else
mid
end
end
iterative binary search:
def binary_search arr, key
low = 0
high = arr.length - 1
while(high >= low) do
mid = low + (high - low) / 2
if arr[mid] > key
high = mid - 1
elsif arr[mid] < key
low = mid + 1
else
return mid
end
end
return -1
end
iterative
def binary_search(array, value, from=0, to=nil)
to = array.count - 1 if to == nil
# from can't be bigger than to
raise ArgumentError if from > to
# out of range
raise ArgumentError if from < 0
raise ArgumentError if to >= array.count
mid = (from + to) / 2
comparison = value <=> array[mid]
# incomparable values
raise ArgumentError if comparison.nil?
# not found
return -1 if from == to && comparison != 0
case comparison
when 0
mid
when -1
binary_search array, value, from, mid - 1
when 1
binary_search array, value, mid + 1, to
end
endnon iterative
def binary_search(array, value, from=0, to=nil)
to = array.count - 1 if to == nil
# from can't be bigger than to
raise ArgumentError if from > to
# out of range
raise ArgumentError if from < 0
raise ArgumentError if to >= array.count
while true do
mid = (from + to) / 2
comparison = value <=> array[mid]
# incomparable values
raise ArgumentError if comparison.nil?
# not found
return -1 if from == to && comparison != 0
case comparison
when 0
return mid
when -1
to = mid - 1
when 1
from = mid + 1
end
end
end
Here's my stab at merge sort
def merge_sort(array)
return array if array.size <= 1
left, right = array.each_slice((array.size/2).round).to_a
merge = -> (left, right) {
array = []
while left.size > 0 && right.size > 0
array << (left[0] < right[0] ? left.shift : right.shift)
end
return array = array + left + right
}
return merge.call merge_sort(left), merge_sort(right)
endAnd others: https://gist.github.com/adamjgrant/b0af5f9b938b3ac8f6b56e424ff8b978
here's another go on a quick and merge sort. (Note, that this, as well as all the others here, are non-inplace and non-destructive implementations
def qs(arr)
return arr if arr.empty?
index = rand(arr.length)
p = arr.delete_at(index)
a,b = arr.partition { |e| e < p }
arr.insert(index, p)
return [*qs(a), p, *qs(b)]
end
def ms(arr)
# break recursion
return arr if arr.length <=1
# split + merge
m = arr.length / 2
a, b = ms(arr[0...m]), ms(arr[m..-1])
# merge
rv = []
while[a,b].none?(&:empty?) do
rv << (a[0] < b[0] ? a.shift : b.shift)
end
# one of a/b is empty
rv.concat(a).concat(b)
end
# test
100.times do
test_a = 30.times.map { rand(1000) }
raise "You're wrong on qs" unless test_a.sort == qs(test_a)
raise "You're wrong on ms" unless test_a.sort == ms(test_a)
end
```
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
You need to add some
return nil if from > toin the start of the binary search impl. Otherwise it will loop forever if the number is not in the array