Sorting Algorithms
Tags: javascript, webdev, computerscience
Published: 2020-04-21 22:19:28

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](http://sorting.at/) 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**
```javascript
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**
```javascript
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**
```javascript
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**
```javascript
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**
```javascript
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 :wink: