Sorting Algorithms

Sorting involves arranging data in a collection based on a comparison algorithm.

There are two general families of sorting algorithms;
1.Linear Sorting - treat the problem of sorting as a single large operation
2.Divide and Conquer - partition data to be sorted into smaller sets that can
be independently sorted.

The performance of sorting algorithms can be measured in terms of:
1.Comparisons - number of times two values of an input array are compared for relative equality.
2.Swaps - number of times two values stored in the input are swapped.

I am going to show you the implementation of 5 sorting algorithms in JavaScript:

Bubble sort
Selection Sort
Insertion Sort
Merge Sort
Quick Sort

I found this site really helpful in visualizing these algorithms.

Bubble Sort

This is the simplest.
It works by repeatedly swapping values if they are the wrong position. Higher values are generally to the right and lower values are to the left.

Pseudocode

set swap counter to a truthy value
Repeat until the swap counter is a falsy value
Reset swap counter to a falsy value
    Look at each adjacent pair
        If two adjacent elements are not in order
        Swap them and set swap counter to truthy value

Code

function bubbleSort(arr) {
    let swapCounter = 1;

    while (swapCounter) {
        swapCounter = 0;
        for (let i = 0; i < arr.length - 1; i++){
            if (arr[i] > arr[i + 1]) {
                const swapElement = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = swapElement;
                swapCounter = 1;
            }
        }
    }

    return arr;
}

let arr = [64, 34, 25, 12, 22, 11, 90];
console.log(bubbleSort(arr)) 
// >> [11, 12, 22, 25,34, 64, 90]

Performance
Worst case - O(n^2)
Best case - O(n^2)

Selection Sort

It works by finding the smallest unsorted element and add it to the array in the first unsorted location

Pseudocode

Repeat until no sorted element remains:
    Search the unsorted part of the data to find the smallest value
    Swap the smallest value with the first element of unsorted part

Code

function selectionSort(arr){
    for (let i = 0; i < arr.length; i++){
        for (let j = i + 1; j < arr.length; j++){
            if (arr[j] < arr[i]) {
                const swapElement = arr[i];
                arr[i] = arr[j];
                arr[j] = swapElement;
            }
        }
    }

    return arr;
}



let arr = [4, 2, 5, 1, 3];
console.log(selectionSort(arr))
// >> [1, 2, 3, 4, 5]

Performance
Worst case - O(n^2)
Best case - O(n)

Insertion Sort

This algorithm sorts items are they are encoumtered

Pseudocode

Call the first element of the array 'sorted'
Repeat until all the elements are sorted :
    Look at the next unsorted element . Insert into the 'sorted' position by
    shifting the required number of elements

Code

function insertionSort(arr) {
    for (let i = 1; i < arr.length; i++){
        let unsorted = arr[i];
        let idx = i - 1;

        while (idx >= 0 && unsorted < arr[idx]) {
            arr[idx + 1] = arr[idx];
            idx -= 1;
        }
        arr[idx + 1] = unsorted;
    }
    return arr;
}

let arr = [4, 2, 5, 1, 3];
console.log(insertionSort(arr)) 
// >> [1, 2, 3, 4, 5]

Perfomance
Worst case - O(n^2)
Best case - O(n)

Merge Sort

Works by recursively splitting an array into two, sorting them and then combining these arrays in a sorted order

Pseudocode

Sort the left half of the array (Assuming n > 1)
Sort the right half of the array (Assuming n > 1)
Merge the two halves together

Code

function mergeSort(arr) {
    let length = arr.length

    // if  n is not > 1 
    // list is considered sorted
    if (length === 1) {
        return arr;
    }

    let midIdx = Math.ceil(length / 2);
    let leftHalf = arr.slice(0, midIdx);
    let rightHalf = arr.slice(midIdx, length);

    leftHalf = mergeSort(leftHalf);
    rightHalf = mergeSort(rightHalf);

    return merge(leftHalf, rightHalf)
}

// merge both halfs 
function merge(leftHalf, rightHalf) {
    const sorted = []
    while (leftHalf.length > 0 && rightHalf.length > 0) {
        const leftItem = leftHalf[0]
        const rightItem = rightHalf[0]

        if (leftItem > rightItem) {
            sorted.push(rightItem)
            rightHalf.shift()
        } else {
            sorted.push(leftItem);
            leftHalf.shift()
        }
    }

    // if left half is not empty
    while (leftHalf.length !== 0) {
        sorted.push(leftHalf[0])
        leftHalf.shift()
    }

    // if right half is not empty
    while (rightHalf.length !== 0) {
        sorted.push(rightHalf[0])
        rightHalf.shift()
    }

    return sorted;
}

let arr = [4, 2, 5, 1, 3];
console.log(mergeSort(arr)) 
// >> [1, 2, 3, 4, 5]

Performance
Worst case - O(nlogn)
Best case - O(nlogn)

Quick Sort

Pseudocode

Repeat until sorted
    Pick a pivot value and partition array
    Put all value smaller than pivot to the left and larger values to the right
    Perform pivot and partition on the left and the right partition

Code

function swap(arr, leftIndex, rightIndex) {
    const temp = arr[leftIndex];
    arr[leftIndex] = arr[rightIndex];
    arr[rightIndex] = temp;
}

function partition(arr, left, right) {
    let pivot = arr[Math.floor((right + left) / 2)], //middle element
        i = left, //left pointer
        j = right; //right pointer
    while (i <= j) {
        // while left pointer is less than pivot
        // move pointer to the right
        while (arr[i] < pivot) {
            i++;
        }
        // while righ pointer is greater than pivot
        // move pointer to the left
        while (arr[j] > pivot) {
            j--;
        }

        // if left pointer is less than or equal to right pointe
        // swap elements
        // increment left pointer n decrement right pointer
        if (i <= j) {
            swap(arr, i, j); //sawpping two elements
            i++;
            j--;
        }
    }
    return i; // index of left pointer
}

function quickSort(arr, left, right) {
    let index;
    if (arr.length > 1) {
        index = partition(arr, left, right); //index returned from partition
        if (left < index - 1) { //more elements on the left side of the pivot
            quickSort(arr, left, index - 1);
        }
        if (index < right) { //more elements on the right side of the pivot
            quickSort(arr, index, right);
        }
    }
    return arr;
}


let arr = [4, 2, 5, 1, 3];
console.log(quickSort(arr, 0, arr.length - 1));
// >> [1, 2, 3, 4, 5]

Perfomance
Worst Case - O(n^2)
Best Case - O(nlogn)

Note: Bubble sort, insertion sort and selection sort are linear sorting algorithms while merge sort and quick sort are divide and conquer algorithms.

Happy coding 😉

Blog

Ivy-Walobwa

Bubble Sort

Selection Sort

Insertion Sort

Merge Sort

Quick Sort

Join Our Newsletter. No Spam, Only the good stuff.

Related