8
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – Wayne Conrad Mar 9 '14 at 10:23
5
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ +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=(... \$\endgroup\$ – tokland Mar 7 '14 at 8:03
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.