Sorting Algorithms

Being able to code in an awesome language such as Ruby does not excuse one from not knowing how to reconstruct something that is already built into the language, case in point is the sort method in class Array. I will use this blog post to analyze the numerous sort algorithms and discuss why quicksort is the sort algorithm used in the Array#sort method.

Before I dig into each specific sorting algorithm, I want to lay down some ground-rules and prevent any ambiguities or confusion. Each algorithm will sort an unordered array from the smallest value to the largest value ordered from left to right.

Bubblesort

Bubblesort is a simple search algorithm where an array is sorted by comparing adjacent pairs of elements and swapping the element positions if the left element is greater than the right element. Each step-through of the array will always yield the correct position for the next largest value in the array, thus the next largest value is ‘bubbled’ to the right. This can be illustrated with a simple example.

Below is the bubblesort algorithm implemented in Ruby.

Since there are n-1 + n-2 + … 2 + 1 comparisons made to execute bubblesort, the total comparisons made is (n-1)(n)/2 => (n2)/2 - n/2 and since n2 dominates as the dataset becomes large, bubblesort has an efficiency of Ο(n2).

Selection Sort

Selection sort sorts an array by repeatedly stepping through an array, keeping track of the successive smallest value’s position and swapping it with the starting position of each sweep.

Below is the selection sort algorithm implemented in ruby.

Selection sort also has an efficiency of Ο(n2).

Insertion Sort

Insertion sort is a search algorithm where a new number is introduced to an already sorted array and the new number is inserted into the correct position in the sequence. An example follows:

Below is the insertion sort algorithm implemented in ruby.

Since the worst case scenario is that the array to be sorted is arranged from largest to smallest, it would take (n-1)(n)/2 steps, so insertion sort also has an efficiency of Ο(n2).

Merge Sort

Merge sort is a divide-and-conquer search algorithm where the array is broken down into smaller and smaller arrays until each number is the only element in its own array. Then each array is merged with adjacent array and this process is repeated until one long sorted array is formed.

Below is the insertion sort algorithm implemented in ruby.

Merge Sort has an efficiency of Ο(n log n).

(More algorithms to come.)