Instantly share code, notes, and snippets.

# aspyct/sort.rb

Last active October 29, 2023 03:08
Show Gist options
• Save aspyct/3433278 to your computer and use it in GitHub Desktop.
Ruby implementation of quicksort, mergesort and binary search
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
 # 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"

### mathieujobin commented Jun 16, 2014

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

### joaquinmoreira commented Nov 13, 2014

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

### googya commented Jul 11, 2015

```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```

### leishman commented Jan 12, 2016

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?

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
end```

non 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?

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)
end```

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

``````