Data Structure and Algorithm

/**********************************************
--------------------------------
QUICK SORT ALGORITHM
--------------------------------
Partition(a,p,q)
1. set i = p
2. for j from p + 1 to q, Repeat step 3 and 4
3. if a[j] <= a[p],increase i
4. Swap a[i] and a[j]
5. swap a[i] and a[p]
6. return i

Quick.Sort(a,p,q)
1. if p < q, Repeat step 2,3 and 4
2. set r = partition(a,p,q)
3. call recursively QuickSort(a,p,r - 1)
4. call recursively QuickSort(a,r + 1,q)
5. return
***********************************************/

#include "iostream.h"
#include "conio.h"

void swap(int &a,int &b)
{
int temp = a;
a = b;
b = temp;
}

int partition(int a[],int p,int q)
{
int i = p;
for(int j = p + 1;j <= q;j++) //from Second element to Last
  if(a[j] <= a[p]) //assign smaller element to Left of pivot
   {
    i++;
    swap(a[i],a[j]);
   }

swap(a[p],a[i]); //set Pivot
return i;
}

void QuickSort(int *a,int p,int q)
{
if(p < q)
  {
   int r = partition(a,p,q); //Find Pivot
   QuickSort(a,p,r - 1); //sort Left Subarray
   QuickSort(a,r + 1,q); //sort Right Subarray
  }
}

int main()
{
int num[50],n;
cout << "How many numbers? ";
cin >> n;
cout << "\nEnter " << n << " Numbers\n";
for(int i = 0;i < n;i++)
  cin >> num[i];

QuickSort(num,0,n - 1); //call function QuickSort with pivot at First

position

cout << endl;
for(int i = 0;i < n;i++)
  cout << num[i] << ' ';

getch();
return 0;
}

OUTPUT

How many numbers? 10

Enter 10 Numbers
25 65 47 88 64 10 -98 0 35 6

-98 0 6 10 25 35 47 64 65 88

Download Original File

Quick.cpp