Bubble Sort

  • Runtime: O(n^2)
  • Memory: O(1)
  1. Start at the beginning
  2. Swap the first 2 elements if the first > second
  3. Repeat until the list is sorted
const bubbleSort = array => {
    for (i = 0; i < array.length; i++) {
        for (j = 1; j < array.length; j++) {
            if (array[j - 1] > array[j]) {
                const temp = array[j - 1];
                array[j - 1] = array[j];
                array[j] = temp;
            }
        }
    }

    return array;
};

Selection Sort

  • Runtime: O(n^2)
  • Memory: O(1)
  1. Find the smallest element using linear scan
  2. Swap the element with the first element
  3. Find the next smallest and swap and so on
const selectionSort = array => {
    for (i = 0; i < array.length; i++) {
        let min = i;
        for (j = i + 1; j < array.length; j++) {
            if (array[j] < array[min]) {
                min = j;
            }
        }
        if (i !== min) {
            const temp = array[i];
            array[i] = array[min];
            array[min] = temp;
        }
    }

    return array;
};

Merge Sort

  • Runtime: O(n log(n))
  • Memory: O(n)
  1. Divide the array in half
  2. Sort each of the halves
  3. Merge back together
  • Essentially it comes to sorting 2 elements at a time then merging them
const mergeSort = (array) => {
  if (array.length == 1) {
    return array;
  }

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

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

const merge = (left, right) => {
  let result = [];
  let indexLeft = 0;
  let indexRight = 0;

  while (indexLeft < left.length && indexRight < right.length) {
    if (left[indexLeft] < right[indexRight]) {
      result.push(left[indexLeft]);
      indexLeft++;
    } else {
      result.push(right[indexRight]);
      indexRight++;
    }
  }

  return result.concat(left.slice(indexLeft)).concat(right.slice(indexRight));
};

Quick Sort

  • Runtime: O(n log(n))
  • Worst: O(n^2)
    • The selected element could always be the furthest from being the median, thus it can take longer
  • Memory: O(log(n))
  1. Pick a random element
  2. Partition the array with that element
  3. Partition all elements less than the selected element to the left and the other to the right
  4. Array will eventually become sorted
const quickSort = array => {
    if (array.length <= 1) {
        return array;
    }

    let left = [];
    let right = [];
    let pivot = array.pop();

    for (i = 0; i < array.length; i++) {
        if (array[i] <= pivot) {
            left.push(array[i]);
        } else {
            right.push(array[i]);
        }
    }
    return [].concat(quickSort(left), pivot, quickSort(right));
};

Radix Sort

  • Runtime: O(kn)
  1. Iterate through each digit of the number
  2. Group numbers by each digit
  3. Repeat sorting by each subsequent digit until it’s sorted

Leave a Reply

Your email address will not be published. Required fields are marked *