Quicksort in JavaScript assuming an immutable array

Question

Update: further succinct versions below (inspired by Haskell)

Quick sort in JS assuming an immutable array:

    const reorder = (arr, pivot) => {
      let larger = []
      let smaller = []
      let equals = []
      for (let i = 0; i < arr.length; i++) {
        if (arr[i] < arr[pivot]) {
          smaller.push(arr[i])
        } else if (arr[i] > arr[pivot]) {
          larger.push(arr[i])
        } else {
          equals.push(arr[i])
        }
      }
      return {
        smaller: smaller,
        equals: equals,
        larger: larger
      }
    }

    const sort = (arr) => {
      if (arr.length <= 1) {
        return arr
      }
      const pivot = Math.floor(arr.length / 2)
      const result = reorder(arr, pivot)
      return [...sort(result.smaller), ...result.equals, ...sort(result.larger)]
    }

    console.log(sort([3, 1, 1, 1, 2]))

PS: I deleted the question posted earlier, thinking the algo was wrong, but then I realized a small tweak corrected it. The present code is based on comments received on earlier question.

Update: Inspired by Haskell, here is a more succinct version using ES6:

const qsort = (arr) => {
  if(arr.length == 0) {
    return []
  }
  let [x,...xs] = arr
  let smaller = xs.filter(v => v <=x)
  let larger = xs.filter(v => v > x)
  return [...qsort(smaller),x,...qsort(larger)]
}

OR simplified further:

const qsort = ([x,...xs]) => {
  return x == undefined ? [] :
  [...qsort(xs.filter(v => v <=x)),x,...qsort(xs.filter(v => v > x))]
}

qsort([3,3,8,1,23,4,5,6,9,9,1,0,45,5,10])

Answer 1

Your code looks quite good. It is easy to read and understand.

I don't know how efficient it is, though. The reorder function creates lots of objects (3 arrays, and a return object). I think there are more efficient ways to implement this. Since you got the algorithmic complexity correct, I would not worry about these performance issues too much. If the code is fast enough, it's good enough. And it's readable, which is often more important.

Instead of let larger = [], you can write const larger = [] since the variable larger is only ever assigned once. Sure, you later modify the contents of the array, but the variable still points to the same array as before.

Instead of the for (let i = 0 loop, you can use the simpler for (const elem of arr) loop, which will free your code from the many [i] brackets.

There are some more unnecessary brackets in that function, in the expression arr[pivot]. This expression is evaluated more often than necessary. I would change the pivot element to be the value itself instead of the array index.

The sort function returns the original array in some cases, and a new array in the other cases. That is inconsistent. The caller of the sort function might assume that they may modify the array afterwards, and depending on the array size, this may or may not affect the original array, which you defined as immutable. Therefore you should return a copy of the array in every case.

You should write lots of automated tests. Having just a single example is not enough to cover all cases. I have written a few test cases for you, feel free to add more.

After applying all these suggestions, the code looks like this:

const reorder = (arr, pivot) => {
    const larger = []
    const smaller = []
    const equals = []
    for (let elem of arr) {
        if (elem < pivot) {
            smaller.push(elem)
        } else if (elem > pivot) {
            larger.push(elem)
        } else {
            equals.push(elem)
        }
    }
    return {
        smaller: smaller,
        equals: equals,
        larger: larger
    }
}

const sort = (arr) => {
    if (arr.length <= 1) {
        return arr.slice()
    }
    const pivotIndex = Math.floor(arr.length / 2)
    const result = reorder(arr, arr[pivotIndex])
    return [...sort(result.smaller), ...result.equals, ...sort(result.larger)]
}

const testcase = (unsorted, expected) => {
    const actual = sort(unsorted)
    const actualStr = actual.join(', ')
    const expectedStr = expected.join(', ')
    if (actualStr !== expectedStr) {
        console.log('error:', 'input:', unsorted, 'expected:', expected, 'actual:', actual)
    }

    if (actual.length !== 0) {
        const beforeModification = unsorted.join(', ')
        actual[0] += 1
        const afterModification = unsorted.join(', ')
        if (beforeModification !== afterModification) {
            console.log('error:', 'unsorted:', unsorted, 'before:', beforeModification, 'after:', afterModification)
        }
    }
}

testcase([], [])
testcase([1], [1])
testcase([3, 1, 1, 1, 2], [1, 1, 1, 2, 3])
testcase([0, 5, 4, 8, 9, 3, 7, 1, 2, 6], [0, 1, 2, 3, 4, 5, 6, 7, 8, 9])