Sorting Algorithms

For the past few week, I’ve wanted to switch gears from Web Development to learn a more deeper topic which is computer science! One of the topics that I focused on learning are the different sorting algorithms commonly used and the time complexity of each one. In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run, This can be expressed in using the big O notation. We will get into more details later, but first let checkout the different sorting algorithms.

Bubble Sort

The first algorithm is the bubble sort which works by repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.

Bubble Sort animation

Let think about how we can implement this in code for if we want to sort an array from smallest to largest numbers. First, we would want to iterate through the array until all of the numbers are sorted. We iterate through the whole array comparing the two numbers together and if the first number is greater than the second number than we can simply swap the two. This will go on until all of the number in the array are sorted.

const array = [5,3,40,20,100,33,6,7]
function bubbleSort(array) {
let notSorted = true;

while(notSorted) {
notSorted = false;
for(let i=0; i<array.length; i++) {
if(array[i] >= array[i+1]) {
array[i], array[i+1] = array[i+1], array[i];
notSorted = true;
}
}
}
return array;
}
bubbleSort(array);

Looking at our JS script algorithm above, we can see that we have two loops (while and for) which will take place as we iterate through the length of the array until it is sorted. As a result, we get a time complexity of O(n²) in the worst case scenario. Bubble Sort is consider to be one of the worst sorting algorithms in terms of performance. I think we can do better than that!

Inersation Sort

This algorithm is actually quite simple on paper. We simply iterate over the original array to find the current minimum value in the original array, remove it from the array, and insert into a new array. Rinse and repeat until there are no more elements left in the original array.

Insertion Sort
const array = [5,3,40,20,100,33,6,7];
function insertionSort(array){
let newArray = [];
while (array.length !==0) {
newArray.push(findMinAndRemove(array))
}
return newArray;
}
function findMinAndRemove(array){
let minNum = array[0];
let index = 0;
for (var i = 0; i < array.length; i++) {
if(array[i] < minNum) {
minNum = array[i];
index = i;
}
}
array.splice(index, 1)
return minNum;
}
insertionSort(array);

In the Insertion Sort algorithm, we have two functions that takes in the array as an argument. In the insertionSort function we call the findMinAndRemove function which will allow us to return the minimum value from our original array and add it to the new array. The findMinAndRemove function works by iteration over all of the elements in the original array and comparing each element with the minNum placeholder. If it finds the minimum value of the array, then it reassigns the minNum placeholder with the new value. We return the new minNum variable containg the minimum value of the array after our iteration. The insertionSort will continue to call the findMinAndRemove function until there is nothing left in the original array which in that case we can exit out of the while loop to return our new array with the sorted elements! The time complexity of this is O(n²) in the worst case scenario. Still not quite ideal, lets move on…

Merge Sort

The merge Sort is one of the tricker algorithm due to it’s recursive call. The merge sort algorithm sorts a list in two main steps. First, it takes an unordered list and continue splitting the list into smaller and smaller subarrays until the subarrays each one element. Second, it couples up the neighboring lists and merge them together. While the merge operation only applies to sorted lists, when the list has only one element in it, it is automatically sorted.

Merge Sort
const array = [5,3,40,20,100,33,6,7];
function mergeSort(array) {
if (array.length <2)
return array;
let middlePoint = array.length/2;
let firstSubarray = array.slice(0, middlePoint);
let secondSubArray = array.slice(middlePoint, array.length);
return merge(mergeSort(firstSubarray), mergeSort(secondSubArray));
}
function merge(firstSubarray, secondSubArray) {
let result = [];
while(firstSubarray.length && secondSubArray.length) {
if (firstSubarray[0] <= secondSubArray[0]) {
result.push(firstSubarray.shift());
} else
result.push(secondSubArray.shift());
}
while (firstSubarray.length) {
result.push(firstSubarray.shift());
}
while (secondSubArray.length) {
result.push(secondSubArray.shift());
}
return result;
}
mergeSort(array);

Just like our Insertion Sort, this algorithm is split up into two parts. In the mergeSort function, we use recursion to split up our array into sub arrays. This is done by finding the middle point of the array’s length divided by two. The firstSubarray variable is from the starting element up until the middle point. The secondSubArray variable is from the middle point to the end of the array. This recursive call will continue to split our array until there is only one element in our array. At the same time it calls our mergeSort function.

In the mergeSort function, we compare first elements in the from the FirstSubarray and the secondSubArray to see which value is less than. Then, we can use the shift method to take out that element and use the push method to insert it into our new array. This continues until there is no elements left into the FirstSubarray or secondSubArray.

Calculating the time complexity for this algorithm is tricky since we have multiple steps. First, looking at mergeSort which splits the our array that has a length of 8, we divide this array by 2 three times(8/2 = 4/2 = 2/2 =1) until we are left with one element. This is a time complexity of log(n). Now factoring in our merge function which finds the smallest elements of our subarrays, this is n. Therefore overall this algorithm is n log(n).

Compare the big o of Merge Sort with that of Insertion and Bubble Sorts. Remember that Insertion and Bubble Sorts cost us n². Well in this example of sorting an array of eight elements n log n = 24 while n² = 64. Once we arrive at a size where n = 1000 then n² = 1,000,000 while n log n = 9,965. So when is one thousand selection sort takes over a hundred times longer than merge sort. That is significant!