This content originally appeared on DEV Community and was authored by Aravind V
In this article we will deepdive into the various sorting algorithms and try to implement it in typescript by summarising my learnings.
The sorting can be performed with the below 5 approaches:
- Bubble sort
- Selection sort
- Insertion sort
- Merge sort
- Quick sort
These sorting algorithms can be explained in two ways based on order required, here let us assume we need ascending order only.
🍃 Simple utility functions used in this article
This function will be used to swap two numbers in a given array with indexes.
function swapTwo(list: number [],a: number, b: number){
[list[a], list[b]] = [list[b], list[a]];
}
This function will be used to compare and sort two numbers in a given array with indexes.
function sortTwo(list: number [],a: number, b: number){
if (list[a] < list[b]) {
swapTwo(list, a, b);
}
}
🎾 Bubble Sort
This is the simplest sorting algorithm that works by swapping the adjacent elements if they are not in the expected order.
If we have total N elements, then we need to repeat the above process for N-1 times.
Pseudo code steps for Bubble sort
- Start iterating through the array, comparing 2 elements at a time, swap them if they are not in the expected order.
- At the end of first pass, ignore the last index in the next pass.
- Continue these passes until the last index is the same as the first index, assuming that the list is fully sorted.
function bubbleSort(arr: number []):number [] {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length +i -1; j++) {
sortTwo(arr, j+1, j);
}
}
return arr;
}
🔭 Selection Sort
This algorithm maintains tries to perform sorting by maintaining two parts in a given array during the processing:
- first part which is already sorted and
- remaining part which is unsorted.
During every iteration we identify the minimum element from the unsorted part and swap it to the beginning of the unsorted part.
Then at the end of every iteration, this minimum element from the unsorted part is picked and moved to the end of the sorted part.
Pseudo code steps for Selection Sort
- Let us assume that the first element is the smallest.
- Find the minimum value from the unsorted array, and swap this with the first element of the array.
- Now repeat the above two steps for the rest of the unsorted array elements excluding the first element swapped to the front of the array till the unsorted part length turns to 1, by then you can add that to the end of the sorted part and completed the sorting.
function selectionSort(arr: number []):number [] {
let min: number;
for (let i = 0; i < arr.length; i++) {
min = i;
for (let j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
if (min !== i) {
swapTwo(arr, min, i);
}
}
return arr;
}
📌 Insertion Sort
The is like selection sort, where there is a portion of the array that is always sorted and a section that remains unsorted.
It places an unsorted element at its suitable place in each turn.
This is most useful when there is a scenario wherein you are receiving a series of numbers in real time, and transform them to a sorted array.
Pseudo code steps for Insertion Sort
- Start by comparing the 2nd element with the 1st element, swap if necessary.
- For each new element, iterate through the sorted portion of the array, and insert this element where it needs to be, by making comparisons, just like playing cards.
- Keep doing this until all the unsorted elements have been inserted into their correct positions.
function insertionSort(arr: number[]):number [] {
for (let i = 1; i < arr.length; i++) {
for (let j = i - 1; j > -1; j--) {
sortTwo(arr, j+1, j);
}
}
return arr;
}
⏰ Time and space complexity traits.
The above sorting algorithms more or less shares the below complexity traits.
- time complexity
O(N^2)which turns out to be inefficient when N is large. - space complexity
O(1)minimum due to minimum number of swaps.
Both of other sorting algorithms discussed below has an average time complexity of O(n * log n) and are recommended for large datasets.
Their space complexities varies depending on the technique used.
🍀 Merge Sort
Merge sort is used when the data structure doesn’t support random access since it works with pure sequential access that is forward iterators, rather than random access iterators. That is fast in the case of a linked list, since for accessing any data at some index we need to traverse from the head to that index and merge sort accesses data sequentially and the need of random access is low.
This sorting algorithm is based on Divide and Conquer algorithm.
Here we divide the input array into two halves recursively until any part is having more than 1 elements. Then we perform sort for the two halves, eventually we merge the two sorted halves.
The main concept here is that if we are able to split our array into smaller subarrays of size 0 or 1, and merge them correctly, we have sorted our array!
We need to find a way to divide an array into halves continuously, until we end up with arrays of size 0 or 1. Then, we merge them in a way that results in a larger (but still sorted) array.
It is widely used for external sorting, where random access can be very, very expensive compared to sequential access.
External sorting is a term for a class of sorting algorithms that can handle massive amounts of data. External sorting is required when the data being sorted do not fit into the main memory of a computing device (RAM) and instead, they must reside in the slower external memory (hard drive).
The main advantage of the merge sort is its stability, the elements compared equally retain their original order.
This sorting algorithm has two phases as follows:
- sorting phase, dividing into chunks of data small enough to fit in main memory are read, sorted, and written out to a temporary file.
We use recursion to do this. Use
sliceto halve the array, and do this until the base case oflist.length ≤ 1is reached. - merge phase, the sorted sub-files are combined into a single larger file.
The helper function to implement the merging of 2 subarrays, has space complexity of O(n).
Pseudo code to perform mergesort of two arrays (of size≤1) such that we end up with a sorted array.
- Start by making an empty array
- Compare the first elements of the 2 subarrays, and push the smaller of the two, to the the new array.
- Suppose 1st element of 1st array is smaller, then push that to the new array.
- Now compare the 2nd element of the first array to the 1st element of the 2nd array, and so on.
- If we have exhausted the array elements in any of the 2 subarrays, then just push the other subarray to the new array we had created.
function merge(list1: number[], list2: number[]):number [] {
let merged:number [] = [],
i:number = 0,
j:number = 0;
while (i < list1.length && j < list2.length) {
if (list1[i] < list2[j]) {
merged.push(list1[i]);
i++;
} else {
merged.push(list2[j]);
j++;
}
}
while (i < list1.length) {
merged.push(list1[i]);
i++;
}
while (j < list2.length) {
merged.push(list2[j]);
j++;
}
return merged;
}
Merge helper function defined above will be used to perform mergesort as follows.
function mergeSort(list:number []):number [] {
if (list.length <= 1) return list;
let mid = Math.floor(list.length / 2);
let left:number [] = mergeSort(list.slice(0, mid));
let right:number [] = mergeSort(list.slice(mid));
return merge(left, right);
}
🚤 Quick Sort
This sorting algorithm is also based on Divide and Conquer algorithm. It picks an element as pivot value and partitions the given list around the choosen pivot. After partitioning the list, the quicksort is applied recursively to both parts of the actual array. i.e., sublist to the left of the pivot and sublist to the right of the pivot.
To implement quick sort’s algorithm we need to assume the index for the pivot recursively. It works by choosing a pivot element, and making sure that all the elements to the left of the pivot element is less than the pivot(not necessarily sorted, they just need to be less than the pivot) and that all the elements to the right of the pivot are all greater than it.
Initially, we assume the pivot to 0th element in the array for this example.
The getPivotIdx helper function to correctly return the index for the pivot element is as follows.
- Choose the pivot initially, and store its index in a variable, let’s say pivotIndex. Loop through the array, if the current element is less than than the pivot, then increment the pivotIndex, and swap the current element with the element present at the new pivotIndex
- After one iteration through the array, swap the pivot with the element present at the pivotIndex.
function getPivotIdx(arr:number [], start:number = 0, end:number = arr.length - 1):number {
let swapIdx:number = start;
let pivotValue:number = arr[start];
for (let i = start + 1; i <= end; i++) {
if (arr[i] < pivotValue) {
swapIdx++;
swapTwo(arr, i, swapIdx);
}
}
swapTwo(arr, start, swapIdx)
return swapIdx;
}
Once we create the above partition helper function, we need to recursively place all the pivot elements at their correct positions.
Assume left side of pivot indicates the start of a subarray, and right indicates the last index of the subarray.
Do the following only if the left pointer is at a lesser index than the right pointer:
Pseudo code to perform quicksort by making use of the partition helper function defined above recursively.
- Start by calling the
getPivotIdxon the entire array by defaulting the left and right pointers to the first and last element of the array respectively. - Then store the return value in the pivotIndex
- Use this to recursively use
quickSortwith the same array, but from leftup until(pivotIndex-1), for the left part of the array. - For the right part of the array, use
quickSortagain, with the same array, but from(pivotIndex + 1)upto right - Once the base case becomes invalid, when left equals right , eventually we return the array.
function quickSort(arr:number [], left:number = 0, right:number = arr.length - 1):number [] {
if (left < right) {
let pivotIndex = getPivotIdx(arr, left, right);
quickSort(arr, left, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, right);
}
return arr;
}
Quick sort is the fastest, but it is not comes with O(N*log N) time complexity always, as there are worst cases where it may become O(N^2).
And the space complexity is O(log n).
Quick Sort in an in-place sort, so it is appropriate to use it for arrays in memory.
i.e., quicksort is more effective for datasets which fits into memory. For larger data sets it proves to be inefficient so algorithms like merge sort are preferred in that case.
🔁 Original post at 🔗 Dev Post
This content originally appeared on DEV Community and was authored by Aravind V
Aravind V | Sciencx (2022-02-21T14:55:36+00:00) ❄️ Sorting Algorithms implemented in Typescript. Retrieved from https://www.scien.cx/2022/02/21/%e2%9d%84%ef%b8%8f-sorting-algorithms-implemented-in-typescript/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.