Create a gist now

Instantly share code, notes, and snippets.

@aspyct /sort.rb
Last active Nov 9, 2017

What would you like to do?
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.

"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

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

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

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

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

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

And others: https://gist.github.com/adamjgrant/b0af5f9b938b3ac8f6b56e424ff8b978

cmantas commented Dec 8, 2016

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