1. Computing

Sorting Arrays

By

Sorting Arrays

Sorting was a preoccupation for computer scientists from early on. There were many algorithms that came into and fell out of use and still today new algorithms are pushing the boundaries of performance. But, being a high level language, you won't be implementing sorting algorithms in Ruby if you care about performance, and besides, sorting Arrays and other collections are yet more things Ruby does for you.

Sorting in a Spaceship

Technically, sorting is a job handled by the Enumerable module. The Enumerable module is what ties all types of collections in Ruby together. It handles iterating over collections, sorting, looking through and finding certain elements, etc. And how Enumerable sorts a collection is a bit of a mystery, or at least it should remain so. The actual sorting algorithm is irrelevant, the only thing you need to know is that objects in the collection are compared using the "spaceship operator."

The "spaceship operator" takes two objects, compares them and then returns -1, 0 or 1. That's a bit vague, but the operator itself doesn't have a very well defined behavior. Let's take Numeric objects for example. If I have two numeric objects a and b, and I evaluate a <=> b, what will the expression evaluate to. In the case of Numerics, it's easy to tell. If a is greater than b, it will be -1, if they're equal it will be 0 and if b is greater than a it will be 1. This is used to tell the sorting algorithm which one of the two objects should go first in the array. Just remember that if the left hand operand is to come first in the array, it should evaluate to -1, if the right hand should be first it should be 1, and if it doesn't matter it should be 0.

But it doesn't always follow such tidy rules. What happens if you use this operator on two objects of different types? You'll probably get an exception. What happens when you call 1 <=> 'monkey'? This will be the equivalent of calling 1.<=>('monkey'), meaning the actual method is being called on the left operand and Fixnum#<=> returns nil if the right hand operand is not a numeric. If the operator returns nil, the sort method will raise an exception. So, before sorting arrays make sure they contain objects that can be sorted.

Second, the actual behavior of the spaceship operator isn't defined. It's only defined for some of the base classes, and for your custom classes it's totally up to you what you want them to mean. If you have a Student class you can have student sort by last name, first name, grade level or combination of that. So always be aware that the behavior of the spaceship operator and sorting is not well defined for anything but the base types.

Performing a Sort

You have an Array of Numeric objects and you'd like to sort them. There are two primary methods to do this: sort and sort!. The first creates a copy of the array, sorts it and returns it. The second sorts the array in place.


a = [1, 3, 2]
b = a.sort  # Make a copy and sort
a.sort!  # Sort a in place

That's pretty self-explanatory. So let's take it up a notch. What if you don't want to rely on the spaceship operator? What if you want a completely different behavior? These two sorting methods take an optional block parameter. That block takes two parameters and should yield values just as the spaceship operator does: -1, 0 and 1. So, given an array we want to sort it so all values that are divisible by 3 come first, and all others come after. The actual order doesn't matter here, just that those divisible by 3 come first.


(0..100).to_a.sort{|a,b| a%3 <=> b%3 }

How does this work? First, note the block argument to the sort method. Second, note the modulo divisions done on the block parameters, and the reuse of the spaceship operator. If one is a multiple of 3, the modulo will be 0, otherwise it will be 1 or 2. Since 0 will sort before 1 or 2, only the modulo matters here. Using a block parameter is particularly useful in arrays that have more than one type of element, or when you want to sort on custom classes that don't have a defined spaceship operator.

One Final Way to Sort

There is one more sort method, called sort_by. However, you should first understand translating arrays and collections with map before tackling sort_by.

©2014 About.com. All rights reserved.