Quicksort implementation

Question

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

• Wayne Conrad: 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

Answer 1

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

• tokland: +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=(...

Answer 2

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.