The Science of Operations

Being able to sort a collecion of data is a fundamental part of programming. There are a variety of ways a collection can be sorted and we’ll look at a handful of the most common sorting algorithms. Generally they are differentiated by their efficiency, stability (whether the sort preserves the original order of keys with equal values), and space requirements. Ruby’s native .sort method uses the quicksort algorithm so let’s start with that one.

Also if you feel dance will help you better understand sorting algorithms I highly recommend checking out the Algorythmics. I, for one, found them highly educational about sorting and folk dance.

Quicksort

Quicksort is a divide and conquer algorithm in that it divides a larger list into sublists. The lists are made around the pivot (the red bar above). The elements greater than the pivot are in one sublist while all lower elements are in the other sublist. This pattern of organizing around a pivot then occurs recursively on the increasingly smaller sublists until they are all sorted. Here is a nice look at implementing quicksort in ruby over a few implementations.

Merge Sort

With merge sort you divide the unsorted list of n items into n sublists. Now each sublist will only have one element in it and the sublists get merged back together to produce new sublists that are ordered. They increase in size until they have all been merged back into one ordered list. You can see the process below and read more about it here.

Bubble Sort

Bubble sort works better for smaller lists. It gets very time consuming with larger lists. This is because bubble sort goes through the list and compares each adjacent item. If the pair is out of order, it switches them. Once at the end of the list it starts over and iterates over the list again, swapping adjacent items until the list is finally completely sorted.

Insertion Sort

Insertion sort takes advantage of the existing order of the input, which makes it adaptive. Like bubble sort, insertion sort is more efficient with smaller data sets. It takes the input list and goes over each element one at a time as it creates a growing sorted output list. This repeats until there are no unsorted input elements left, only sorted output elements. This sorting occurs in-place so if the next element is already the greatest one that the sort has reached, it remains in the same spot as seen above. This makes it a stable sorting algorithm as well.

Ruby Algorithms is a great resource for seeing how these algorithms can be implemented in ruby and also a way to gague when you should use which one. You can use their benchmark suite to see what would be most efficient where. Definitely worth taking a look at.