Table of Contents
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
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.
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.