C or C++ Program for Quick Sort

This article describes about the program to perform quick sort in C/C++. Let us descuss about quick sort.

Quick Sort
Quick Sort is a sorting technique based comparison. It was developed by Tony Hoare in 1960. It uses divide-and-conquer method for sorting. It is also known as partition-exchange sort
Quick Short uses the following steps:

• Choose a pivot element form the list
• Split all other elements (except the pivot) into two partitions
• The first partition holds the elements less than the pivot
• The second partition holds the elements greater than the pivot
• Use recursion to sort both partitions
• Finally Its Join the first sorted partition, the pivot, and the second sorted partition

Quick Sort Program

#include
#include
#include
int parttion(int *a, int p, int r)
{
    int x=a[r];
    int i=p-1,w,q;
    for(int j=p;j<r;j++)
    {
        if(a[j]<=x)
        {
            i=i+1;
            w=a[i];
            a[i]=a[j];
            a[j]=w;
        }
    }
    q=a[i+1];
    a[i+1]=a[r];
    a[r]=q;
return (i+1);
}

quicksort(int *a,int p,int r)
{
    int q=0;
    if(p<r)
    {
        q=parttion(a,p,r);
        quicksort(a,q+1,r);
        quicksort(a,p,q-1);
    }
return 0;
}

void main()
{
    int a[34];
    int r,p=0;
    clrscr();

    cout<<"This is a Quick sort program\n\n\n";
    cout<<"How many numbers you want to enter :";     cin>>r;
    cout<<"Enter the values :\n";
    for(int i=0;i<r;i++)     cin>>a[i];
    quicksort(a,p,r-1);
    cout<<"After sorting.........\n\n";
    for(i=0;i<r;i++)
    cout<<a[i]<<"\t";
    getch();
}