But What About Iterative?

Now let's think of the iterative version. It's not as straightforward to implement!

We can apply the pivot and adjustment of items around the pivot, only on one subarray at a time. If we work with the left subarray, then we need to store the indices of the right subarray to be used later for repeating the process. This necessitates the implementation of our own stack that will maintain the indices of left and right subarrays to work with, instead of using the implicitly built system activation stack for recursive functions.

In the code here for the iterative version of quickSort, we have two stacks of the same size. One holds the start index of the subarray and the other holds the end index of the subarray. Once values are adjusted around the pivot for one subarray, the other subarray's start and end indices are popped from the stack.

xxxxxxxxxx

console.log(vect);

function exchange(a, i, j) {

  let temp = a[i];

  a[i] = a[j];

  a[j] = temp;

}

​

function adjust(A, start, end, pivot) {

  let a = start, b = end;

  let stop = false;

  while (!stop) {

    while (a < pivot && A[a] <= A[pivot])

      a++;

    while (b > pivot && A[b] >= A[pivot])

      b--;

    if (a >= pivot && b <= pivot)

      stop = true;

    else {

      exchange(A, a, b);

      if (a === pivot)

        pivot = b;

      else if (b === pivot)

        pivot = a;

    }

  }

}

​

function quickSortIterative(A, start, end) {

  let startIndex = [];

  let endIndex = [];