Instantly share code, notes, and snippets.

# aspyct/sort.rb

Last active October 29, 2023 03:08
Star You must be signed in to star a gist
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"

Thx

### cheeyeo commented Oct 12, 2013

binary search gives stack level too deep errors

### excalq commented Feb 21, 2014

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.

### imogenkinsman commented Mar 25, 2014

"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 May 13, 2014

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

### mathieujobin commented Jun 16, 2014

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

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

### stereobooster commented Sep 28, 2016 • edited

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

### adamjgrant commented Nov 3, 2016 • edited

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 < right ? left.shift : right.shift)
end

return array = array + left + right
}

return merge.call merge_sort(left), merge_sort(right)
end```

### cmantas commented Dec 8, 2016 • edited

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

``````