C++ Program to Perform Quick Sort

Quick Sort

AIM:

• To Write a C++ Program to perform quick sort.

Algorithm:

• Pick an element, called a pivot, from the list.

• Reorder the list so that all elements which are less than the pivot come before the

pivot and so that all elements greater than the pivot come after it (equal values can

go either way). After this partitioning, the pivot is in its final position. This is called

the partition operation.

• Recursively sort the sub-list of lesser elements and the sub-list of greater elements

Program:

#include<iostream.h>

#include<conio.h>

class QuiSort

{

int i,j,pivot;

public:

int n,a[20];

void quick(int a[],int left,int right);

void swap(int a[],int i,int j);

};

void QuiSort :: quick(int a[],int first,int last)

{

if(first<last)

{

pivot=a[first];

i=first;

j=last;

while(i<j)

{

while(a[i]<=pivot&&i<last)

i++;

while(a[j]>=pivot&&j>first)

j--;

if(i<j)

swap(a,i,j);

}

swap(a,first,j);

quick(a,first,j-1);

quick(a,j+1,last);

}

}

void QuiSort :: swap(int a[],int i,int j)

{

int temp;

temp=a[i];

a[i]=a[j];

a[j]=temp;

}

void main()

{

QuiSort obj;

clrscr();

cout<<"\n\nQUICK SORT";

cout<<"\n\nEnter the limit : ";

cin>>obj.n;

clrscr();

cout<<"\n\nEnter the element\n\n";

for(int i=0;i<obj.n;i++)

cin>>obj.a[i];

obj.quick(obj.a,0,obj.n-1);

cout<<"\n\nThe sorted list is \n\n";

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

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

getch();

}

OUTPUT:

Enter the limit: 5

Enter the elements

5

4

3

2

1

The sorted list is

1 2 3 4 5

Result:

• Thus, the quick sort program has been written and executed successfully.