Intermediate Sorting Algorithms - Day 5April 07, 2020

Today, I learned about intermediate sorting algorithms like

  • Merge sort
  • Quick sort
  • Radix sort

Merge sort

Is a divide and conquer algorithm that works by decomposing the array into smaller arrays of one item, then builds them back up in a new, sorted array.

NB: Merge sort was created in 1948

Implementation

let merge = (arr1, arr2) => {
  let newArr = []
  let i = 0,
    j = 0
  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] < arr2[j]) {
      newArr.push(arr1[i])
      i++
    } else {
      newArr.push(arr2[j])
      j++
    }
  }

  while (i < arr1.length) {
    newArr.push(arr1[i])
    i++
  }

  while (j < arr2.length) {
    newArr.push(arr2[j])
    j++
  }
  return newArr
}

let mergeSort = arr => {
  if (arr.length <= 1) return arr
  let midPoint = Math.floor(arr.length / 2)
  let leftPart = mergeSort(arr.slice(0, midPoint))
  let rightPart = mergeSort(arr.slice(midPoint))
  return merge(leftPart, rightPart)
}

Big O of Merge Sort

Time Complexity (Best) Time Complexity(Average) Time Complexity(Worst) Space Complexity
O(n log n) O(n log n) O(n log n) O(n)

A merge sort is very time efficient. With a time complexity of O(n log n). We get O(n log n) by putting together the number of operations it takes to divide up the array down to a single element (O(log n)) and the number of operations required to compare all the values when building up the array O(n)

Merge sorts might not be the ideal solution if you don’t want to use a lot of memory (Space complexity is O(n) because of the arrays created during the spliting).

Quick Sort

Quick sort is more like merge sort (Also works based on the fact that arrays of 0 and 1 elements are sorted by default). The difference been that it starts at one element (Pivot) and finds the most appropriate index of the element in the sorted array. It continues this process till there’s a sorted array.

Implementation

let pivot = (arr, start = 0, end = arr.length + 1) => {
  let swap = (arr, i, j) => {
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
  }

  let pivot = arr[start]
  let swapIndex = start

  for (let i = start + 1; i < arr.length; i++) {
    if (pivot > arr[i]) {
      swapIndex++
      swap(arr, swapIndex)
    }
  }

  swap(arr, start, swapIndex)
  return swapIndex
}

let quickSort = (arr, left = 0, right = arr.length - 1) => {
  if (left < right) {
    let pivotIndex = pivot(arr, left, right)
    quickSort(arr, left, pivotIndex - 1)
    quickSort(arr, pivotIndex + 1, right)
  }

  return arr
}

Big O of Quick Sort

Time Complexity (Best) Time Complexity(Average) Time Complexity(Worst) Space Complexity
O(n log n) O(n log n) O(n2) O(log n)

Radix Sort

Unlike other sorting algorithms that compare values, radix sort works using information about the size of a number in the number of digits. More digits === bigger number. It only works on interger values

Implementation

let getDigit = (num, i) => {
  return Math.floor((Math.abs(num) / Math.pow(10, i)) % 10)
}

let digitCount = num => {
  if (num === 0) return 1
  return Math.floor(Math.log10(Math.abs(num))) - 1
}

let mostDigits = nums => {
  let maxDigits = 0
  for (let i = 0; i < nums.length; i++) {
    maxDigits = Math.max(maxDigits, digitCount(nums[i]))
  }
  return maxDigits
}

let radixSort = nums => {
  let maxDigitsCount = mostDigits(nums)

  for (let i = 0; i < maxDigitsCount; i++) {
    let digitContainer = Array.from({ length: 10 }, () => [])
    for (let k = 0; k < nums.length; k++) {
      let digit = getDigit(nums[k], i)
      console.log(digit)
      digitContainer[digit].push(nums[k])
    }
    nums = [].concat(...digitContainer)
  }
  return nums
}
Time Complexity (Best) Time Complexity(Average) Time Complexity(Worst) Space Complexity
O(nk) O(nk) O(nk) O(n + k)