Sorting algorithms are a well established category of algorithms that have been researched extensively for years by computer scientists, and there are many well-known sorting algorithms out there. Sorting algorithms, as the name implies, solve the problem of taking an unsorted array of values and sorting them in a particular order. To start, we will be introducing a new category of Big O while taking a look at a sorting algorithm called bubble sort.
Bubble Sort & A New Category Of Big O
Bubble sorting works by "bubbling" up the highest unsorted value to its correct position in the array. Bubble sort follows these steps: Compare the first two values in the array, if the first value is greater than the second, swap them. If not, do nothing, then move both the pointers one cell to the right and repeat until reaching the end of the array or values that have already been sorted. At this point, move the two pointers back to the first two values of the array, and repeat. Each time we pass through the array we're moving the highest value to the end; until we pass through the array without performing any swaps, meaning the array is now sorted. A JavaScript implementation of bubble sort would look like this:
// Creating the bblSort function
function bblSort(arr){
for(let i = 0; i < arr.length; i++){
// Last i elements are already in place
for(let j = 0; j < ( arr.length - i -1 ); j++){
// Checking if the item at present iteration
// is greater than the next iteration
if(arr[j] > arr[j+1]){
// If the condition is true then swap them
let temp = arr[j]
arr[j] = arr[j + 1]
arr[j+1] = temp
}
}
}
// Return the sorted array
return arr;
}
Analyzing Bubble Sort Efficiency
Let's take a look at what category of Big O Notation bubble sort would fit into, by starting with determining how many steps the algorithm takes.
During each pass through there are 2 significant steps: comparisons and swaps. As far as comparisons go, for an array containing 5 elements, the first pass through would make 4 comparisons (1 to 2, 2 to 3, 3 to 4, and 4 to 5), the second pass through would make 3 (1 to 2, 2 to 3, 3 to 4), third would make 2 (1 to 2, 2 to 3), and fourth would make 1 (1 to 2). That's a total of 10 comparisons for an array with 5 elements. In the worst case scenario, where the array is sorted in descending order and we're making it ascending, a swap would be required for each comparison, creating a grand total of 20 steps, 10 comparisons and 10 swaps. For an array of N = 10, the total number of steps in a worst case scenario grows to 90. For an array N = 20, we get 380 steps. As the size of the data increases, the number of steps the algorithm takes increases exponentially, pretty close to N2. Because of this, we refer to algorithms like this as O(N2). If you haven't read my previous post on data structures & algorithms (Sorted Arrays, Binary Search, & Big O) or aren't familiar with Big O Notation, pause here and go check it out.
O(N2)
O(N2) is considered to be a pretty inefficient algorithm, and is referred to as having quadratic time. Often, but not always, when an algorithm nests one loop inside another, it results in O(N2). Whenever you see this pattern, alarm bells should go off in your head, because it's probably worth considering whether there are any faster alternatives when you encounter such a relatively inefficient algorithm as O(N2). It may be there aren't any, but it's worth the effort to make sure when you encounter an algorithm like this. So let's try another sorting algorithm and see if we can make any improvements.
Selection Sort
With selection sort, we check each index of the array from left to right and store the index of the lowest value we encounter in a variable. Once we've determined the lowest value, we swap its value with the value with the value at the index we started the pass through at, then start another pass through of the array from the next index. Here is a JavaScript implementation of selection sort.
// Creating the selectionSort function
function selectionSort(arr) {
for(let i = 0; i < arr.length - 1; i++) {
// Finding the smallest number in the subarray
let lowestNumberIndex = i;
let j = i + 1;
for(j; j < arr.length; j++) {
if(arr[j] < arr[lowestNumberIndex]) {
lowestNumberIndex = j;
}
}
// Swapping the elements
if(lowestNumberIndex != j) {
let temp = arr[i];
arr[i] = arr[lowestNumberIndex];
arr[lowestNumberIndex] = temp;
}
}
// Return the sorted array
return arr;
}
Analyzing Selection Sort Efficiency
Selection sort contains the same 2 types of steps as bubble sort: comparisons and swaps. If we look at comparisons, we see that selection sort and bubble sort take the same amount of steps. For an array of N length, there are (N - 1) + (N - 2) + (N - 3) ... + 1 comparisons. When it comes to swaps though, selection sort makes a maximum of 1 swap per pass through, while bubble sort could potentially have to make 1 swap for every comparison. This results in the following as data size increases:
| N Elements | Max # of Steps for Bubble Sort | Max # of Steps for Selection Sort |
|---|---|---|
| 5 | 20 | 14 |
| 10 | 90 | 54 |
| 20 | 380 | 199 |
| 40 | 1560 | 819 |
| 80 | 6320 | 3239 |
As we can see from the comparison, selection sort takes about half as many steps as bubble sort, indicating selection sort is twice as fast. How would we describe this in terms of Big O? Since bubble sort was O(N2), it would be natural to think about describing selection sort as O(N2 / 2). It probably comes as some surprise, then, that selection sort and bubble sort are both classified as O(N2). This is because Big O Notation ignores constants. Instead of describing an algorithm as O(N2 / 2), we drop the "/ 2" and simply call it O(N2).
This is because Big O Notation is focused on determining the general category of an algorithm based on the long-term trajectory of the algorithms steps as the size of the data increases. This is useful because at some point as the data grows larger, an algorithm having quadratic time will always become slower than an algorithm having linear time which will always become slower than an algorithm having log time which will always become slower than an algorithm having constant time.
However, when two algorithms fall under the same classification of Big O, we've seen that that doesn't mean they'll always have the same speed. Bubble sort is still twice as slow as selection sort, even though both fall under O(N2). Big O is great for contrasting algorithms of different classifications of Big O, but within the same classification, further analysis may be required to determine which algorithm is faster.
More Optimistic Scenarios
Up to now, we've classified algorithms based primarily on how many steps they would take in a worst case scenario. This is useful, because if you are always prepared for the worst, then things will turn out okay. However, being able to consider all scenarios is an important skill to enable you to choose the most appropriate algorithm for a given real world situation. The worst case scenario isn't the only situation worth considering. To see how this may be applicable, let's explore a third sorting algorithm: insertion sort.
Insertion Sort
With insertion sort, we pass through the array and remove the value at index 1 and store it in a temporary variable, leaving a gap in the array. Then, we compare each value to the left of the gap to the value in the temporary variable. If the value to the left of the gap is greater than the temporary variable, we shift that value to the right, inherently moving the gap leftward. Once we encounter either encounter the left end of the array or a variable lower than the temporary variable, we insert the variable back into the current gap. We then repeat the process starting from the next index until the pass through gets to the final index of the array, resulting in a fully sorted array. Here is a JavaScript implementation of insertion sort:
function insertionSort(arr) {
let n = arr.length;
for (let i = 1; i < n; i++) {
// Choosing the first element in our unsorted subarray
let current = arr[i];
// The last element of our sorted subarray
let j = i-1;
while ((j > -1) && (current < arr[j])) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = current;
}
return arr;
}
Analyzing Insertion Sort Efficiency
Insertion sort involves four different types of steps: removals, comparisons, shifts, and insertions.
Comparisons
Each time we pass through the array, we compare each value to the left of our temporarily removed variable, starting at index 1 (which would be 1 comparison, then index 2 (2 comparisons), and going all the way to the end of the array. For an array of N = 5 that adds up to 10 comparisons, N = 10 adds up to 45 comparisons, and as the size of the data grows the pattern we see emerge is that for an array of N length, the number of comparisons are approximately N2 / 2.
Shifts
Shifts occur each time we move a value one cell to the right. In the worst case scenario, resorting an array that is sorted in reverse order, there will be as many shifts as comparisons, since each comparison will result in a shift to the right. N2 / 2 + N2 / 2 = N2.
Removals & Insertions
Removing and inserting the temporary variable each happen once per pass through, since there are always N - 1 passthroughs, this brings our total to N2 + 2N - 2 steps.
We already know that Big O Notation ignores constants, so we are left with O(N2 + N). However, there's another rule of Big O that we've yet to encounter. Big O only takes into account the highest order of N and ignores the rest when we have multiple orders added together. This is for the same principle as ignoring the constants. As the size of the data grows, the highest order of N is so much more significant than the rest that we just drop it.
So insertion sort will be simplified to O(N2), the same as bubble and selection sort. However, we know by digging deeper into each of these sorting algorithms that bubble sort really takes about N2 # of steps, selection sort takes about N2 / 2 # of steps, and insertion sort takes N2 + 2N # of steps. So, if we were only judging these algorithms based on their efficiency up against the worst case scenario, we would say that selection sort is the fastest, followed by bubble sort, then insertion sort. But, a real world case may not be so simple.
Optimizing For The Average Scenario
In the real world, worst case scenarios happen relatively infrequently, while average case scenarios happen most of the time. If we are sorting a randomly sorted array, the values are likely to be all over the place rather than in perfectly ascending or descending order. Let's examine the effect this has on an algorithm like insertion sort. We already know how insertion sort performs in a worst case scenario, N2 + 2N. However, in the best case scenario, where data is already sorted in ascending order, we end up making just one comparison per pass through and not a single shift, since each value is already in its correct place. When data is randomly sorted, we'll have some pass throughs where we compare and shift some, all, or possibly none of the data. For the average scenario, we probably compare and shift about half of the data. Thus, insertion sort takes N2 + 2N steps for the worst case scenario, we'd say that it takes about N2 / 2 steps for the average case scenario, and in the best case scenario takes about N steps. Compare that to selection sort, which takes N2 / 2 steps in all cases: worst, average, and best. This is because selection sort does not have any mechanism for ending a pass through early at any point. Each pass through compares every value to the right of the chosen index no matter what.
| Best Case | Average Case | Worst Case | |
|---|---|---|---|
| Selection Sort | N2 / 2 | N2 / 2 | N2 / 2 |
| Insertion Sort | N | N2 / 2 | N2 |
So which algorithm is better? Well, because the performance of insertion sort varies greatly depending on the scenario, it depends. In an average case with randomly sorted data they will perform similarly. If you have reason to believe the data you'll be dealing with is mostly sorted, insertion sort will be the better option. Alternatively, if you have reason to believe you'll be dealing with data that is mostly sorted in reverse order, selection sort will be the better option.
This is why being able to discern between the best, average, and worst case scenarios can be an important skill. Choosing the best algorithm for a given task depends on the data structure and the particular data you're dealing with. While some algorithms may be prepared to handle the worst case scenario better, average cases are what happen most of the time; or you may be dealing with data that is set up in a particular way that suits other algorithms better. Knowing what to look for is the first step towards getting there, so keep building up that knowledge and looking for ways to optimize your code so that it works best with the data you're dealing with.
If any of this stuff didn't make any sense, go back and read my previous posts on Data Structures & Algorithms and I think everything covered here will make sense. If it still doesn't make sense or I got something wrong, let me know in the comments down below. If you are interested in learning more, I'd encourage you to buy a copy of A Common-Sense Guide to Data Structures and Algorithms, by Jay Wengrow.
