Skip to content

Instantly share code, notes, and snippets.

@aspyct
Last active October 29, 2023 03:08
  • Star 97 You must be signed in to star a gist
  • Fork 39 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save aspyct/3433278 to your computer and use it in GitHub Desktop.
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"
@doron2402
Copy link

Thx

@cheeyeo
Copy link

cheeyeo commented Oct 12, 2013

binary search gives stack level too deep errors

@excalq
Copy link

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
Copy link

"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
Copy link

it's good,

@knappe
Copy link

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
Copy link

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

@mathieujobin
Copy link

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

@joaquinmoreira
Copy link

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
Copy link

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
Copy link

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
Copy link

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
Copy link

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
Copy link

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