DSA: Sorting like a boss with JS
Published: 2022-06-18 10:06:17

One of the most common operations in programming is sorting a collection. Generally, this is a costly operation for most algorithms, as sorting has the notion of comparing every element with each other. We will see which algorithms overcome this with divide and conquer techniques, and how the simpler linear sorting algorithms are implemented. We will also discuss the complexity of each algorithm. 


# Table of Contents
1. [Bubble Sort](#bubble)
2. [Selection Sort](#selection)
3. [Insertion Sort](#insertion)
4. [Merge Sort](#merge)
5. [Quick Sort](#quick)
6. [Other sorting algorithms](#other)


## Bubble Sort <a name="bubble"></a>

Bubble sort is a very simply sorting algorithm. This algorithm doesn't have particular use cases other than have an introduction to the sorting algorithms for education purposes.

Bubble Sort algorithm loops through an array and compares two adjacent elements. Depending a condition, we determine if we require to switch the elements. In this way it is bubbling up the maximum value to the end of the array. 

For each pair, we compare if the first element is greater than the second then the two elements are swapped. Otherwise, we continue with the next pair of elements.

### Pseudocode

>     Look at each adjacent pair
>         If two adjacent elements are not in order
>         Swap them and set swap counter to falsy value


### Time complexity

Bubble sort is not an ideal sorting algorithm. From the pseudocode, we see that we have to compare pairs. This leads us to think we will have one nested loop! A nested loop makes our time complexity O(n²). 

In the best-case scenario, the array is already sorted. With a small optimisation in the algorithm, we can reach a best-case of O(n) (if the array is already sorted.).


### Implementation

```javascript
const bubbleSort = (arr) => {
  if (!arr) return;
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - i; j++) {
      if (arr[j] > arr[j + 1]) {
        const temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
}
```

### Optimization

```javascript
const bubbleSort = (arr) => {
  let swapped;
  for (let i = 0; i < arr.length; i++) {
    swapped = false;
    for (let j = 0; j < arr.length - i; j++) {
      if (arr[j] > arr[j + 1]) {
        const temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        swapped = true;
      }
    }

    if (swapped == false)
      break;
  }

  return arr;
}

```


## Selection Sort <a name="selection"></a>

One more algorithm that is used for educational purposes is Selection sort. The selection sort algorithm sorts an array by repeatedly finding the minimum element (or maximum, depending the order) from the unsorted part and putting it at the beginning. In every iteration, the minimum (or maximum) element from the unsorted subarray is picked and moved to the sorted subarray. 

### Pseudocode

> Repeat in the unsorted array:
>     Search the unsorted data to find the smallest value
>     Swap the smallest value with the first unsorted element


### Time Complexity

This search algorithm compares elements in an array to the first element. When it finds the smaller of the two elements, it swaps it to the first position. The algorithm repeats this pattern until the array is sorted. We can see again that we will need two nested loops to achieve that as we require comparison of pairs. That makes our complexity O(n²).

### Implementation


```javascript

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

    if (arr[min] < arr[i]) {
      let temp = arr[i];
      arr[i] = arr[min];
      arr[min] = temp;
    }
  }

  return arr;
}

```

## Insertion Sort <a name="insertion"></a>

Insertion sort is a sorting algorithm that works similar to how you sort playing cards in your hands. Weird eh?

The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.

Insertion sort is efficient for small data values or almost sorted arrays.

The algorithm is simple. We iterate through the array, we pick an element from the unsorted part and we **_insert_** it to the correct place. 

### Pseudocode

> The first element of the array is 'sorted'
> Repeat to the unsorted part of the array
>     Find the position of the next unsorted item 
>     Insert into the 'sorted' position by shifting elements

### Time complexity

In worst case the array is sorted with the opposite order. And we have to compare and insert in the appropriate position all the elements. That will be a O(n²).


### Implementation

```javascript

const insertionSort = (arr) => {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < arr[0]) {
      arr.unshift(arr.splice(i, 1)[0])
    } else {

      for (let j = 1; j < i; j++) {
        if (arr[i] > arr[j - 1] && arr[i] < arr[j]) {
          arr.splice(j, 0, arr.splice(i, 1)[0])
        }
      }

    }
  }

  return arr
}

```


## Merge Sort <a name="merge"></a>

Merge sort is using the divide and conquer technique. We will have a mergeSort function that partitions the array and a merge function that merge the partitions.

The main algorithm of merge sort divides the input array into two halves and calls itself with the two halves. This recursion continues until we reach granular components that are sorted. Then we proceed with merging these individual pieces into one result array.

### Pseudocode

•    Find the mid element of the array. mid = Math.floor((array.length)/2)
•    Splice the array in left and right parts
•    Call merge sort on (left,mid)
•    Call merge sort on (mid+1,right)
•    Continue until left is less than right
•    Then call merge function to perform a merge of the arrays.

### Time Complexity

Merge sort is a complicated algorithm. Dividing the algorithm into halves gives us a great time complexity of O(nlogn).  We need an auxiliary result array, and this results in a space complexity of O(n)


### Implementation

```javascript

const mergeSort = (arr) => {
  if (arr.length === 1) {
    return arr;
  }

  const middle = Math.floor(arr.length / 2);
  const left = arr.slice(0, middle)
  const right = arr.slice(middle)

  return merge(mergeSort(left), mergeSort(right))
}

const merge = (left, right) => {
  let arr = []
  // Break out of loop if any one of the array gets empty
  while (left.length && right.length) {
    if (left[0] < right[0]) {
      arr.push(left.shift())
    } else {
      arr.push(right.shift())
    }
  }

  return [...arr, ...left, ...right]
}

```

## Quick Sort <a name="quick"></a>

QuickSort is a Divide and Conquer sorting algorithm. It's much faster than linear sorting algorithms. Quick-sort is a comparison sorting algorithm, meaning that the sorting occurs by iterating through the array and comparing two defined values to a pivot. This pivot determines how to partition the collection. We have different ways to pick the pivot value, and this can affect the complexity of the algorithm.

### Pseudocode

> While the collection is unsorted
>     Pick a pivot 
>     Partition the array
>     All values smaller than pivot to the left and larger to the right
>     Perform pivot and partition on the left and the right partition

### Time complexity

The performance of this algorithm heavily depends on the pivot. If you always choose the first element as a pivot and we have an already sorted array, the quicksort will try to sort it. Choosing the first element as a pivot will make the call stack really long. This worst-case can reach a complexity of O(n²). The average case though, with a performant pivot is O(nlogn)

```javascript

const quickSort = (arr, low, high) => {
  if (low < high) {
    const pi = partition(arr, low, high);

    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
  }

  return arr;
}


const partition = (arr, low, high) => {

  const pivot = arr[high];
  let i = (low - 1);  

  for (let j = low; j <= high - 1; j++) {

    // If current element is smaller than the pivot
    if (arr[j] < pivot) {
      i++;
      swap(arr, i, j);
    }
  }
  swap(arr, i + 1, high);
  return (i + 1);
}

const swap = (arr, i, j) => {
  let temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

```


## Other sorting algorithms <a name="other"></a>

Other famous sorting algorithms are:

1. Heap Sort

Heap sort is a comparison-based sorting technique based on Binary Heap data structure. It is similar to selection sort algorithm where we first find the minimum element and place it at the beginning. We repeat the same process for the remaining elements. Time complexity: O(N log N).

2. Counting Sort

Counting sort is a sorting technique based on keys between a specific range. It works by counting the number of objects that are having distinct key-values. Then do arithmetic to calculate the position of each object in the output sequence. Time complexity: O(n)

3. Radix Sort

The idea of Radix Sort is to do digit by digit sort starting from least significant digit to most significant digit. Radix sort uses counting sort as a subroutine to sort.

4. Bucket Sort

Bucket sort is mainly useful when input is uniformly distributed over a range. For example, when we want to sort a large set of floating point numbers which are in range from 0.0 to 1.0 and are uniformly distributed across the range.