15
Feb
09

A Simple Quicksort Implementation in Ruby

I’ve recently start playing around with Rails. In the past I’ve used mostly PHP for the server-side. My first impressions of Rails are pretty positive though. Of course, since I haven’t used Ruby before either, I’m going to need to pick up some Ruby programming skills along the way.

I decided to start with something pretty basic: Quicksort. Here is a very simple implementation based entirely off of the algorithm from Cormen, Leiserson, Rivest, and Stein’s book.

#!/usr/bin/ruby
# quicksort.rb

def quicksort(list, p, r)
    if p < r then
        q = partition(list, p, r)
        quicksort(list, p, q-1)
        quicksort(list, q+1, r)
    end
end

def partition(list, p, r)
    pivot = list[r]
    i = p - 1
    p.upto(r-1) do |j|
        if list[j] <= pivot
            i = i+1
            list[i], list[j] = list[j],list[i]
        end        
    end
    list[i+1],list[r] = list[r],list[i+1]
    return i + 1
end

# Testing it out
a = [9,4,10,12,3,5,10,3,2,25,6,21,33,23,19,13,38,26,12,3]
quicksort(a, 0, a.length-1)
puts a

You can do a whole lot better than this of course. Check out this post by Daniel Lyons for instance comparing quicksort implementations in a whole bunch of different languages.

About these ads

1 Response to “A Simple Quicksort Implementation in Ruby”


  1. 1 lavaboom
    October 13, 2012 at 8:04 am

    Could you show me how to do a quick sort in REVERSE order (large to small)? How do I modify the above code? Really appreciate it. Thanks a lot!


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

%d bloggers like this: