Iterative Implementation of quick sort

Given an array, this function will sort the array using quick sort. Here, quick sort is not implemented recursively, it is implemented in iterative manner.

Example:

INPUT:
arr[] = {4, 1, 10, 23, 5}

OUTPUT:
sorted array is {1, 4, 5, 10, 23}

Algorithm

Partition Algorithm

1. Take rightmost element as the pivot

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

3. Swap the rightmost element with the element at pIndex

4. return pIndex 

iterativeQuicksort Algorithm

Create a stack which 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

The above algorthm can be clearly explained in below diagram

C++ Program

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

int partition(int arr[], int start, int end)
{
	int pivot = arr[end]; //rightmost element is the pivot
	int pIndex = start;  //Is to push elements less than pivot to left and greater than to right of pivot
	for (int i = start; i < end; ++i)
	{
		if (arr[i] < pivot)
		{
			swap(arr[i],arr[pIndex]);
			pIndex++;
		}
	}
	swap(arr[pIndex], arr[end]);
	return pIndex;
}
void iterativeQuicksort(int arr[], int start, int end)
{

	int stack[end - start + 1];//Initializing stack size
	int top = -1; //To keep track of top element in the stack
	//pushing intial start and end
	stack[++top] = start;
	stack[++top] = end; 	

	//pop till the stack is empty
	while(top >= 0) 
	{
		//poping the top two elements 
		//ie,poping parent subarray indexes to replace child subbary indexes 
		end = stack[top--];
		start = stack[top--]; 	
		int pivot_index = partition(arr, start, end);

		//Pushing the left subarray indexes that are less than pivot
	    if (pivot_index - 1 > start )
	    {
	    	stack[++top] = start;
	    	stack[++top] = pivot_index -1;
	    }
	    //pushing the right subarray indexes that are greater than pivot
	    if (pivot_index + 1 < end)
	    {
	    	stack[++top] = pivot_index + 1;
	    	stack[++top] = end;
	    }
	}
	

}
void printArray(int arr[], int n)
{
	//Printing the sorted array
	cout<<"Sorted array is [ ";
	for (int i = 0; i < n; ++i)
	{
		cout<<arr[i]<<" ";
	}
	cout<<"]"<<endl;
}

int main()
{
	int arr[]= {4, 1, 10, 23, 5};  //creating an array
    int n = sizeof(arr)/sizeof(arr[0]); //size of the array
    iterativeQuicksort(arr,0,n-1);
    printArray(arr, n);
    return 0;
}
Try It


Next > < Prev
Scroll to Top