Different Types of Sorting Algorithms

Hey everyone! In this blog, I wanted to discuss different types of sorting algorithms. These are important to understand and solve coding algorithms. Before I begin to explain the different types let me begin with answering the question, what even is ‘sorting’? Sorting is the process of rearranging the items in a collection (in an array) so that items are in some kind of order. An example could be sorting numbers from smallest to largest, or sorting names alphabetically, or sorting movies based on the year they were released, and so on. With that let's begin discussing some different types!

Merge Sort

Merge sort is a combination of merging and sorting. It exploits the fact that an array of 0 or 2 elements is always sorted. Merge sort works by decomposing an array into smaller arrays of 0 or 1 elements, then building a new sorted array. In order to implement merge sort, it's useful to first implement a function responsible for merging two sorted arrays. Then given the two arrays that are sorted, a helper function should create a new array that is also sorted, and consists of all the elements in the two input arrays. The function should run in O(n+m) time and O(n+m) space and should not modify the parameters passed to it. The Big O of merge sort is → O(n log n). However, Merge Sort takes up a lot more space complexity.

Quick Sort

Quick sort exploits the fact that arrays of 0 or 1 element are always sorted. Quick sort works by selecting one element called the pivot and finding the index where the pivot should end up in one sorted array. Once the pivot is positioned appropriately, the quick sort method can be applied on either side of the pivot. The Big O of quick sort is → O(n log n).

Radix Sort

Radix sort is a special sorting algorithm that works on lists of numbers. It never makes comparisons between elements. It exploits the fact that information about the size of a number is encoded in a number of digits. More digits mean a bigger number. In order to implement radix sort, it's helpful to build a few helper functions such as first getDigit(num, place)- returns the digit in num at the given place value. The Big O of radix sort is → O(n)k → where the length of number n→ length of the array.

Bubble Sort

Bubble sort is a sorting algorithm where the largest values ‘bubbles’ to the top. As we loop through each item we compare the current item to the following item. Is this larger than the current item if yes then swap the two. The pseudocode goes like this. Start by looping from the end of the array towards the beginning with a variable called I. Start an inner loop with a variable called j from the beginning until i-1.If arr[j] is greater than arr[j+1], swap those two values! Bubble sort optimization → last time through did we make any swaps if not then stop. Big O Complexity → N²

Selection Sort

Selection sort is similar to bubble sort, but instead of placing large values into sorted position, it places small values into sorted position. Store the first element as the smallest value you’ve seen so far. Compare this item to the next item in the array until you find a smaller number. If a smaller number is found, designate that smaller number to be the new “minimum” and continue until the end of the array. If the “minimum” is not the value (index) you initially began with, swap the two values. Repeat this with the next element until the array is sorted. Store the first element as the smallest value you’ve seen so far. Compare this item to the next item in the array until you find a smaller number. If a smaller number is found, designate that smaller number to be the new “minimum” and continue until the end of the array. If the “minimum” is not the value (index) you initially began with, swap the two values. Repeat this with the next element until the array is sorted. The Big O of selection sort is time complexity → O(n)²

Insertion Sort

Insertion sort builds up the sort by gradually creating a larger left half which is always sorted. Start by picking the second element in the array. Now compare the second element with the one before it and swap if necessary. Continue to the next element and if it is in the incorrect order, iterate through the sorted portion (the left side) to place the element in the correct place.. Repeat until the array is sorted. The Big O Complexity → O(n)².

The screenshot above shows the Big O of sorting algorithms and is helpful to look back on. I used the Udemy Colt Steele course to understand all these and I would recommend checking it out for further clarification. Here is the link: https://www.udemy.com/course/js-algorithms-and-data-structures-masterclass/