Common Sorting Algorithms in JavaScript
Tags: javascript, beginners, webdev, algorithms
Published: 2020-08-07 00:04:24

In this article, I will cover some common sorting algorithms in computer science. Sorting algorithms are important to study because they can often reduce the complexity of a problem. They also have direct applications in searching algorithms, database algorithms, and much more. 

Sorting algorithms we will learn about:
- Bubble Sort
- Selection Sort
- Insertion Sort
- Merge Sort
- Quick Sort
- Bucket Sort

## Helper Methods for Swapping and Comparing
We will be swapping elements in arrays a lot so let's start by writing a helper method called swap:
```javascript
function swap(arr, a, b) {
    let temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}
```
We will be comparing elements a lot so I think it's a good idea to write a function for just that:
```javascript
const Compare = {
    LESS_THAN: -1,
    BIGGER_THAN: 1
};

function defaultCompare(a, b) {
    if (a === b) {
        return 0;
    }
    return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}
```
Okay, now that that's settled, let's move onto sorting!

# Bubble Sort
### Best: O(N), Worst: O(N^2)

![gif of bubble sort](https://dev-to-uploads.s3.amazonaws.com/i/3m00apvur6vmr44yjq1a.gif)

The bubble sort is a good starting point since it is one of the simplest sorting algorithms. It's mostly just good for teaching purposes though since it is one of the slowest sorting algorithms. 

In short, the **bubble sort** algorithm compares every two adjacent values and swaps them if the first one is bigger than the second one. This reflects its name since the values tend to move up into the correct order, like bubbles rising to the surface. 

![gif of swapping process in bubble sort](https://dev-to-uploads.s3.amazonaws.com/i/ubhywp9xh8zk6on4caql.gif)

```javascript
function bubbleSort(arr, compare = defaultCompare) {
    const { length } = arr;
    for (let i = 0; i < length; i++) {
        for (let j = 0; j < length - 1 - i; j++) { // refer to note below
            if (compare(arr[j], arr[j + 1]) === Compare.BIGGER_THAN) {
                swap(arr, j, j + 1);
            }
        }
    }
    return arr;
}
```
Note that the solution I provided is a slightly improved version of the usual bubble sort algorithm since we are subtracting the number of passes from the inner loop to avoid unnecessary comparisons. To get a better understanding of what's actually happening, here is a diagram with an example:

![bubble sort step-by-step example](https://dev-to-uploads.s3.amazonaws.com/i/euz62qdpc74m9w4gcg09.png)

# Selection Sort
### Best/Worst: O(N^2)

![gif of selection sort](https://dev-to-uploads.s3.amazonaws.com/i/vweh1mcmiap8q3onqxz8.gif)

The basic idea behind the **selection sort** algorithm is that is finds the minimum value in the data structure, places it in the first position, finds the second minimum value, places it in the second position, and so on. 

![gif of selection sort process](https://dev-to-uploads.s3.amazonaws.com/i/mbzjewb2l897eiidkr14.gif)

```javascript
function selectionSort(arr, compare = defaultCompare) {
    const { length } = arr;
    let minIndex;
    for (let i = 0; i < length - 1; i++) {
        minIndex = i;
        for (let j = i; j < length; j++) {
            if (compare(arr[minIndex], arr[j]) === Compare.BIGGER_THAN) {
                minIndex = j;
            }
        }
        if (i !== minIndex) {
            swap(arr, i, minIndex);
        }
    }
    return arr;
}
```
The following diagram acts as an example of the selection sort algorithm in action:

![selection sort step-by-step example](https://dev-to-uploads.s3.amazonaws.com/i/43gibzc1hne0ie73cmp1.png)

# Insertion Sort
### Best: O(N), Worst: O(N^2)

![gif of insertion sort](https://dev-to-uploads.s3.amazonaws.com/i/tl0warawos46qnenoq33.gif)

The **insertion sort** algorithm builds the final sorted array one value at a time. The process looks something like this: 
1. Assume the first element is already sorted. 
2. Compare the first and second elements - should the second value stay in its place or be inserted before the first value? 
3. Next, you can do a similar comparison with the third value - should it be inserted in the first, second, or third position? And so on...

![gif of insertion sort process](https://dev-to-uploads.s3.amazonaws.com/i/osft7ojymgp8jroekxxu.gif)

```javascript
function insertionSort(arr, compare = defaultCompare) {
    const { length } = arr;
    let temp;
    for (let i = 1; i < length; i++) {
        let j = i;
        temp = arr[i];
        while (j > 0 && compare(arr[j - 1], temp) === Compare.BIGGER_THAN) {
            arr[j] = arr[j - 1];
            j--;
        }
        arr[j] = temp;
    }
    return arr;
}
```
Refer to this diagram for an example of insertion sort in action:

![insertion sort step-by-step example](https://dev-to-uploads.s3.amazonaws.com/i/kdcqz1o3weeqjxwcdfpq.png)

The insertion sort algorithm has a better performance than the selection and bubble sort algorithms when sorting small arrays though again, I wouldn't really recommend using it outside educational purposes. 

# Merge Sort
### Best/Worst: O(N Log N)

![gif of merge sort](https://dev-to-uploads.s3.amazonaws.com/i/fnswk5eug8jynxwkzdv0.gif)

The **merge sort** algorithm is a divide-and-conquer algorithm. In other words, it divides the original array into smaller arrays until each small array has only one position, then it *merges* the smaller arrays into a bigger one that is sorted. 

![gif of merge sort process](https://dev-to-uploads.s3.amazonaws.com/i/xokw1fxci67ttscu23vy.gif)

The implementation here is [recursive](https://dev.to/christinamcmahon/recursion-explained-with-examples-4k1m) and consists of two functions, one to divide the arrays into smaller ones and one to perform the sort:

```javascript
function mergeSort(arr, compare = defaultCompare) {
    if (arr.length > 1) {
        const { length } = arr;
        const middle = Math.floor(length / 2);
        const left = mergeSort(arr.slice(0, middle), compare);
        const right = mergeSort(arr.slice(middle, length), compare);
        arr = merge(left, right, compare);
    }
    return arr;
}

function merge(left, right, compare) {
    let i = 0;
    let j = 0;
    const result = [];
    while (i < left.length && j < right.length) {
        result.push(compare(left[i], right[j]) === Compare.LESS_THAN ? left[i++] : right[j++]);
    }
    return result.concat(i < left.length ? left.slice(i) : right.slice(j));
}
```
Here's a diagram to visualize the process:

![merge sort step-by-step example](https://dev-to-uploads.s3.amazonaws.com/i/bowug91fuof69su39fwd.png)

# Quick Sort
### Best/Average: O(N Log N), Worst: O(N^2)

![gif of quick sort](https://dev-to-uploads.s3.amazonaws.com/i/9sl7t3z56s02oy4smbzm.gif)

The **quick sort** is one of the most used sorting algorithm. Similar to the merge sort, the quick sort also uses the divide-and-conquer approach. Let's break the process down into steps to understand it a little better since it's a bit more complex than the previous sorts we've covered:

1. Select a value from the array that we will call **pivot**, generally the value at the middle of the array. 
2. Perform the **partition** operation which will result in an array with values lesser than the pivot on the left and greater on the right.
3. Repeat the first two steps for each subarray (left and right) until the arrays are completely sorted. 

![gif of quick sort process](https://dev-to-uploads.s3.amazonaws.com/i/vo2ltivrpucxtoamvdeb.gif)

```javascript
function quickSort(arr, compare = defaultCompare) {
    return quick(arr, 0, arr.length - 1, compare);
}

function quick(arr, left, right, compare) {
    let i;
    if (arr.length > 1) {
        i = partition(arr, left, right, compare);
        if (left < i - 1) {
            quick(arr, left, i - 1, compare);
        }
        if (i < right) {
            quick(arr, i, right, compare);
        }
    }
    return arr;
}

function partition(arr, left, right, compare) {
    const pivot = arr[Math.floor((right, left) / 2)];
    let i = left;
    let j = right;

    while (i <= j) {
        while (compare(arr[i], pivot) === Compare.LESS_THAN) {
            i++;
        }
        while (compare(arr[j], pivot) === Compare.BIGGER_THAN) {
            j--;
        }
        if (i <= j) {
            swap(arr, i, j);
            i++;
            j--;
        }
    }
    return i;
}
```

# Bucket Sort
### Best/Average: O(N + k), Worst: O(N^2)
The **bucket sort** algorithm is a distributed sorting algorithm that separates the elements into different *buckets*, or smaller arrays, and then uses a simpler sorting algorithm good for sorting small arrays, such as insertion sort, to sort each bucket. 

![gif of bucket sort process](https://dev-to-uploads.s3.amazonaws.com/i/vdv48hfw2oomr5r3myc0.gif)

```javascript
function bucketSort(arr, bucketSize) {
    if (arr.length < 2) {
        return arr;
    }
    // create buckets and distribute the elements
    const buckets = createBuckets(arr, bucketSize);
    // sort the buckets using insertion sort and add all bucket elements to sorted result 
    return sortBuckets(buckets);
}

function createBuckets(arr, bucketSize) {
    // determine the bucket count
    let min = arr[0];
    let max = arr[0];
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] < min) {
            min = arr[i];
        } else if (arr[i] > max) {
            max = arr[i];
        }
    }
    const bucketCount = Math.floor((max - min) / bucketSize) + 1;

    // initialize each bucket (a multidimensional array)
    const buckets = [];
    for (let i = 0; i < bucketCount; i++) {
        buckets[i] = [];
    }

    // distribute elements into buckets
    for (let i = 0; i < arr.length; i++) {
        const bucketIndex = Math.floor((arr[i] - min) / bucketSize);
        buckets[bucketIndex].push(arr[i]);
    }
    return buckets;
}

function sortBuckets(buckets) {
    const sortedArr = [];
    for (let i = 0; i < buckets.length; i++) {
        if (buckets[i] != null) {
            insertionSort(buckets[i]); // quick sort is another good option
            sortedArr.push(...buckets[i]);
        }
    }
    return sortedArr;
}
```
Note that the bucket sort works best when the elements can be distributed into buckets evenly. If the elements are largely sparse, then using more buckets is better, and vice versa.

The following diagram demonstrates the bucket sort algorithm in action:

![bucket sort step-by-step example](https://dev-to-uploads.s3.amazonaws.com/i/m10o9xkwmpyllvarra5g.png)

# Conclusion
We have covered some of the most common sorting algorithms. There are a lot more sorting algorithms I didn't get to go over in this article so let me know if you would like me to write a second part. Either way, I plan to write about [searching algorithms](https://dev.to/christinamcmahon/linear-binary-and-interpolation-search-algorithms-explained-55ni) soon so stay tuned! 

Below are some reference material (the sound of sorting video is my favorite!):

- [Big O Notation Cheat Sheet](https://www.bigocheatsheet.com/)
- [The Sound of Sorting (Full Video)](https://youtu.be/kPRA0W1kECg) by Timo Bingmann
- [Implementations in multiple languages](https://www.freecodecamp.org/news/sorting-algorithms-explained-with-examples-in-python-java-and-c/) from freeCodeCamp
- [Sorting Visualization Tool](https://visualgo.net/en/sorting) from Visualgo
- [Comedic Sorting Algo Webcomic](https://xkcd.com/1185/) from xkcd