Elementary sorting algorithm in Javascript

In this story am going to walk through about elementary sorting algorithm and its performance. There many type of sorting algorithm, here we are going to learn about implementing Bubble Sort, Insertion Sort & Selection sort in Javascript.

Bubble Sort

The bubble sort repeatedly traverse all unsorted elements and compare the consecutive elements then interchange each other when they are out of order.

Pseudo Code

(A is an array of elements, where N is the length of an array)
FOR I = 0 to N - 2
    FOR J = 0 to N - 2
        IF A[J] > A[J + 1]
            TEMP = A[J]
            A[J] = A[J + 1]
            A[J + 1] = A[J]
    END-FOR
END-FOR

Implementation

function bubbleSort(a) {
    const n = a.length;
    // Iteration of array till last before element 
    for (let i = 0; i < (n - 2); i++) {
        // Iteration of array till last before element 
        for (j = 0; j < (n - 2); j++) {
            if (a[j] > a[j + 1]) {
                //Swap the consecutive elements 
                let temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
    }
    return a;
}

const input = [5, 4, 2, 6, 7];
const result = bubbleSort(input);
// Expected Output: [ 2, 4, 5, 6, 7 ]

The given program will result the sorted array in ascending order. For example when the given input is [5,4,2,6,7] it will return output array as [2,4,5,6,7]

Insertion Sort

Traverse all elements in an array and insert each element within a sorted array.

Pseudo Code

(A is an array of elements, where N is the length of an array)
FOR I = 0 to N - 1
    J = 1
    WHILE J > 0 AND A[J] < A[J - 1]
        TEMP = A[J]
        A[J] = A[J - 1]
        A[J - 1] = TEMP
    END-WHILE
END-FOR

Implementation

function insertionSort(a) {
    const n = a.length;
    // Iteration of array till last element 
    for (i = 0; i < n; i++) {
        let j = i;
        // Iterate over the sorted part of array and insert the element
        while (j >= 0 && a[j] < a[j - 1]) {
            let temp = a[j];
            a[j] = a[j - 1]
            a[j - 1] = temp;
            j--;
        }
    }
    return a;
}

Selection Sort

Traverse all elements in an array and find the smallest element in unsorted array and swap it with the first element

Pseudo Code

(A is an array of elements, where N is the length of an array)
For I = 0 to N-1 do:
    leastElementIndex = I
    For J = I + 1 to N-1 do:
        If A(J) < A(leastElementIndex)
        leastElementIndex = J
        End-If
    End-For
    Temp = A(I)
    A(I) = A(leastElementIndex)
    A(leastElementIndex) = Temp
End-For

Implementation

function selectionSort(a) {
    const n = a.length;
    // Iteration of array till last element 
    for (let i = 0; i < (n - 1); i++) {
        let leastElementIndex = i;
        for (let j = i + 1; j < (a.length - i); j++) {
            // Check for least element and override least element index
            if (a[j] < a[leastElementIndex]) {
                leastElementIndex = j;
            }
        }
        // Swap elements
        let temp = a[i];
        a[i] = a[leastElementIndex];
        a[leastElementIndex] = temp;
    }
    return a;
}
selectionSort([5, 4, 2, 6, 7])
// Output : [ 2, 4, 5, 6, 7 ]

Algorithm Time Complexity Analysis

All the above mentioned sorting algorithms are inefficient algorithms, there are more advanced sorting algorithms available which will be posted in upcoming stories. The upper bound worst case complexity for all the three algorithms are Quadratic Time O (n^2) as per Big-0 Notation.

Visualization

In order to visualize the flow of above mentioned algorithms in animation, check out this geeky website by Dr Steven Halim, https://visualgo.net/en/sorting. It has visualization collection of many data structures and algorithms

Reference

https://users.csc.calpoly.edu/~jdalbey/SWE/pdl_std.html