Quick Sort

A recursive approach is used to find the pivot element and iteratively push all of the smaller elements to the left, as well as all of the larger elements to the right in this algorithm. In practice, this technique is frequently the quickest. In other words, most programming languages support this technique for sorting out of the box.

The complexity of Space and Time

Best: O(nlog(n)) time | O(log(n)) space

Average: O(nlog(n)) time | O(log(n)) space

Worst: O(n^2) time | O(log(n)) space

n is the length of the input array.

Input

[8, 5, 1, 9, 5, 6, 2]

Output

[1, 2, 5, 5, 6, 8, 9]

Hint

Choose a random number from the input array and make it the pivot. Iterate through the rest of the array using two pointers left and right, the left pointer will move progressively to right and the right pointer moves left. When you traverse the array, compare the left and right pointer values to the pivot. If the left number is greater than the pivot and the right number is less than the pivot, exchange them. this will sort these numbers with respect to the pivot at the end of the iteration. Repeating this process, the key array should be completely sorted.

Pseudo Code

DEFINE FUNCTION quickSort(array):
    quickSortHelper(array, 0, len(array) - 1)
    RETURN array

DEFINE FUNCTION quickSortHelper(array, startIdx, endIdx):
    IF startIdx >= endIdx:
        RETURN
    SET pivotIdx TO startIdx
    SET leftIdx TO startIdx + 1
    SET rightIdx TO endIdx
    WHILE rightIdx >= leftIdx:
        IF array[leftIdx] > array[pivotIdx] and array[rightIdx] < array[pivotIdx]:
            swap(leftIdx, rightIdx, array)
        IF array[leftIdx] <= array[pivotIdx]:
            leftIdx += 1
        IF array[rightIdx] >= array[pivotIdx]:
            rightIdx -= 1
    swap(pivotIdx, rightIdx, array)
    SET leftSubarrayIsSmaller TO rightIdx - 1 - startIdx < endIdx - (rightIdx + 1)
    IF leftSubarrayIsSmaller:
        quickSortHelper(array, startIdx, rightIdx - 1)
        quickSortHelper(array, rightIdx + 1, endIdx)
    ELSE:
        quickSortHelper(array, rightIdx + 1, endIdx)
        quickSortHelper(array, startIdx, rightIdx - 1)

DEFINE FUNCTION swap(i, j, array):
    SET array[i], array[j] TO array[j], array[i]

Solution in Typescript

function quickSort(array) {
  quickSortHelper(array, 0, array.length - 1);
  return array;
}

function quickSortHelper(array, startIdx, endIdx) {
  if (startIdx >= endIdx) return;
  const pivotIdx = startIdx;
  let leftIdx = startIdx + 1;
  let rightIdx = endIdx;
  while (rightIdx >= leftIdx) {
    if (array[leftIdx] > array[pivotIdx] && array[rightIdx] < array[pivotIdx]) {
      swap(leftIdx, rightIdx, array);
    }
    if (array[leftIdx] <= array[pivotIdx]) leftIdx++;
    if (array[rightIdx] >= array[pivotIdx]) rightIdx--;
  }
  swap(pivotIdx, rightIdx, array);
  const leftSubarrayIsSmaller =
    rightIdx - 1 - startIdx < endIdx - (rightIdx + 1);
  if (leftSubarrayIsSmaller) {
    quickSortHelper(array, startIdx, rightIdx - 1);
    quickSortHelper(array, rightIdx + 1, endIdx);
  } else {
    quickSortHelper(array, rightIdx + 1, endIdx);
    quickSortHelper(array, startIdx, rightIdx - 1);
  }
}

function swap(i, j, array) {
  let temp = array[j];
  array[j] = array[i];
  array[i] = temp;
}

mocha.setup("bdd");
describe("Quick Sort", () => {
  it("Test Case #1", function () {
    const input = [8, 5, 1, 9, 5, 6, 2];
    chai.expect(quickSort(input)).to.deep.equal([1, 2, 5, 5, 6, 8, 9]);
  });

  it("Test Case #2", function () {
    const input = [5, 3, 1, 2, 4];
    chai.expect(quickSort(input)).to.deep.equal([1, 2, 3, 4, 5]);
  });
});

mocha.run();

Demo

https://codepen.io/evalteam/pen/NWwWQxg