SORTING TECHNIQUES
#include
#include
#include
template
class sort{
private:
T a[20],temp,k[30],n,i,j,l,first,second,third;
int size;
public:
void getdata();
void i_sort();
void q_sort(T a[],int LB,int UB);
void quick();
void mergesort();
void simple_merge(T k[],T first,T second,T third);
void two_merge_sort_R(T k[],T start,T finish);
};
template
void sort::getdata(){
int i;
cout<<"\nEnter the Total no. of Elements\t";
cin>>size;
for(i=1;i<=size;i++) {
cin>>a[i];
}
}
template
void sort ::i_sort(){
T temp;
a[0]=0;
for(int p=2;p<=size;p++) {
temp=a[p];
for(int j=p;temp a[j]=a[j-1];
}
a[j]=temp;
}
cout<<"\n\t\t INDSERTION SORT\n";
cout<<"\nThe Sorted elements are:";
for(int i=1;i<=size;i++)
cout << a[i]<< "\t";
}
template
void sort :: quick(){
q_sort(a,1,size);
cout<<"\n\t\t QUICK SORT\n";
cout<<"\nThe Sorted elements are:";
for(int i=1;i<=size;i++)
cout << a[i]<< "\t";
}
template
void sort :: q_sort(T a[],int LB, int UB){
int flag=1,key;
int temp,i,j;
if(LB i=LB;
j=UB+1;
key=a[LB];
while(flag) {
i=i+1;
while(a[i] i++;
j=j-1;
while(a[j]>key)
j--;
if(i temp=a[i];
a[i]=a[j];
a[j]=temp;
}
else
flag=0;
}
temp=a[LB];
a[LB]=a[j];
a[j]=temp;
q_sort(a,LB,j-1);
q_sort(a,j+1,UB);
}
return;
}
template < class T>
void sort ::simple_merge(T k[],T first,T second,T third){
int i=first;
int j=second;
int l=0;
int temp[20];
while((i if(k[i]<=k[j]) {
l=l+1;
temp[l]=k[i];
i=i+1;
}
else {
l=l+1;
temp[l]=k[j];
j=j+1;
}
}
if(i>=second) {
while(j<=third) {
l=l+1;
temp[l]=k[j];
j=j+1;
}
}
else {
while(i l=l+1;
temp[l]=k[i];
i=i+1;
}
}
for(int x=1;x<=l;x++)
k[first-1+x]=temp[x];
}
template < class T>
void sort::two_merge_sort_R(T k[],T start,T finish){
int size=finish-start+1;
if(size<=1)
return;
int middle=start + ( size / 2 ) - 1;
two_merge_sort_R(k,start,middle);
two_merge_sort_R(k,middle+1,finish);
simple_merge(k,start,middle+1,finish);
}
template < class T>
void sort::mergesort(){
two_merge_sort_R(a,1,size);
cout<<"The sorted elements are\n";
for(int i=1;i<=size;i++)
cout <}
void main(){
int choice,ch,ch1;
sort s;
clrscr();
do {
cout<<"\n\tSORTING TECHNIQUES";
cout<<"\n\t__________________\n";
cout<<"\n\t1.INTERNAL SORTING\n";
cout<<"\n\t2.EXTERNAL SORTING\n";
cout<<"\n\t3.EXIT\n";
cout<<"\nEnter the types of sort:\t";
cin>>ch;
switch(ch) {
case 1:
cout<<"\n\n\t\tTYPES OF INTERNAL SORT\n";
cout<<"\n\t1.INSERTION SORT";
cout<<"\n\t2.QUICK SORT";
cout<<"\n\t3.EXIT";
cout<<"\n\nInput the Choice\t";
cin>>choice;
switch(choice) {
case 1:
s.getdata();
s.i_sort();
break;
case 2:
s.getdata();
s.quick();
break;
case 3:
return;
}
break;
case 2:
cout<<"\n\n\t\tTYPE OF EXTERNAL SORT\n";
cout<<"\n\t1.MERGE SORT";
cout<<"\n\t2.EXIT";
cout<<"\n\nInput the Choice\t";
cin>>ch1;
switch(ch1) {
case 1:
s.getdata();
s.mergesort();
break;
case 2:
return;
}
break;
case 3:
return;
}
}
while(ch<=3);
getch();
}
|
No responses found. Be the first to respond and make money from revenue sharing program.
|