Quick sort

by rishul matta

HTML

<div id="result"> </div>

JavaScript

function partition(arr, startIndex, endIndex) {
  const pivotVal = arr[endIndex]; // the pivot element
  let index = startIndex;
debugger;
  // begin iterate and swap
  for (let i = index; i < endIndex; i++) {
    if (arr[i] < pivotVal) {
      [arr[i], arr[index]] = [arr[index], arr[i]];
      index += 1; // note:  aim is to get the pivot to the correct place
    }
  }

  // move `pivotVal` to the middle index and return middle index
  [arr[index], arr[endIndex]] = [arr[endIndex], arr[index]];
  return index;
}

function quickSort(arr, startIndex, endIndex) {
  // Base case or terminating case
  // note: the return condition same as the binary search
  if (startIndex >= endIndex) {
    return;
  }

  // Returns midIndex / pivot index
  let midIndex = partition(arr, startIndex, endIndex);

  // Recursively apply the same logic to the left and right subarrays
  quickSort(arr, startIndex, midIndex - 1); // note end is length - 1 as this is used to select the pivot
  quickSort(arr, midIndex + 1, endIndex); // not the start BIG MISS
}

var arr = [10, 11 , 8, 6, 4, 2, 1, 7]
quickSort(arr, 0, arr.length - 1);
console.log(arr); // [-2, 2, 3, 4, 6, 7]



document.getElementById("result").innerHTML = arr