quick_sort.js

'use strict';

function swap(arr, ind1, ind2) {
  let temp = arr[ind1];
  arr[ind1] = arr[ind2];
  arr[ind2] = temp;
}

function quickSortInPlace(arr, left, right) {
  left = left || 0;
  right = typeof(right) == 'undefined' ? arr.length - 1 : right;
  // 1. If left is less than right, declare a letiable called partitionIndex
  if(left < right) {
    // which is equal to the result of a call to partition, passing in arr, left, and right.
    let partitionIndex = partition(arr, left, right);
    // After the call to partition, perform a quicksort to the two subarrays
    // to the left and right of the partitionIndex.
    quickSortInPlace(arr, left, partitionIndex - 1);
    quickSortInPlace(arr, partitionIndex + 1, right);
  }

  return arr;
  // 2. Return arr.
}

function partition(arr, left, right) {
  // 1. Set the pivot value to be the value at the left index,
  let pivotValue = arr[left];
  // and set a letiable called partitionIndex equal to left.
  let partitionIndex = left;
    // The partitionIndex will help us keep track of where to perform our swaps so that we wind up with values correctly placed on either side of the pivot.

  // 2. For every index greater than left and less than right + 1,
  for (let i = left + 1; i < right + 1; i++) {
    // compare the array value to the pivot value.
    // 3. If the array value at the given index is less than the pivot value,
    if(arr[i] < pivotValue) {
      //increment the partition index and swap the array value with the value at the partition index.
      partitionIndex++;
      swap(arr, i, partitionIndex);
    }
  }

  swap(arr, left, partitionIndex);
  // 4. At the end, swap the pivot value with the value at the partition index
    //(this ensures that the pivot ends up in between values less than it and values greater than it).
  // 5. Return the partition index.
  return partitionIndex;
}

function quickSort(arr) {
  // 1. If the length of the array is less than 2, it is already sorted, so return it.
  if(arr.length < 2) {
    return arr;
  }

  // 2. Otherwise, create two empty arrays (one for the left and one for the right),
  // and set the first value in arr equal to the pivot.
  let left = [];
  let right = [];

  let pivotValue = arr[0];

  // 3. Compare every element in the array to the pivot.
  for (let i = 1; i < arr.length; i++) {
    //If the element is less than the pivot,
    if(arr[i] < pivotValue) {
      // push it into the left array.
      left.push(arr[i]);
    } else {
      // Otherwise, push it into the right array.
      right.push(arr[i]);
    }
  }
  // 4. Recrusively call quickSort on the left array and the right array,
  left = quickSort(left);
  right = quickSort(right);
  // then concatenate these arrays together with the pivot value in between them,
  left.push(pivotValue);
  return left.concat(right);
  // and return this larger array.
}

let gifNums = [6,5,3,1,8,7,2];
// console.log(quickSort(gifNums));
// gifNums = [6,5,3,1,8,7,2];
// console.log(partition(gifNums, 0, gifNums.length - 1))
// console.log(gifNums);
console.log(quickSortInPlace(gifNums));