QuickSort

Home   »   QuickSort

const quicksort = (arr) => {
  const swap = (index1, index2) => {
    const elementToSwap = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = elementToSwap;
  };

  const partition = (left, right, pivot) => {
    while (left <= right) {
      while (arr[left] < pivot) {
        left++;
      }

      while (arr[right] > pivot) {
        right--;
      }

      if (left <= right) {
        swap(left, right);
        left++;
        right--;
      }
    }

    return left;
  };

  const _quicksort = (left, right) => {
    if (left >= right) return;

    const pivot = arr[Math.floor((left + right) / 2, 10)]; // might be random
    const index = partition(left, right, pivot);

    _quicksort(left, index - 1);
    _quicksort(index, right);
  };

  _quicksort(0, arr.length - 1);
};

Leave a Reply

Your email address will not be published. Required fields are marked *