Quick Sort Algorithm (with Example) with C++ Code | Sorting Algorithms | Data Structures & Algorithms

> Quick Sort Algorithm is a Divide & Conquer algorithm. It divides input array in two partitions, calls itself for the two partitions(recursively) and performs in-place sorting while doing so. A separate partition() function is used for performing this in-place sorting at every iteration. Quick sort is one of the most efficient sorting algorithms.

• >> Time Complexity: θ(nlog(n))
• >> Space Complexity: O(log(n))

Working –

There are 2 Phases (3 major steps) in the Quick Sort Algorithm –

1. Division Phase – Divide the array(list) into 2 halves by finding the pivot point to perform the partition of the array(list).
   1. The in-place sorting happens in this partition process itself.
2. Recursion Phase –
   1. Call Quick Sort on the left partition (sub-list)
   2. Call Quick Sort on the right partition (sub-list)

Quick Sort Algorithm(Pseudo Code) –

Quick Sort Partition Function(Pseudo Code) –

C++ Program to Implement Quick Sort –

# include <iostream>
using namespace std;
// quick sort sorting algorithm
int Partition(int arr[], int s, int e)
{
 int pivot = arr[e];
 int pIndex = s;
 
 for(int i = s;i<e;i++)
 {
 if(arr[i]<pivot)
 {
 int temp = arr[i];
 arr[i] = arr[pIndex];
 arr[pIndex] = temp;
 pIndex++;
 }
 }
 
 int temp = arr[e];
 arr[e] = arr[pIndex];
 arr[pIndex] = temp;
 
 return pIndex;
}
 
void QuickSort(int arr[], int s, int e)
{
 if(s<e)
 {
 int p = Partition(arr,s, e);
 QuickSort(arr, s, (p-1));  // recursive QS call for left partition
 QuickSort(arr, (p+1), e);  // recursive QS call for right partition
 }
}
 
int main()
{
 
 int size=0;
 cout<<"Enter Size of array: "<<endl;
 cin>>size;
 int myarray[size];
 
 cout<<"Enter "<<size<<" integers in any order: "<<endl;
 for(int i=0;i<size;i++)
 {
 cin>>myarray[i];
 }
 cout<<"Before Sorting"<<endl;
 for(int i=0;i<size;i++)
 {
 cout<<myarray[i]<<" ";
 }
 cout<<endl;
 
 QuickSort(myarray,0,(size-1));  // quick sort called
 
 cout<<"After Sorting"<<endl;
 for(int i=0;i<size;i++)
 {
 cout<<myarray[i]<<" ";
 }
 
 return 0;
}

YouTube video tutorial –