sorting algorithms in javascript
Tags: algorithms, javascript
Published: 2018-12-20 07:07:52

---
title: sorting algorithms in javascript
published: true
description: 
tags: algorithms, javascript
---

## Bubble sort

![alt text](https://static.pokemonpets.com/images/monsters-images-300-300/1-Bulbasaur.png "bulba-sort")
<figcaption>Fun fact: if you say bubble sort really fast, it sounds like bulbasaur :O</figcaption>

Bubble sort is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order.

The pass through the list is repeated until no swaps are needed, which indicated that the list is sorted.

This algorithm is not suitable for large data sets as its average and worst case time complexity are of O(n\*2). 

{% youtube koMpGeZpu4Q %}<figcaption>even Obama disapproves</figcaption>


The best case time complexity is Ω(n) which occurs when array is already sorted.


```javascript
function bubbleSort(arr) {
    let swapped, tmp;
    do {
        swapped = false;
        for (let i=0; i< arr.length -1 ; i++) {
            if(arr[i] > arr[i+1]) {
                tmp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = tmp;
                swapped = true;
            }
        }
    } while (swapped)
    return arr
}
```

## Selection sort

Selection sort is a simple sorting algorithm that loops over the array and saves the absolute lowest value. The lowest value is then swapped with the first item in the unsorted array.

The best and worst case time complexity is O(n\*2).

```javascript
function selectionSort(arr) {
    for (let i =0; i < arr.length; i++) {
        let min = i
        for (let j=i+1; j<arr.length; j++) {
            if (arr[j] < arr[min]) {
                min = j
            }
        }
        if (i !== min) [arr[i], arr[min]] = [arr[min], arr[i]]
    }
    return arr
}
```

## Insertion sort

With insertion sort, you move an element that is not in the right position all the way to the point that it should be.

This algorithm is not suitable for large data sets as its average and worst case time complexity are of O(n\*2). The best case time complexity is Ω(n) which occurs when array is already sorted.

```javascript
function insertionSort(arr) {
    for (let i = 1; i < arr.length; i ++) {
        for (let j =0; j < i; j++) {
            if (arr[i] < arr[j]) {
                let tmp = arr.splice(i, 1)
                arr.splice(j,0,tmp[0])
            }
        }
    }
    return arr
}
```

## Merge sort

Merge sort splits an array into halves, calls itself for the two halves, and then merges the two halves.

The merge algorithm consists of two functions: the mergeSort function, which takes care of partitioning the arrays, and the merge function, which merges the separated arrays.

![alt text](https://ds055uzetaobb.cloudfront.net/image_optimizer/8c074d46d4c96077d11f9e8cab9ff5d95bdc3da0.gif "merge sort")
<figcaption>here is a visual representation</figcaption>

Merge sort leverages on recursion and is one of the most respected searching algorithms. Its worst time complexity is O(n*logn(n)). However, the best case time complexity is also Ω(n*logn(n))

```javascript
function mergeSort(arr) {
  if (arr.length === 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);
  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  let result = [];
  let li = 0; //left index
  let ri = 0; //right index
  while (li < left.length && ri < right.length) {
    if (left[li] < right[ri]) {
      result.push(left[li]);
      li++;
    } else {
      result.push(right[ri]);
      ri++;
    }
  }
  return result.concat(left.slice(li)).concat(right.slice(ri));
}
```