Documenting my path on becoming a Rails Developer.
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 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.
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 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.
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 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.