Skip to content

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Sample implementation of quicksort, mergesort and binary search in ruby
# 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"
@cheeyeo

binary search gives stack level too deep errors

@excalq

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.

@jademcgough

"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

it's good,

@knappe

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

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

@mathieujobin

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

@joaquinrulin

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
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.