# Quicksort implementation

I put together this implementation after playing around with various partitioning- and pivot-strategies, and it runs fine. I wrote this off a version which seemed a bit different from the majority of implementations, so I'm curious on what you guys think. It works and handles duplicates.

def quicksort(a, min=0, max=a.length-1)
if min < max
index = partition(a, min, max)
quicksort(a, min, index-1)
quicksort(a, index+1, max)
end
end

def partition(a, l, r)

m=(l+r)/2
piv = a[m]
a[m], a[r] = a[r], a[m]

cur = l
for i in l..r-1

if a[i] <= piv
a[i], a[cur] = a[cur], a[i]
cur+=1
end
end
a[cur], a[r] = a[r], a[cur]

return cur

end

• It's amusing just how terse Quicksort can be in Ruby. For a functional (that is, not in-place) version of Quicksort that is just a few lines, see this page on Ward's wiki Mar 9, 2014 at 10:23

You code looks nice, my main problem with it is naming:

Don't use single letters as member names, unless they are trivial. I couldn't figure out what l and r stand for until I read your code a couple of times (length? range?).

Even more so, don't ever use the letter l as a variable name - it is much too similar to 1, and is notoriously known to obfuscate code.

Don't re-use too familiar names for different purposes - partition is a well known method in ruby enumerables. Using this name for your code, especially when it involves arrays is very confusing. Don't do that. Call it reorder_partition or pivot_partition.

Expressiveness goes a long way - a[l], a[r] = a[r], a[l] works perfectly, but is hard to read, a much more readable way would be if you had a helper method swap(a, l, r). Even better might look to implement it into Array a.swap!(l, r)

Use the power of ruby - instead of l..r-1, use non-inclusive range operator - l...r

So, my version may look a little more verbose, but I believe it is much more readable. It did teach me a lot about quicksort :-)

def quicksort(array, min=0, max=array.length-1)
if min < max
index = reorder_partition(array, min, max)
quicksort(array, min, index-1)
quicksort(array, index+1, max)
end
end

def reorder_partition(array, left_index, right_index)
middle_index = (left_index + right_index)/2
pivot_value = array[middle_index]

array.swap!(middle_index, right_index)

less_array_pointer = left_index

(left_index...right_index).each do |greater_array_pointer|
if array[greater_array_pointer] <= pivot_value
array.swap!(greater_array_pointer, less_array_pointer)
less_array_pointer+=1
end
end

array.swap!(less_array_pointer, right_index)

return less_array_pointer
end

class Array
def swap!(a,b)
self[a], self[b] = self[b], self[a]
self
end
end

• +1. Just some comments: 1) I'd use each instead of for (more idiomatic). 2) Some spaces seem to be missing (for example on middle_index=(... Mar 7, 2014 at 8:03

# Integer Overflow

I'm not very confident with ruby but I'm assuming this is integer arithmetic (otherwise you could have a floating point index, which doesn't make sense):

  m=(l+r)/2


If it indeed is integer arithmetic you will have an integer overflow if you're dealing with large arrays.

You should implement it as:

 m = l + (r - l)/2;


which will not overflow for any 0 <= l <= r.