Quick Sort

//Complexity O(n^2) worst case


/*

Tanzila Islam

Southeast University

mail: tanzilamohita@gmail.com

*/

#include<iostream>

using namespace std;


    int Partition(int A[], int p, int r)

{

        int j=p, pivot=A[p], i;


            for(i=p+1;i<=r;i++)

{

    if(pivot>A[i]){

    A[j]=A[i];

    A[i]=A[j+1];

    A[j+1]=pivot;

    j=j+1;

    }

    }

    return j;

}



void QuickSort(int A[], int p, int r)

{

if(p<r)

{

int q=Partition(A,p,r);


QuickSort(A,p,q-1);

QuickSort(A,q+1,r);

}

}



int main()

{


int A[100],n,p,r;


cout << "\n------- QUICK SORT -------\n\n";

 cout <<  "Enter No. of Elements : " << endl;

    cin >> n;


cout << "Enter Elements :" << endl;

        for(int i=1;i<=n;i++)

            {


                cin >> A[i];

            }

p=1;

r=n;


QuickSort(A,p,r);


cout<<"\nAfter Sorting : \n";

for(int i=1;i<=n;i++)

{

cout<<A[i]<<endl;

}


}