# 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

2. Till the stack is empty

Available Captures for Rook Leetcode Solution

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.