JavaScript Selection, Insertion and Bubble Sort Algorithms

A Sorting Algorithm is used to rearrange a given array or list elements according to a comparison operator on the elements. The comparison operator is used to decide the new order of element in the respective data structure. Let’s take at 3 different algorithms.

Selection Sort

compare the element to the next one and swap if the value is smaller

The first Iteration we want to find the smallest value and swap to the beginning of our array, so we pick the first item. Then we compare it with the second item. If the second item is smaller, we swap it with the first. And so on, we compare this first item with every item in the array.

Once we know we have the smallest item, we switch to the second element, and we compare it with every item in the array, ignoring index 0, since we already know that’s the minimum. And so on, until the end of the array.

function sselectionSort(arr){
    for(let i = 0; i < arr.length; i++){
        let lowest = i;
        for(let j = i+1; j < arr.length; j++){
            if(arr[j] < arr[lowest]){
                lowest = j;
            }
        }
        if(i !== lowest){
            //SWAP!
            let temp = arr[i];
            arr[i] = arr[lowest];
            arr[lowest] = temp;
        }
    }
    return arr;
}

Worst Case Time Complexity: O(n*n).

Best Case Time Complexity: O(n*n).

Space Complexity: O(1)

Insertion Sort

Insertion is sorting an array by dividing the array into a ‘sorted’ portion and ‘unsorted’ portion. Then we compare the unsorted item to see if it is larger than the previous element, if not we insert the new item. Basically we are looking from left to right and sorting as we go.

we start at index 2 and compare with the let side and swap if the value is smaller

function insertionSort(arr){

    for(let i = 1; i < arr.length; i++){
       let currentVal = arr[i];
        for(let j = i - 1; j >= 0 && arr[j] > currentVal; j--) {
            arr[j+1] = arr[j]
        }
        arr[j+1] = currentVal;
    }
    return arr;
}

insertionSort([2,1,9,76,4])

1- We have a for loop looping over each element of the array, and we will do our sorting inside of it and we Set up current value to a variable.

2- We assign j the value of our current array position minus 1 and evaluate it against if it is greater than 0 and if the current element is smaller than the starting loop element.

Finally we add assign the value currentVal to the current index position in the array. Using j+1 because we are initially setting the value of j to i-1.

Worst Case Time Complexity: O(n*n).

Best Case Time Complexity: O(n*n).

Space Complexity: O(1)

Bubble Sort

Bubble sort is an algorithm that compares the next elements and swaps their positions if they are not in the intended order. The order can be ascending or descending.

comparing the element to the next one and swap if the element is lesser

How it works ?

1. Starting with the first element, compare to the next element.

2. If the current element is greater than the next element of the array, swap them.

3. If not just move to the next element and Start again from Step 1

function bubbleSort(arr){
  let bubbleSort = (inputArr) => {
    let len = inputArr.length;
    for (let i = 0; i < len; i++) {
        for (let j = 0; j < len; j++) {
            if (inputArr[j] > inputArr[j + 1]) {
                let temp = inputArr[j];
                inputArr[j] = inputArr[j + 1];
                inputArr[j + 1] = tmp;
            }
        }
    }
    return inputArr;
};

Worst Case Time Complexity: O(n*n).

Best Case Time Complexity: O(n). When array is already sorted.

Space Complexity: O(1)