quick-sort.js

/*
 * Quick Sort implementation in JS, using stack instead of recursion
 */
function quickSort(arr) {
  let stack = [[0, Math.floor(Math.random() * arr.length), arr.length - 1]];

  while(stack.length > 0) {
    let vals = stack.pop();
    let startingIndex = vals[0];
    let pivot = vals[1];
    let endingIndex = vals[2];
    let swap = 0;

    /*
     * Originally tried to use XOR swap, but realized
     * when two elements equal each other, XOR swap will
     * zero out both numbers. Thus, it requires an "IF"
     * check to only swap if elements are unequal. I
     * figured that just made the code more complicated,
     * so I switched to a temp variable.
     */
    swap = arr[endingIndex];
    arr[endingIndex] = arr[pivot];
    arr[pivot] = swap;

    pivot = startingIndex;

    for (let i = startingIndex; i < endingIndex; ++i) {
      if (arr[i] < arr[endingIndex]) {
        swap = arr[i];
        arr[i] = arr[pivot];
        arr[pivot++] = swap;
      }
    }

    swap = arr[endingIndex];
    arr[endingIndex] = arr[pivot];
    arr[pivot] = swap;

    if (pivot - startingIndex > 1) {
      let leftPivot = pivot - (Math.floor(Math.random() * (pivot - startingIndex) + 1));
      stack.push([startingIndex, leftPivot, pivot - 1]);
    }
    if (endingIndex - pivot > 1) {
      let rightPivot = endingIndex - Math.floor(Math.random() * (endingIndex - pivot));
      stack.push([pivot + 1, rightPivot, endingIndex]);
    }
  }
  return arr;
}