JavaScript quicksort

You can easily "stabilize" an unstable sort using a decorate-sort-undecorate pattern

function stableSort(v, f)
{
    if (f === undefined) {
        f = function(a, b) {
            a = ""+a; b = ""+b;
            return a < b ? -1 : (a > b ? 1 : 0);
        }
    }
    var dv = [];
    for (var i=0; i<v.length; i++) {
        dv[i] = [v[i], i];
    }
    dv.sort(function(a, b){
              return f(a[0], b[0]) || (a[1] - b[1]);
            });
    for (var i=0; i<v.length; i++) {
        v[i] = dv[i][0];
    }
}

the idea is to add the index as last sorting term so that no two elements are now "the same" and if everything else is the same the original index will be the discriminating factor.


Quicksort (recursive)

function quicksort(array) {
  if (array.length <= 1) {
    return array;
  }

  var pivot = array[0];
  
  var left = []; 
  var right = [];

  for (var i = 1; i < array.length; i++) {
    array[i] < pivot ? left.push(array[i]) : right.push(array[i]);
  }

  return quicksort(left).concat(pivot, quicksort(right));
};

var unsorted = [23, 45, 16, 37, 3, 99, 22];
var sorted = quicksort(unsorted);

console.log('Sorted array', sorted);

Quick Sort (ES6)

function quickSort(arr) {
  if (arr.length < 2) {
    return arr;
  }
  const pivot = arr[Math.floor(Math.random() * arr.length)];

  let left = [];
  let right = [];
  let equal = [];

  for (let val of arr) {
    if (val < pivot) {
      left.push(val);
    } else if (val > pivot) {
      right.push(val);
    } else {
      equal.push(val);
    }
  }
  return [
    ...quickSort(left),
    ...equal,
    ...quickSort(right)
  ];
}

Few notes:

  • A random pivot keeps the algorithm efficient even when the data is sorted.
  • As much as it nice to use Array.filter instead of using for of loop, like some of the answers here, it will increase time complexity (Array.reduce can be used instead though).

  1. Put your objects into an array.
  2. Call Array.sort(). It's very fast.

    var array = [3,7,2,8,2,782,7,29,1,3,0,34];
    array.sort();
    console.log(array); // prints [0, 1, 2, 2, 29, 3, 3, 34, 7, 7, 782, 8]
    

Why does that print in lexicographic order? That's how array.sort() works by default, e.g. if you don't provide a comparator function. Let's fix this.

    var array = [3,7,2,8,2,782,7,29,1,3,0,34];
    array.sort(function (a, b)
    {
        return a-b;
    });
    console.log(array); // prints [0, 1, 2, 2, 3, 3, 7, 7, 8, 29, 34, 782]