Quick sort using stack

Open-Source Internship opportunity by OpenGenus for programmers. Apply now.

In this article, we will study about Quick sort algorithm along with it's implementation using stack in C++. Before getting started with Quick sort using Stack we should know about stack data structure.

Table of contents:

Basics of Stack
Quick sort
Algorithm for Quick sort using stack
Implementation of Quick sort using stack in C++
Time Complexity of Quick sort using Stack
Space Complexity of Quick sort using stack
Question

Pre-requisites:

Basics of Stack

Stack is a linear data structure used to store element in LIFO (Last In First Out) order. It means that when we insert element in stack, it get's stored at top position and when we remove an element the top positon element will get removed first.

Creating a Stack

The syntax for creating a stack in C++ is:

stack <data_type> stack_name;

For example:

stack <int> s; //s is the stack which store integer elements

The basic operations which we can perform on stack are as follows:

push(n):
It is used to insert an element n at the top of the stack.The time complexity required to complete this operation is O(1).
For example:
```
stack <int> s;
s.push(5); //This inserts an element 5 in the stack s
```
pop():
It is used to delete the element at the top of the stack.The time complexity required to complete this operation is O(1).
For example:
```
stack <int> s;
s.push(10);
s.pop(); //This will remove the element 10 from the stack
```
top():
It returns the reference to the element at the top of the stack.The time complexity required to complete this operation is O(1).
For example:
```
stack <int> s;
s.push(10);
s.push(11);
s.push(12);
s.push(13);
s.pop();
s.pop();

while(!s.empty()){
    cout<<s.top()<<" ";
    s.pop();
}
```
Output:
```
    11  10
```

Quick sort

Quick sort is an algorithm which is used to sort the list of elements.It is based on the divide and conquer paradigm.It means that we will divide the array of elements into two sub-parts and then further quick sort algorithm is applied on these two sub-parts.This division of array takes place using a pivot point.

We will partition the array around pivot element such that the left side has elements lesser than the pivot and right side elements are greater than the pivot element.

Algorithm for Quick sort using stack

First, we have to store the starting and ending index of the given array in the stack. We will call the partition function on these indices and remove them from the stack.
Now, we will do partitioning around the pivot element such that all left side elements in the array are smaller than the pivot element and all the right side elements are larger than the pivot element.
The starting and ending indices of the left side subarray and the starting and ending indices of the right side subarray are again stored in stack and partitioned by selecting pivot elements for them and then we will remove these indices from the stack.
This process continues until the stack is empty and there are no elements left to be partitioned.This way, we will get the array which is completely sorted.

Quicksort
Figure: Partitioning of element around Pivot element

Implementation of Quick sort using stack in C++:

Following is the implementation of Quick sort using stack in C++:

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
 
int partition(int arr[], int startIndex, int endIndex)
{
    // select the last element as a pivot from the array
    int pivot = arr[endIndex];
 
    // elements smaller than the pivot element goes to the left of `pivotIndex`
    // elements greater than the pivot element goes to the right of `pivotIndex`
    // equal elements can go on either side of the pivotIndex
    int pivotIndex = startIndex;
 
    // if an element is less than or equal to the pivot, we will increase the 'pivotIndex' and we will place that element before the pivot.
    for (int i = startIndex; i < endIndex; i++)
    {
        if (arr[i] <= pivot)
        {
            swap(arr[i], arr[pivotIndex]);
            pivotIndex++;
        }
    }
 
    // swap `pivotIndex` with pivot element
    swap (arr[pivotIndex], arr[endIndex]);
 
    return pivotIndex;
}
 
void Quicksort(int arr[], int n)
{
    //stack for storing start and end Index of the subarrays
    stack<pair<int, int>> s; 

    //starting index of the given array
    int startIdx = 0; 
    //ending index of the given array
    int endIdx = n - 1; 
    
    //pushing the start and end index of the array into the stack
    s.push({startIdx, endIdx});  
 
    while (!s.empty())
    {
        // removing the top pair from the array and get the starting
        // and ending index of the subarray
        startIdx = s.top().first;
        endIdx = s.top().second;
        s.pop();
 
        // partitioning the elements around pivot
        int pivotIdx = partition(arr, startIdx, endIdx);
 
        //push subarray indices to stack which has elements smaller than the current pivot
        if (pivotIdx - 1 > startIdx) {
            s.push({startIdx, pivotIdx - 1});
        }
        
        //push subarray indices to stack which has elements greater than the current pivot
        if (pivotIdx + 1 < endIdx) {
            s.push({pivotIdx + 1, endIdx});
        }
    }
}
 
int main()
{
    
    int n; //size of the array
    cin>>n;

    int arr[n]; //arr is the array to be sorted
    
    cout<<"Enter the elements of the array to be sorted:"<<endl;
    
    for(int i=0;i < n;i++){
        cin>>arr[i];
    }
 
    Quicksort(arr, n);
 
    // print the sorted array
    
    cout<<"Sorted array:"<<endl;
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
 
    return 0;
}

Input:
6
Enter the elements of the array to be sorted:
9 -2 4 7 2 4
Sorted array:
-2 2 4 4 7 9

Time Complexity of Quick sort using Stack:

Best Case: The best case occurs when the pivot element is the middle element or near to the middle element.The best case time complexity of quick sort is O(nlogn).

Average Case: The average case occurs when the array elements are not in proper sequence i.e. they are not arranged properly either in ascending or descending order.The average case time complexity of quick sort is O(nlogn).

Worst Case: The worst case occurs when the pivot element is either the greatest or smallest element of the array.The worst case time complexity of quick sort is O(n^2).

Space Complexity of Quick sort using stack:

Since we are using stack for implementation of quick sort, the space complexity will be O(n).

Question:

What is the best case time complexity of the quick sort algorithm?

a) O(n)
b) O(1)
c) O(nlogn)
d) O(logn)

With this article at OpenGenus, you must have the complete idea of Quick Sort using Stack along with time and space complexity.