Bubble Sort, Insertion Sort, Selection Sort are three quadratic algorithms that I recently came across. They are called quadratic algorithms because the average time complexity for all these sorts are O(n²). They are sometimes referred to as elementary algorithms because they are the first sorting algorithms that many developers may come across.
I wanted to just share the code for the sorting algorithms for any one who is interested. I will discuss the time and space complexities of the three Sorts below.
Bubble Sort
function bubbleSort(arr){
const swap = (arr,one,two)=>{
[arr[one],arr[two]] = [arr[two],arr[one]]
}
for (var i=arr.length;i>0;i--){
for(var j =0;j<i-1;j++){
if(arr[j]>arr[j+1]) swap(arr,j,j+1)
}
}
return arr
}Insertion Sort
function insertionSort(arr){
var currentVal;
for(var i = 1; i < arr.length; i++){
currentVal = arr[i];
for(var j = i - 1; j >= 0 && arr[j] > currentVal; j--) {
arr[j+1] = arr[j]
}
arr[j+1] = currentVal;
}
return arr;
}Selection Sort
function selectionSort(arr) {
const swap = (arr, idx1, idx2) =>
([arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]]);
for (let i = 0; i < arr.length; i++) {
let lowest = i;
for (let j = i + 1; j < arr.length; j++) {
if (arr[lowest] > arr[j]) {
lowest = j;
}
}
if (i !== lowest) swap(arr, i, lowest);
}
return arr;
}The time complexity of all three Sorting Algorithms on average is O(n²), but the best case scenario of Bubble Sort and Insertion Sort is O(n). Bubble Sort works by swapping the adjacent elements if they are in the wrong order. If the data given to Bubble Sort was already sorted data array, then there is no swapping involved at all. Bubble Sort will approach O(n) time complexity as it only has to navigate through the array once.
Insertion Sort takes the data given to the algorithm by building a sorted array one item at a time. During each iteration, the first of the remaining element of the array is only compared with the right-most element of the sorted subsection of the array. An already sorted array will allow Insertion Sort to finish its sorting after going through the entire array just once and hence, O(n) time complexity.
The time complexity for Selection Sort at best is O(n²). Selection Sort will iterate through the array each time for the smallest value and make a comparison against each element. While Bubble Sort and Insertion Sort will only iterate through the array once for arrays that are already sorted, Selection Sort needs to make comparisons for the selected element against every element. Selection sort will always have a time complexity of n(O²).
Space complexities for all three elementary algorithms are the same. Not a lot of space is being used. No new arrays or new variables are being created.
Bubble Sort, Insertion Sort, Selection Sort are roughly equivalent in the grand scheme of things. They are relatively easier to understand than the harder algorithms that have better time complexities. They have good space complexities because they are not adding new arrays or variables to help with the sorting. Bubble Sort and Insertion sort also perform better on nearly sorted data because the time complexities of both algorithms approaches O(n) as inputted data becomes more sorted.
Please find more resources for the sorts below in the references section.
Cheers!
References
