# Iterative Implementation of quick sort

0
593

## 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;
}``````