Quick sort Iterative

We have already seen in detail about the quick sort algorithm and have also seen its recursive implementation. In this article we will see how to implement the iterative quick sort in Javascript.

There are four different variations of pivot partition which can be used for quick sort algorithm.

• First element as a pivot.
• Last element as a pivot.
• Mid element as a pivot.
• Random element as a pivot.

We have already seen all these in our recursive implementation, for our iterative implementation also we will be use all of them.

Iterative quick sort implementation in Javascript

To implement the quick sort iteratively we will mock the recursive implementation using a stack. Because in each recursive call functions are pushed in a stack and then fetched and executed.

As quick sort picks a pivot and then partitions the array around this pivot making sure that pivot is sorted, but the partitioned array may or may not be sorted that is why we call them recursively to sort them.

The partition is done based on start and the end index. Keeping this in mind this is how we implement it iteratively.

• Create a stack and store the start and end index of the partition array.
• Then iterate the stack and in each iteration pick a pivot and partition the array around it.
• After partition push the new sub array indexes back to stack and repeat it.

Here I have used the last element as pivot, but you can use any of the above partition method.

const swap = (arr, left, right) =>  {
  const temp = arr[left]
  arr[left] = arr[right]
  arr[right] = temp;
}

const partitionHigh = (arr, low, high) => {
  //Pick the first element as pivot
  let pivot = arr[high];
  let i = low;
  
  //Partition the array into two parts using the pivot
  for(let j = low; j < high; j++){
    if(arr[j] <= pivot){      
      swap(arr, i, j);
      i++;
    }
  }
  
  swap(arr, i, high);
  
  //Return the pivot index
  return i;
}

const iterativeQuickSort = (arr) => {
  //Stack for storing start and end index
  let stack = [];
  
  //Get the start and end index
  let start = 0;
  let end = arr.length - 1;
  
  //Push start and end index in the stack
  stack.push({x: start, y: end});
  
  //Iterate the stack
  while(stack.length){
    //Get the start and end from the stack
    const { x, y } = stack.shift();
    
    //Partition the array along the pivot
    const PI = partitionHigh(arr, x, y);
    
    //Push sub array with less elements than pivot into the stack
    if(PI - 1 > x){
      stack.push({x: x, y: PI - 1});
    }
    
    //Push sub array with greater elements than pivot into the stack
    if(PI + 1 < y){
      stack.push({x: PI + 1, y: y});
    }
  }
}

Input:
let arr = [10, 7, 8, 9, 1, 5];
iterativeQuickSort(arr);
console.log(arr);

Output:
[1, 5, 7, 8, 9, 10]

Time complexity: O(nlogn) (average case), O(n ^ 2) (best case).
Space complexity: O(logn).