Sorting Algorithms in JavaScript

Sorting in general is arranging 'things' in a particular order. This particular order can either be ascending or descending. Sorting algorithms are instructions to define the particular order in which you want the 'things' sorting.

There are many different sorting algorithms, but in this article I will be discussing Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort and efficiency of each.

Bubble Sort // O(n^2) - nested loops

• Start by comparing the first two elements in an array, swap them if required.
• Continue until the end of the array swapping elements.
• Repeat steps until no more swaps required

Code snippet:

const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0]


function bubbleSort(array) {
    for (let i=0; i<array.length; i++) {
        for (let j=0; j<array.length; j++) {
            if (array[j]>array[j+1]) {
                let temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp
            }
        }
    }


} // O(n^2) - here we have nested loops to compare each element and bubble up through 


bubbleSort(numbers);
console.log(numbers);        

Selection Sort - O(n^2) nested loops

• Assume the first element in the array is the smallest (for ascending order)
• From the remaining elements in the array, find the small value and swap it with the first element.
• Repeat the steps with the rest of the array comparing elements to the right.

Code Snippet

const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0]


function selectionSort(array) {
    for (let i=0; i<array.length; i++) {
        let min = i;
        let temp = array[i];
        for (let j=i+1; j<array.length; j++) {
            if (array[j]<array[min]) {
                min = j;
            }
        }
        array[i] = array[min];
        array[min] = temp;
    }
} //O(n^2) - nested loops again. 


selectionSort(numbers);
console.log(numbers);        

Insertion Sort - O(n^2) nested loops

• Iterate from array[1] to array[n] over the array.
• Compare the current element to the previous element. If it is smaller, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.
• This method can be thought of as rearranging playing cards in your hand. Moving left to right, as soon as the current element is smaller than the previous one, move that element to the correct position.

Code Snippet

const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0];


function insertionSort(arr){
    //Start from the second element.
    for (let i = 1; i < arr.length; i++) {
        //Go through the elements behind it.
        for (let j = i - 1; j > -1; j--) {
            if (arr[j + 1] < arr[j]) {
                let temp = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = temp
            }
        }
    }
  return arr;
}


insertionSort(numbers);
console.log(numbers);        

Merge Sort - O(n*log(n)) DIVIDE & CONQUER Technique

• Split the array into individual elements.
• Compare the individual elements and arrange them in order using recursion. This is a tree like structure and so we can use recursion here.
• Make an empty array.
• Compare the elements of the subarrays and push the smaller value to the empty array.
• Continue until all subarrays have been covered and you have one sorted array.

Code Snippet

const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0]


function mergeSort(array) {
    //base case
    if (array.length === 1) {
        return array
      }
    //split array into right and left
    const middle = Math.floor(array.length / 2);
    const left = array.slice(0,middle);
    const right = array.slice(middle);
    //use recursion here to keep splitting array until length 1. 
    return merge(
    mergeSort(left),
    mergeSort(right)
  )
}


function merge(left, right){
    const result = [];
    let leftIndex = 0;
    let rightIndex = 0;
    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex] < right[rightIndex]) {
            result.push(left[leftIndex]);
            leftIndex++
        } else {
            result.push(right[rightIndex]);
            rightIndex++
        }
    }
    return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}


const answer = mergeSort(numbers);
console.log(answer);        

Quick Sort - O(n*log(n)) DIVIDE & CONQUER Technique

Quick sort is another divide & conquer algorithm which picks an element as pivot and partitions the given array around the picked pivot.

There are many different versions of quick sort that pick the pivot in different ways e.g.

• choosing the first element
• choosing the last element
• choosing a random element
• picking the median

This method can be quite complex and cumbersome and so I've omitted the implementation of this. More information on this can be found here: https://www.geeksforgeeks.org/quick-sort/

Some Rules to follow and think about:

• Insertion Sort - Should only be used when you have a small input of items or if the items are already mostly sorted. It's very fast in these cases and uses little space and easy to implement code.
• Bubble Sort - Never use it. Only used for educational purposes.
• Selection Sort - Never use it. Only used for educational purposes.
• Merge Sort - It is very good due to divide and conquer. Best, average and worst case the time complexity is O(n*log(n)). So if you are worried about worst case scenarios, then you should use merge sort as we can guarantee the time complexity. Merge sort is however O(n) for space complexity and so is expensive on memory.
• Quick sort - It is actually better than merge sort in pretty much most cases. It has a better space complexity too of O(n*log(n)) and average and best time complexity of O(n*log(n)). It is a pretty popular sorting algorithm, but we do need to be careful. If the pivot isn't picked properly, then in the worst case we can have really slow sorting of O(n^2)
• Heap sort is another algorithm that is similar to quick sort but has a better space complexity and doesn't have the O(n^2) worst behaviour like quick sort. Most of the time however, quick sort is faster and wins out most of the time. See here for more info: https://stackoverflow.com/questions/2467751/quicksort-vs-heapsort

Overview & additional information

With an understanding of sorting algorithms, software developers can figure out the appropriate sorting algorithm to use depending on the data set, the time required, and the space available.

Although merge sort and quick sort are harder to implement, they are the most often used sorting algorithms in real life. They use divide and conquer to get O(n*log(n)) time complexity.

In JavaScript, the sort() method uses insertion sort and so is not suitable for large data sets. That is why when we deal with large data sets, we should consider other sorting algorithms.

Mathematically it is impossible to be quicker than O(n*log(n)) due to making comparison sorts, but there are a small selection of inputs which are non-comparison sorts.

• Counting Sort
• Radix Sort

This is an entirely different way to think about sorting and these methods have better time complexities. It can get very complex and not worth myself knowing for the time being but it is useful to know they are options and this exists.