quick sort copypasta

by Augustus Yuan

HTML

<div id="debug-output">

</div>

CSS

code {
  display: block;
}

.inline {
  display: inline;
}

JavaScript

function logOut(output, inline) {
	var debugOutput = document.getElementById('debug-output');
  var codeElement = document.createElement('code');
  if (inline) codeElement.classList.add('inline');
  codeElement.innerHTML = (output);
  debugOutput.appendChild(codeElement);
}

// pick a pivot and then dedicate certain sections of the array to be greater and lower than the pivot
// once "partitioned", go through each list, compare the values, and swap accordingly
function quickSort(arr) {
  var left =  0;
  var right = arr.length-1;
  quickSortHelper(arr, left, right);
  logOut(arr);
}

function quickSortHelper(arr, left, right) {
  if (left >= right) {
    return;
  }
  var midIndex = Math.floor((parseInt(left) + parseInt(right)) / 2);
	var pivot =  arr[midIndex]; // just use the middle
  var index = partition(arr, left, right, pivot);
  logOut('index for quickSort: ' + index);
  logOut('quickSort left where range is ' + left + '-' + (index-1));
  quickSortHelper(arr, left, index-1);
  logOut('quickSort right where range is ' + index + '-' + right);
  quickSortHelper(arr, index, right);
}

// partition the array
// left and right represent the pointers on the side of the array which we compare
// against the pivot
function partition(arr, left, right, pivot) {
  logOut('current array: ' + arr);
  logOut('current left: ' + left + ' right: ' + right);
  logOut('pivot value ' + pivot);
  while (left <= right) {
  	while (arr[left] < pivot) left++;
    while (arr[right] > pivot) right--;
    logOut('left: ' + left);
    logOut('right: ' + right);
    if (left <= right) {
      logOut('swap ' + arr[left] + ' and ' + arr[right]);
      var tmp = arr[left];
      arr[left] = arr[right];
      arr[right] = tmp;
      left++;
      right--;
    }
  }
  logOut('final index: ' + left);
  return left;
}

var array = [4,13,3,2,6,7,8];
logOut(quickSort([4,13,3,2,6,7,8]));