Iterative Implementation of Quick Sort  

Difficulty Level Medium
Frequently asked in Amazon Apple Bloomberg
Array Sorting

Problem Statement  

In the “Iterative Implementation of Quick Sort” problem, we have given an array a[]. We have to sort the array using quick sort. Here, quick sort is not implemented recursively, it is implemented in an iterative manner.

Input Format  

The first line containing an integer n.

Second-line containing n space-separated integer

Output Format  

The first and only one line containing n space-separated integer.

Constraints  

  • 1<=n<=10^5
  • -10^6<=a[i]<=10^6

Example  

5
4 1 10 23 5
1 4 5 10 23

Algorithm for Iterative Implementation of Quick Sort  

Partition Algorithm:

1. Take the rightmost element as the pivot

2. From the start index to the end index, Take a variable pIndex and point it to the start index. If the element is less than the pivot, swap with the element at pindex and increment pindex. Otherwise, do nothing.  ie, pushing all the elements less than pivot to the left and greater elements to the right.

3. Swap the rightmost element with the element at pIndex

4. Return pIndex

Iterative Quicksort Algorithm:

Create a stack that has the size of the array

1. Push Initial values of start and end in the stack ie, parent array(full array) start and end indexes

See also
Available Captures for Rook Leetcode Solution

2. Till the stack is empty

3.  Pop start and end indexes in the stack

4. call the partition function and store the return value it in pivot_index

5. Now, push the left subarray indexes that is less to the pivot into the stack ie, start, pivot_index -1

6. push the right subarray indexes that is greater than pivot into the stack ie, pivot+1, end

Implementation  

C++ Program for Iterative Implementation of Quick Sort

#include <bits/stdc++.h> 
using namespace std; 

int partition(int arr[], int l, int h) 
{ 
  int x = arr[h]; 
  int i = (l - 1); 

  for (int j = l; j <= h - 1; j++) { 
    if (arr[j] <= x) { 
      i++; 
      swap(arr[i], arr[j]); 
    } 
  } 
  swap(arr[i + 1], arr[h]); 
  return (i + 1); 
} 

void quick_sort(int arr[], int l, int h) 
{ 
  int stack[h-l+1]; 
  int top = -1; 
  stack[++top]=l; 
  stack[++top]=h; 
  while(top >= 0) 
  { 
    h = stack[top--]; 
    l = stack[top--]; 
    int p = partition(arr, l, h); 
    if(p-1>l) 
    { 
      stack[++top] = l; 
      stack[++top] = p - 1; 
    } 
    if(p+1<h) 
    { 
      stack[++top] = p + 1; 
      stack[++top] = h; 
    } 
  } 
} 

int main() 
{ 
  int n;
  cin>>n;
  int a[n];
  for(int i=0;i<n;i++)
  {
      cin>>a[i];
  }
  quick_sort(a,0,n-1); 
  for(int i=0;i<n;i++)
  {
      cout<<a[i]<<" ";
  }
  cout<<endl;
  return 0; 
}

Java Progeam for Iterative Implementation of Quick Sort

import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.Scanner;
import java.util.Vector;
class sum
{
    static int partition(int arr[], int low, int high) 
    { 
        int pivot = arr[high];
        int i = (low - 1); 
        for (int j = low; j <= high - 1; j++) { 
            if (arr[j] <= pivot) { 
                i++; 
                int temp = arr[i]; 
                arr[i] = arr[j]; 
                arr[j] = temp; 
            } 
        } 
        int temp = arr[i + 1]; 
        arr[i + 1] = arr[high]; 
        arr[high] = temp; 
  
        return i + 1; 
    } 
    static void quick_sort(int arr[], int l, int h) 
    { 
        int[] stack = new int[h - l + 1]; 
        int top = -1; 
        stack[++top] = l; 
        stack[++top] = h; 
        while (top >= 0) { 
            h = stack[top--]; 
            l = stack[top--]; 
            int p = partition(arr, l, h); 
            if (p - 1 > l) { 
                stack[++top] = l; 
                stack[++top] = p - 1; 
            } 
            if (p + 1 < h) { 
                stack[++top] = p + 1; 
                stack[++top] = h; 
            } 
        } 
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        quick_sort(a,0,n-1);
        for(int i=0;i<n;i++)
        {
            System.out.print(a[i]+" ");
        }
    }
}
5
3 -2 7 4 17
-2 3 4 7 17

Complexity Analysis for Iterative Implementation of Quick Sort  

Time Complexity

O(n*logn) where n is the size of the given array a[]. Here we sort the array using quick sort algorithm which lead us to n*logn time complexity.

See also
Dividing Array into Pairs With Sum Divisible by K

Space Complexity

O(n) where n is the size of the given array a[]. Here we use stack to sort the array and the maximum size of the stack will be n.

Ads Blocker Image Powered by Code Help Pro
Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Refresh