Program for Quick Sort in C++

Quick Sort is one of the most productive sorting calculation whose best, most noticeably terrible and normal case time complexities are O (n log n), O (n2) and O (n log n) individually.

How does it function?

1. We first pick a turn component. There are different approaches to pick a turn component.

Pick the first component

Pick the last component

Pick an arbitrary component

Pick middle component

So we can utilize anybody of the above strategies to pick the turn component. In the program given beneath I have picked the first component as turn.

1. Presently every one of the components littler than rotate is set at its left while components greater are put at right.
2. Rehash the over two stages recursively for both halves.

The following is the program to execute this calculation in C++.

Program for Quick Sort in C++

#include <iostream>
 
using namespace std;
 
void quick_sort(int[],int,int);
int partition(int[],int,int);
 
int main()
{
    int a[50],n,i;
    cout<<"How many elements?";
    cin>>n;
    cout<<"\nEnter array elements:";
    
    for(i=0;i<n;i++)
        cin>>a[i];
        
    quick_sort(a,0,n-1);
    cout<<"\nArray after sorting:";
    
    for(i=0;i<n;i++)
        cout<<a[i]<<" ";
    
    return 0;        
}
 
void quick_sort(int a[],int l,int u)
{
    int j;
    if(l<u)
    {
        j=partition(a,l,u);
        quick_sort(a,l,j-1);
        quick_sort(a,j+1,u);
    }
}
 
int partition(int a[],int l,int u)
{
    int v,i,j,temp;
    v=a[l];
    i=l;
    j=u+1;
    
    do
    {
        do
            i++;
            
        while(a[i]<v&&i<=u);
        
        do
            j--;
        while(v<a[j]);
        
        if(i<j)
        {
            temp=a[i];
            a[i]=a[j];
            a[j]=temp;
        }
    }while(i<j);
    
    a[l]=a[j];
    a[j]=v;
    
    return(j);
}

Output

How many elements?6

Enter array elements:9 15 6 7 10 12

Array after sorting:6 7 9 10 12 15