IMPLEMENTATION OF QUICK SORT

IMPLEMENTATION OF QUICK SORT

AIM:

            To sort the elements using the quick sort.

ALGORITHM:

Step 1:Start the process.

Step 2:Get the values from the user.

Step 3:Position a pointer ‘low’ to the second element and a pointer ‘HIGH’  to the last element.

Step 4:Move ‘low’ forward till it reaches an element greater than k1.

Step 5:Move ‘high’ backward till it reaches an element less than k1.

Step 6:Interchange klow and khigh if low<high.

Step 7:Continue steps 2 to 4 till low<high.

Step 8:Swaps the elements at first and high indices.

PROGRAM:

#include <iostream.h>

#include <conio.h>

#include <process.h>

template <class T>

class QUICK_SORT

{

private:

T a[20];

int low, high, size;

public:

QUICK_SORT(int n)

{size=n;

}

void Get_Data();

void Quick(int low, int high);

int Partition(int low, int high);

void Display_Data();

};

template<class T>

void QUICK_SORT<T>::Get_Data()

{ cout<<"Enter the elements to be inserted" << endl;

for(int i=0; i<size; i++)

cin >> a[i];

}

template<class T>

void QUICK_SORT<T>::Quick(int low, int high)

{ int j;

if(low <= high)

{ j=Partition(low,high);

Quick(low, j-1);

Quick(j+1, high);

}} template<class T>

int QUICK_SORT<T>::Partition(int low, int high)

{ int i, j;

T key;

i = low + 1;

j = high;

key = a[low];

while(1)

{

while(i < high && key >= a[i]) i++;

while(key <a[j]) j--;

if(i < j)

{

T temp = a[i];

a[i] = a[j];

a[j] = temp;

} else

{

T temp = a[j];

a[j] = a[low];

a[low] = temp;

return j;

}

}

//end while

}//end QUICK_SORT<T>

template<class T>

void QUICK_SORT<T>::Display_Data()

{ int i;

cout << "The sorted list is:";

for(i=0; i<size; i++)

cout <<a[i]<<"\t";

cout << endl;

}

void main()

{ int n, ch;

clrscr();

cout<<"Enter number of data: ";

cin>>n; cout << endl;

QUICK_SORT<int>Q1(n);

QUICK_SORT<double>Q2(n);

cout << "1.To sort integer data " << endl;

cout << "2.To sort double data" << endl;

cout << "3.To quit" << endl;

cout << "Enter your choice" << endl;

cin >> ch;

switch(ch)

{ case 1:

Q1.Get_Data();

Q1.Quick(0,n-1);

Q1.Display_Data();

break;

case 2:

Q2.Get_Data();

Q2.Quick(0,n-1);

Q2.Display_Data();

break;

}

getch();

}//end main()

OUTPUT1:

Enter number of data: 4

1.To sort integer data

2.To sort double data

3.To quit

Enter your choice

2

Enter the elements to be inserted

1.7 2.6 1.9 4.7

The sorted list is:1.7  1.9     2.6     4.7

OUTPUT2:

Enter number of data: 4

1.To sort integer data

2.To sort double data

3.To quit

Enter your choice

1

Enter the elements to be inserted

12 56 89 23

The sorted list is:12   23      56      89

  

RESULT:

Thus the program for implementation of Quick sort using templates was executed.