Write a menu driven program to sort the array in ascending/descending order using a) Quick sort b) Merge sort
#include
#include
#include
#include
class sort
{
int
a[30], i, j, k, n;
public:
int
mergesort(int a[], int low, int high);
int
simplemerge(int a[], int low, int mid, int high);
int
partition(int a[], int low, int high);
int
quicksort(int a[], int low, int high);
};
int sort::mergesort(int a[], int low, int
high)
{
int
i, mid;
if
(low
{
mid
= (low + high) / 2;
mergesort(a,
low, mid);
mergesort(a,
mid + 1, high);
simplemerge(a,
low, mid, high);
}
return
0;
}
int sort::simplemerge(int a[], int low, int
mid, int high)
{
int
c[' '];
i
= low;
j
= mid + 1;
k
= low;
while
((i<=mid)&&(j<=high))
{
c[k++]
= a[i++];
else
c[k++]
= a[j++];
}
while
(i<=mid)
{
c[k++]
= a[i++];
}
while
(j<=high)
{
c[k++]
= a[j++];
}
for
(i=0 ;i<=k-1 ;i++ )
{
a[i]
= c[i];
}
return
0;
}
int sort::partition(int a[], int low, int
high)
{
int
i, j, key, temp;
key
= a[low];
i
= low + 1;
j
= high;
while
(1)
{
while
((i<=high)&&(key>=a[i]))
{
i++;
}
{
j--;
}
if
(i
{
temp
= a[i];
a[i]
= a[j];
a[j]
= temp;
}
else
{
temp
= a[j];
a[j]
= a[low];
a[low] = temp;
return
j;
}
}
}
int sort::quicksort(int a[], int low, int
high)
{
if
(low
{
j
= partition(a, low, high);
quicksort(a,
low, j-1);
quicksort(a,
j+1, high);
}
return
0;
}
void main()
{
sort
obj;
int
a[' '], ch, i, n;
char
ch2;
clrscr();
do
{
cout
<< "\nEnter number of elements : " ;
cin
>> n;
cout
<< "\n\nEnter the values :\n" ;
for
(i=0 ;i
{
cin
>> a[i];
}
cout
<< "\n\nChoose any given option : " ;
cout
<< "\n\t 1. Merge Sort" ;
cout
<< "\n\t 2. Quick Sort" ;
cout
<< "\n\t 3. Exit";
cout
<< "\n\nEnter your choice : " ;
cin
>> ch;
switch
(ch)
{
case
1: obj.mergesort(a, 0, n-1);
break;
case
2: obj.quicksort(a, 0, n-1);
break;
case
3: exit(0);
default:
cout << "\n\nInvalid choice" ;
}
cout
<< "\n\nThe sorted list in Ascending Order" ;
for
(i=0 ;i
{
cout
<< "\n" << a[i];
}
cout
<< "\n\nThe sorted list in Descending Order" ;
for
(i=n-1 ;i>=0 ;i-- )
{
cout
<< "\n" << a[i];
}
cout
<< "\n\nDo you want to continue? (y/n) : " ;
fflush(stdin);
cin
>> ch2;
}
while
(ch2=='y');
getch();
}
Comments
Post a Comment