quickSort.js

#!/usr/bin/env node

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }

  // Choosing the first item as the pivot causes worst-case
  // performance if an array is already sorted.
  let randomIdx = Math.floor(Math.random() * arr.length);
  let pivot = arr[randomIdx];

  let rest = [...arr];
  rest.splice(randomIdx, 1);

  let left = rest.filter(i => i < pivot);
  let right = rest.filter(i => i >= pivot);

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

console.log(
  quickSort([
    8,
    99,
    998,
    17,
    10,
    68,
    2,
    10021,
    6,
    2,
    4,
    234,
    9,
    456,
    1,
    2,
    3,
    9,
    7,
    5,
    9,
    3,
    6,
    5
  ])
);

I should really try to implement an imperative quickSort that operates upon the array in-place.

I should really try to implement an imperative quickSort that operates upon the array in-place.

https://gist.github.com/sebinsua/5f5ec07282bcee43f7df3c4396bdfaa5

three years later!!!