C++ program to implement QuickSort

#include<iostream>
using namespace std;
 

int partition(int left,int right,int arr[]);

void quicksort(int left,int right,int arr[]);

 

int main()

{

             int *a,n,left,right,i;

             cout<<"Enter number of elements:";

             cin>>n;

             a=new int[n];

             for(i=0;i<n;i++)

                cin>>a[i];

             right=n-1;

             left=0;

             quicksort(left,right,a);

             for(i=0;i<n;i++)

             cout<<a[i]<<"      ";

             return 0;

}

 

 

int partition(int left,int right,int arr[])

{

             int i,high,low,pivot;

             pivot=arr[left];

             while(right>left)

             {

                          high=arr[right];

                          while(pivot<high)

                          {

                              if(right<=left) break;

                              right--;

                              high=arr[right];

                          }

 

                          arr[left]=high;

                          low=arr[left];

                          while(pivot>low)

                          {

                              if(right<=left) break;

                              left++;

                              low=arr[left];

                          }

                          arr[right]=low;

             }

             arr[left]=pivot;

             return left;

}

 

void quicksort(int left,int right,int arr[])

{

             int index,i;

             if(left<right)

             {

                index=partition(left,right,arr);

                quicksort(left,index-1,arr);

                quicksort(index+1,right,arr);

             }

}

Input

Enter how many elements : 9

9  8  7  6  5  4  3  2  1

Output

1  2  3  4  5  6  7  8  9

Leave a Reply

Your email address will not be published.