Customized Sorting

Note! This whole page is an advanced topic.

How Sorting Arrays Works

Before we get into sorting arrays, let’s ask a fundamental question: How do you sort things? If you had a set of index cards with people’s last names on them, how would you sort them into alphabetical order? You would probaby take the first card and compare it to the second card, and see if they needed to change order. Then you would compare another two cards and see if they were in the right order or needed to be switched. You would keep doing this until you had all the cards sorted.

Ruby does something very similar. When Ruby wants to sort an array of numbers or strings, it goes through the array in a systematic fashion, repeatedly comparing two elements and seeing if they need to be switched or not. Ruby does this in a very sophisticated and efficient way, but the particular method it uses is not important. The important point is: Ruby’s sort works by repeatedly comparing two elements and figuring out which one comes before the other.

How Ruby Compares Things

By default, Ruby’s sort algorithm always sorts into ascending order. Whenever it gets two items, it uses the comparison operator on them. The comparison operator looks at the two items (let’s call them a and b) and returns:

The sort operator will switch the positions of a and b if the comparison returns 1 (because that means the two items are not in the proper order). The comparison operator is written <=>. You can see it in action using irb. By the way, the comparison operator is also called the “spaceship operator” because it looks like a little flying saucer.

>> 2 <=> 5
=> -1
>> 5 <=> 5
=> 0
>> 5 <=> 2
=> 1

By the way: when Ruby uses the <=> operator on strings, it compares them in ASCII order (according to their computer encoding), so the comparison is case sensitive. This means that uppercase letters come before lowercase letters:

>> "Z" <=> "a"
=> -1

The question becomes: how can you sort an array in reverse order, or sort strings in a case-insensitive manner? Ruby lets you do this by specifying how comparison ought to be done. You put this in a do/end block after the word sort. The following code will sort an array in descending order. Try it in irb.

>> data = [5, 1, 4, 2, 3]
=> [5, 1, 4, 2, 3]
>> data.sort do |a,b| b <=> a end
=> [5, 4, 3, 2, 1]
>>

The highlighted section says that whenever the sort algorithm needs to compare two numbers, they should be put into variables a and b. The criteria for sorting should be the result of b <=> a—that is, switch the items when the second item is greater than the first item.

How would you sort an array of strings into ascending order without regard to case? Well, you need to switch items a and b if the uppercase version of a is greater than the uppercase version of b, so try this in irb and see how it works.

>> words = ["France", "egg", "Zaire", "ant", "dog", "Germany"]
=> ["France", "egg", "Zaire", "ant", "dog", "Germany"]
>> words.sort
=> ["France", "Germany", "Zaire", "ant", "dog", "egg"]
>> words.sort do |a,b| a.upcase <=> b.upcase end
=> ["ant", "dog", "egg", "France", "Germany", "Zaire"]

Note: when the code for specifying sort order fits on one line, most Ruby programmers will use { and } instead of do and end, which are used here for the sake of consistency. Using braces would make the previous two custom sorts look like this:

data.sort { |a, b| a <=> b }
words.sort { |a, b| a.upcase <=> b.upcase }

Finally! Sorting Arrays of Objects

You already know how to sort an array of integers or strings using the Array#sort method. What happens if you try to sort the inventory array? If you try reading the inventory file and then execute a line like this:

inventory = inventory.sort

You will get an error message like this:

in `sort': undefined method `<=>'

What the error message means is that Ruby knows how to compare Strings to each other when it sorts a list of words. It knows how to compare floats and integers when sorting numbers. But it doesn’t know how to compare two Inventory_item objects; there is no <=> for them.

While it is possible to create a comparison operator for your own classes, that is way beyond the scope of this course. Instead, you can solve the problem by providing a custom sort algorithm. Here are some examples:

# sort by increasing price
price_array = inventory.sort do |a, b|
  a.price <=> b.price
end

# sort by increasing quantity
qty_array = inventory.sort do |a, b|
  a.quantity <=> b.quantity
end

# sort by item name, case insensitive
value_array = inventory.sort do |a,b|
  a.name.upcase <=> b.name.upcase
end

In the first sort, the custom code tells Ruby to compare the prices of items a and b when determining whether they need to change order or not. The second sort tells Ruby to compare the quantities, and the third sort tells Ruby to compare the uppercase names in order to figure out whether the two items are in the proper order or not.

You can see a program that uses custom sorting on an inventory. For purposes of simplicity, the inventory is created in the program rather than being read from a file.

Programming Challenge

Add code to the program to sort the array in increasing order of inventory value. The inventory of a value is calculated by the price times the quantity.