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

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

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.