{{ message }}

Instantly share code, notes, and snippets.

# aspyct/sort.rb

Last active Jul 16, 2021
Ruby implementation of quicksort, mergesort and binary search
 # 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.

### immykins 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.

### Harryyan commented Mar 30, 2014

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

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

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