Quick Sort C++

 Quick Sort Program Code in C++

Read Similar Posts:
1. Quick Sort In C 
2. Quick Sort Time Complexity

//Code Body Start

#include<iostream>
using namespace std;

int partition(int a[], int left, int right, int n);
void QuickSort(int a[], int left, int right, int n);

int main()
{
    int i, n, numbers[100];
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>numbers[i];
    }
    QuickSort(numbers, 0, n-1, n);
    for(i=0;i<n;i++)
    {
        cout<<numbers[i]<<" ";
    }
    cout<<endl;
    return 0;
}


int partition(int a[], int left, int right, int n)
{
    int piv, i, j, temp;
    piv = left;
    i = piv + 1;
    j = right;
    while(i<=j)
    {
        while(a[piv] < a[j] && piv < j)
        {
            j--;
        }
        if(a[piv] > a[j] && piv < j)
        {
            temp = a[piv];
            a[piv] = a[j];
            a[j] = temp;
            piv = j;
            j--;
        }
        while(a[i] < a[piv] && i < piv)
        {
            i++;
        }
        if(a[i] > a[piv] && i < piv)
        {
            temp = a[piv];
            a[piv] = a[i];
            a[i] = temp;
            piv = i;
            i++;
        }
    }
    return piv;
}
void QuickSort(int a[], int left, int right, int n)
{
    if(left < right)
    {
        int ind = partition(a, left, right, n);
        QuickSort(a, left, ind-1, n);
        QuickSort(a, ind+1, right, n);
    }
}


//Code Body End

Sample Input:
10 /*Number of integers*/
12 33 44 55 555 66 77 88 99 100 /*Numbers*/

Sample Output:
12 33 44 55 66 77 88 99 100 555 /*Sorted Numbers*/

Post a Comment

Previous Post Next Post