Implementing QuickSort in Javascript with a random pivot

Question

I've written quicksort in javascript, but I wanted to try and create one with a random pivot, rather than by selecting the first or last element in the array:

   function qsort(a) {
     //base case
     if (a.length === 0) return [];

     //setting the pivot as the last element. 
     var left = [],
         right = [],
         pivot = a[a.length - 1];

     //look before the pivot. everything less than it goes to its left, more than it, to its right.
     for (var i = a.length - 2; i >= 0; i--) {
         a[i] < pivot ? left.push(a[i]) : right.push(a[i]);
     }
     //you then do this recursively until the basecase, pivoting/sorting all sub arrays, then concatenating the left side with the pivot and the right side.
     return qsort(left).concat(pivot, qsort(right));
 }

 console.log(qsort([9, 8, 7, 6, 10, 5]));//[5, 6, 7, 8, 9, 10]

I was thinking I could do something like:

pivot = a[Math.floor(Math.random() * a.length)];

Where I'm getting tripped up is that once you assign the pivot to be a random value in the array, the parameters of my for loop would no longer be valid. What is the best way to account for a random pivot within this function/for loop and make it sort properly?

Answer 1

The obvious thing to do would be to make a pivot array where you'd stuff elements that are equal to the pivot.

Another is to remember the index of the pivot as well as the value, and skip it at the top of the loop (which would go over the whole array):

if (i == pivotIndex) continue;

Another approach, usually used in C to avoid allocations, is to do everything in one array.

function qsort(array, start, end) {
  if (start === undefined) {
    start = 0;
    end = array.length - 1;
  } else if (start >= end) {
    return array;
  }
  var rStart = start, rEnd = end;
  var pivot = array[Math.floor(Math.random() * (end - start + 1) + start)];
  while (start < end) {
    while (array[start] <= pivot) start++;
    while (array[end] > pivot) end--;
    if (start < end) {
      var temp = array[start];
      array[start] = array[end];
      array[end] = temp;
    }
  }
  qsort(array, rStart, start - 1);
  qsort(array, start, rEnd);
  return array;
}

console.log(qsort([9, 8, 7, 6, 10, 5]));//[5, 6, 7, 8, 9, 10]