sorting algorithms in javascript

Bubble sort

Fun fact: if you say bubble sort really fast, it sounds like bulbasaur :O

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).

even Obama disapproves

The best case time complexity is Ω(n) which occurs when array is already sorted.

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).

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.

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.

here is a visual representation

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))

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));
}