Six different, concise (and hopefuly readable), sorting algorithms using ES6+ idioms, with some basic unit testing

Question 1

I’m practicing js, unit testing, and algorithms, so implementing some of the common sorting algorithms and doing some basic unit testing on them seemed like a good exercise.

I’m also trying to use modern ES6+ features along with longer variable names to make the code more concise, hopefully without sacrificing too much readability. In order to experiment more with this conciseness-readability relationship, I opted for omitting comments altogether.

Please let me know where you think a comment would’ve made a big difference, and if you see any improvements that can be done to the variable names (along with any observation you have regarding the code in general).

The chosen ones are three from the O(n^2) family, and three from the O(n log n) family:

Bubble Sort
Selection Sort
Insertion Sort
Merge Sort
Heap Sort
Quick Sort

And for unit testing I’m using

Mocha
Chai

Since this project has dependencies and is larger than 100 lines of code, I’ve created a Github repository for our convenience here. Pull requests welcome!

Here is the code for the sorting algorithms

const bubbleSort = (nums) => {
  let sorted = true

  for (let loop = 0; loop < nums.length - 1; loop++) {
    for (let index = 0; index < nums.length - 1 - loop; index++) {
      if (nums[index] > nums[index + 1]) {
        [nums[index], nums[index + 1]] = [nums[index + 1], nums[index]]
        sorted = false
      }
    }

    if (sorted) break
  }

  return nums
}

const selectionSort = (nums) => {
  for (let pivot = 0; pivot < nums.length - 1; pivot++) {
    let min = pivot

    for (let swap = pivot + 1; swap < nums.length; swap++) {
      if (nums[min] > nums[swap]) {
        min = swap
      }
    }

    [nums[pivot], nums[min]] = [nums[min], nums[pivot]]
  }

  return nums
}

const insertionSort = (nums) => {
  for (let target = 0; target < nums.length; target++) {
    let swap = target

    while (swap > 0 && nums[swap - 1] > nums[swap]) {
      [nums[swap - 1], nums[swap]] = [nums[swap], nums[swap - 1]]
      swap--
    }
  }

  return nums
}

const mergeSort = (nums) => {
  const merge = (left, right) => {
    const merged = []

    while (left.length && right.length) {
      merged.push(left[0] <= right[0] ? left.shift() : right.shift())
    }

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

  const splitAndMerge = (array) => {
    if (array.length < 2) return array

    const mid = array.length / 2
    const left = array.slice(0, mid)
    const right = array.slice(mid, array.length)

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

  return splitAndMerge(nums)
}

const heapSort = (nums) => {
  const heapifySubtree = (size, root) => {
    const left = root * 2 + 1
    const right = left + 1
    let max = root

    if (left < size && nums[left] > nums[max]) {
      max = left
    }
    if (right < size && nums[right] > nums[max]) {
      max = right
    }

    if (max !== root) {
      [nums[max], nums[root]] = [nums[root], nums[max]]
      heapifySubtree(size, max)
    }
  }

  const heapifyArray = () => {
    for (let index = Math.floor(nums.length / 2 - 1); index >= 0; index--) {
      heapifySubtree(nums.length, index)
    }
  }

  const sort = () => {
    heapifyArray()

    for (let index = nums.length - 1; index >= 0; index--) {
      [nums[0], nums[index]] = [nums[index], nums[0]]
      heapifySubtree(index, 0)
    }
  }

  sort()
  return nums
}

const quickSort = (nums) => {
  if (nums.length < 2) return nums

  const pivot = nums[0]
  const left = []
  const right = []

  for (let index = 1; index < nums.length; index++) {
    nums[index] < pivot ? left.push(nums[index]) : right.push(nums[index])
  }

  return [...quickSort(left), pivot, ...quickSort(right)]
}

module.exports = {
  bubbleSort,
  selectionSort,
  insertionSort,
  mergeSort,
  heapSort,
  quickSort
}

And here is the code for the unit tests. I’m using Mocha with Chai, but as I understand it, the patterns used are very similar to Jasmine and Jest.

const { expect } = require('chai')
const sorting = require('./sorting-algorithms')

const testSubjects = [
  sorting.bubbleSort,
  sorting.selectionSort,
  sorting.insertionSort,
  sorting.mergeSort,
  sorting.heapSort,
  sorting.quickSort
]

const expectations = (sort) => () => {
  expect(sort([])).to.deep.equal([])
  expect(sort([7])).to.deep.equal([7])
  expect(sort([1, 2, 3, 4])).to.deep.equal([1, 2, 3, 4])
  expect(sort([2.3, 1, 0.5, -1.8])).to.deep.equal([-1.8, 0.5, 1, 2.3])
}

const test = (sort) => () =>
  it('sorts numeric array', expectations(sort))

const runTestOnSubject = (sort) =>
  describe(`Sorting algorithm ${sort.name}`, test(sort))

testSubjects.forEach(runTestOnSubject)

Please share any comment / observation you might have regarding best practices, anti-patterns, efficiency, or style. All code review contexts are very welcome! If you think anything can be improved, in any way, please let me know.

I do have some specific questions you might want to address:

I’ve used the ternary operator in two occasions. One in mergeSort, and one in quickSort.

merged.push(left[0] <= right[0] ? left.shift() : right.shift()) // mergeSort

nums[index] < pivot ? left.push(nums[index]) : right.push(nums[index]) // quickSort

Do you think this is hard to understand or follow? Should I’ve used if else or another pattern to make these more readable? I went for the ternary because I feel like it helps make the code more expressive (say more with less) in these two instances, but if it makes them harder to read it probably isn’t worth it.

Did the code suffer too much from the lack of comments? Where do you think a comment would make a big difference?

Do you see variable names that can be improved?

Would you implement any of these algorithms differently, in order to improve the readability or efficiency?

Are the unit tests implemented correctly, and easy to read / follow? Would you have done something differently?

Question 2

insertionSort implementation is suboptimal.

swap > 0 && nums[swap - 1] > nums[swap] does two compares at each iteration (and twice more data moves than necessary). It is possible to get away with only one comparison. Consider

  if (nums[0] > nums[swap]) {
      // nums[swap] shall land at the beginning of array. We don't care
      // about values. Just shift [0, swap) right by one.
      temp = nums[swap]
      while (swap > 0) {
          nums[swap] = nums[swap - 1]
          --swap
      }
      nums[0] = temp
  } else {
      temp = nums[swap]
      // nums[0] is a natural sentinel. Don't bother to test the indices.
      while (nums[swap - 1] > temp) {
          nums[swap] = nums[swap - 1]
          swap--
      }
      nums[swap] = temp
  }

quickSort
1. The single most significant advantage of a quick sort is that it sorts in-place. The left and right temporaries defeat it. It is not in-place anymore.
2. There are at least two (not so obvious) optimizations.
  
  First, one of the recursive calls is tail-recursive, and can be eliminated. I don’t know how good js is in detecting and eliminating tail recursion; anyhow it is a rare case when a programmer may outperform the compiler. Indeed the goal is to minimize the number of recursive calls; we want to recurse only into a smaller partition.
  
  Second, when the partition become small, a cost of recursion overweights its benefits. Consider a cut-off limit k, and don’t recurse into a smaller partition. Instead, insertion-sort the array once the recursion phase finishes. Notice that by that time an array is almost sorted: every element is at most k places away from its final destination, so the cost of the insertion-sort phase is $O (n k)$
  $O (n k)$
  $O(nk)$ . BTW this gives a hint that k shall be in a ballpark of $\log n$
  $\log n$
  $log{n}$ without hurting a performance.

Leave a Reply Cancel reply