/**
 * Recursive partition of an array into two sub-arrays.
 * @param {array} array - array to iterate from
 * @param {array} leftArray - array with numbers smaller than the pivot
 * @param {array} rightArray - array with numbers bigger than the pivot
 * @param {number} pivot - number to compare
 * @result {object} returns the resultant leftArray and rightArray
 */
function partition (array, leftArray, rightArray, pivot) {
  // If array is empty it means there are no more elements 
  // to compare against pivot
  if (!array.length) {
    return {leftArray, rightArray};
  }
  
  // Immutably assign values
  const newLeftArray = array[0] < pivot ?
    [...leftArray, array[0]] :
    leftArray.slice(0);
        
  // Immutably assign values
  const newRightArray = array[0] < pivot ?
    rightArray.slice(0) :
    [...rightArray, array[0]];
  
  // Immutably assign values
  const newArray = array.slice(1);
        
  return partition(newArray, newLeftArray, newRightArray, pivot);
}

/**
 *
 */
function quickSort (array) {
  // Stop iterating when there is one or zero elements left,
  // since it wouldn't be sortable anymore.
  if (array.length < 2) {
    return array;
  }
  // Divide
  // In theory we could randomize the pivot, but as a practice we are
  // using the last element in the array.
  const pivot = array[array.length - 1];
  const { leftArray, rightArray } = partition(
    array.slice(0, array.length - 1), [], [], pivot);
  // Conquer
  // Keep partitioning the partitions. On each iteration the partitions become sorted
  // by the nature of the partition logic which splits the smaller and bigger numbers.
  const sortedLeftArray = quickSort(leftArray);
  const sortedRightArray = quickSort(rightArray)
  // Finally, concatenate the sorted results
  const sortedArray = [...sortedLeftArray, pivot, ...sortedRightArray];
  return sortedArray;
}


/*
* Unit Tests
*/
// Test 1
const array_1 = [4,5,2,7];
const sorted_1 = quickSort(array_1);
const should_1 = [2, 4, 5, 7];

document.querySelector('#sorted-1').textContent = sorted_1.toString();
document.querySelector('#should-1').textContent = should_1.toString();
const badge_1 = document.querySelector('#badge-1');
if (sorted_1.toString() === should_1.toString()) {
  badge_1.textContent = 'Passed';
  badge_1.classList.add('passed');
} else {
  badge_1.textContent = 'Failed';
  badge_1.classList.add('failed');
}

// Test 2
const array_2 = [7, 5, -2, 0];
const sorted_2 = quickSort(array_2);
const should_2 = [-2, 0, 5, 7];

document.querySelector('#sorted-2').textContent = sorted_2.toString();
document.querySelector('#should-2').textContent = should_2.toString();
const badge_2 = document.querySelector('#badge-2');
if (sorted_2.toString() === should_2.toString()) {
  badge_2.textContent = 'Passed';
  badge_2.classList.add('passed');
} else {
  badge_2.textContent = 'Failed';
  badge_2.classList.add('failed');
}

// Test 3
const array_3 = [1,4,2,9,5];
const sorted_3 = quickSort(array_3);
const should_3 = [1,2,4,5,9];

document.querySelector('#sorted-3').textContent = sorted_3.toString();
document.querySelector('#should-3').textContent = should_3.toString();
const badge_3 = document.querySelector('#badge-3');
if (sorted_3.toString() === should_3.toString()) {
  badge_3.textContent = 'Passed';
  badge_3.classList.add('passed');
} else {
  badge_3.textContent = 'Failed';
  badge_3.classList.add('failed');
}

// Test 4
const array_4 = [1,3,8,3,9];
const sorted_4 = quickSort(array_4);
const should_4 = [1,3,3,8,9];

document.querySelector('#sorted-4').textContent = sorted_4.toString();
document.querySelector('#should-4').textContent = should_4.toString();
const badge_4 = document.querySelector('#badge-4');
if (sorted_4.toString() === should_4.toString()) {
  badge_4.textContent = 'Passed';
  badge_4.classList.add('passed');
} else {
  badge_4.textContent = 'Failed';
  badge_4.classList.add('failed');
}

// Test 5
const array_5 = [2,3,4,5,6];
const sorted_5 = quickSort(array_5);
const should_5 = [2,3,4,5,6];

document.querySelector('#sorted-5').textContent = sorted_5.toString();
document.querySelector('#should-5').textContent = should_5.toString();
const badge_5 = document.querySelector('#badge-5');
if (sorted_5.toString() === should_5.toString()) {
  badge_5.textContent = 'Passed';
  badge_5.classList.add('passed');
} else {
  badge_5.textContent = 'Failed';
  badge_5.classList.add('failed');
}