Sorting Algorithms With Javascript
We will learn some of the basic and popular sorting algorithms. But before we directly jump on the topic let's first understand some parameters used to describe/evaluate a sorting algorithm.
Time Complexity:
The time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the input.
Space Complexity:
The space complexity of an algorithm is the amount of memory space required to solve an instance of the computational problem as a function of the length of the input.
Stability:
Consider you have an array [2, 4, 4] & let's rename it to [2, 4i, 4j] for understanding purpose. Some sorting algorithms will keep the 4 in its respective positions [2, 4i, 4j] while some sorting algorithms will swap the positions of 4 like [2, 4j, 4i] while sorting.
Algorithms which does not change the positions of equally-weighted numbers from their relative positions in the input are known to be Stable while algorithms which change the respective positions of numbers are known as UnStable
1. Selection Sort
Time Complexity
------------------------Best Case : O(n^2)Average Case : O(n^2)Worst Case : O(n^2)
------------------------Space Complexity : O(n)Stability: Stable
The sorting happens in the order of the index of an array. It first selects the position of the elements & finds outs the element that belongs to that position & hence called selection sort
2. Bubble Sort
Time Complexity
------------------------Best Case : O(n)Average Case : O(n^2)Worst Case : O(n^2)
------------------------Space Complexity: O(n)Stability: Stable
You can notice that a number jumps only one position left/right after every iteration to reach to its destination & hence its called Bubble Sort
3. Insertion Sort
Complexity
------------------------Best Case : O(n)Average Case : O(n^2)Worst Case : O(n^2)
------------------------Space Complexity: O(n)Stability: Stable
Here the array is divided into two parts sorted(left) & unsorted(right). On every iteration the first number from unsorted part is inserted in its respective index to sorted part & hence its called Insertion Sort
4. Merge Sort
Complexity
------------------------Best Case : O(nlogn)Average Case : O(nlogn)Worst Case : O(nlogn)
Space Complexity
------------------------Worst Case: O(n)Stability: Stable
Merge follows divide & conquer strategy. Here we have two functions perfoming mergeSort & merge. Sorting is basically peerformed by a merge function & hence the name MergeSort
5. Quick Sort
Complexity
------------------------Best Case : O(nlogn)Average Case : O(nlogn)Worst Case : O(n^2)
------------------------Space Complexity: O(n)Stability: Stable
QuickSort follows divide & conquer strategy. Here we consider a pivot element & consider it to be in its designated index in sorted array. All elements lesser that pivot are adjusted on left of it & passed to quicksort function & elements greater than pivot are adjusted to right & passed to quicksort function. It’s one of the fastest algorithm in most of the practical scenarios & hence its called Quick Sort
