Working with Ruby
Hi, I am Jan. This is my old Ruby blog. I still post about Ruby, but I now do it on idiosyncratic-ruby.com. You should also install Irbtools to improve your IRB.

Quicksort in 5 minutes

September 2009, ruby · hints · algorithm

Some time ago, I conducted a short presentation about Ruby. And to impress the audience, I did some live coding and implemented the quicksort algorithm in 5 minutes. They were impressed :)

quicksort 
 1
2
3
4
5
6
7
8
9
10
11
12

class Array
  def qsort
    return self if self.length <= 1
    pivot = self.shift
    left, right = [],[]
    self.each { |ele| ele <= pivot ? left << ele : right << ele }
    left.qsort + [pivot] + right.qsort
  end
end

# Example of use
# p t[8,6,544,423,3].qsort
Creative Commons License

J-_-L | November 10, 2009

- __Unwittingly, I have deleted some comments__ :/ -
One commentator pointed out that this snippet changes the base array (it removes the first element from it).
In the other comment, someone noted that the function is even faster than the built-in one on small arrays (however, far slower on not so small ones).