#include<conio.h>
#include<stdio.h>
void quick(int [],int,int,int);
void accept_arr(int [],int);
void disp_arr(int [],int);
void partition(int [],int,int,int);
void merge(int [],int,int,int,int );
void main()
{
int a[30],n,i,op;
char ch;
do
{
printf("\n\t \t**MENU** \n \t \t 1.Quick Sort \n\t \t2.Merge Sort");
printf("\n \t Enter choice = \t ");
scanf("%d",&op);
switch(op)
{
case 1:
printf("\nEnter no of elements = \t ");
scanf("%d",&n);
accept_arr(a,n);
quick(a,n,0,n-1);
printf("\nSORTED ARRAY IS = ");
disp_arr(a,n);
break;
case 2:
printf("\nEnter no of elements = \t ");
scanf("%d",&n);
accept_arr(a,n);
partition(a,n,0,n-1);
printf("\nSORTED ARRAY IS :: ");
disp_arr(a,n);
break;
default:
printf("\n \t Wrong choice...!");
}
printf("\nWant to continue ?(y/n) ");
scanf("%c",&ch);
}while(ch=='y'||ch=='Y');
getch();
}
//function to accept array
void accept_arr(int a[],int n)
{
int i;
printf("\nENTER ARRAY ELEMENTS :: ");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
}
//function to display array
void disp_arr(int a[], int n)
{
int i;
printf("\n");
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}
}
//quick sort function
void quick(int a[], int n, int l, int h)
{
int down,up,t,pivot;
pivot=a[l];down=l+1;up=h;
while(down<=up)
{
while(a[down]<=pivot && down<=up)
down++;
while(a[up]>pivot)
up--;
if(down<=up)
{
t=a[down];
a[down]=a[up];
a[up]=t;
down++;up--;
}
}
a[l]=a[up];
a[up]=pivot;
printf("\nPIVOT %d :",pivot);
disp_arr(a,n);
if(l<up-1)
{
quick(a,n,l,up-1);
}
if(down<h)
{
quick(a,n,down,h);
}
}
//function to partition
void partition(int a[], int n, int s, int e)
{
int m;
if(s<e)
{
m=(s+e)/2;
partition(a,n,s,m);
partition(a,n,m+1,e);
merge(a,n,s,m,e);
}
}
//merge sort function
void merge(int a[], int n, int s, int m, int e)
{
int b[30],i,j,k;
i=s;j=m+1;k=s;
while(i<=m && j<=e)
{
if(a[i]<=a[j])
{
b[k]=a[i];
i++;k++;
}
else
{
b[k]=a[j];
j++;k++;
}
}
while(j<=e)
{
b[k]=a[j];
j++;k++;
}
while(i<=m)
{
b[k]=a[i];
i++;k++;
}
for(i=s;i<=e;i++)
{
a[i]=b[i];
}
}
#include<stdio.h>
void quick(int [],int,int,int);
void accept_arr(int [],int);
void disp_arr(int [],int);
void partition(int [],int,int,int);
void merge(int [],int,int,int,int );
void main()
{
int a[30],n,i,op;
char ch;
do
{
printf("\n\t \t**MENU** \n \t \t 1.Quick Sort \n\t \t2.Merge Sort");
printf("\n \t Enter choice = \t ");
scanf("%d",&op);
switch(op)
{
case 1:
printf("\nEnter no of elements = \t ");
scanf("%d",&n);
accept_arr(a,n);
quick(a,n,0,n-1);
printf("\nSORTED ARRAY IS = ");
disp_arr(a,n);
break;
case 2:
printf("\nEnter no of elements = \t ");
scanf("%d",&n);
accept_arr(a,n);
partition(a,n,0,n-1);
printf("\nSORTED ARRAY IS :: ");
disp_arr(a,n);
break;
default:
printf("\n \t Wrong choice...!");
}
printf("\nWant to continue ?(y/n) ");
scanf("%c",&ch);
}while(ch=='y'||ch=='Y');
getch();
}
//function to accept array
void accept_arr(int a[],int n)
{
int i;
printf("\nENTER ARRAY ELEMENTS :: ");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
}
//function to display array
void disp_arr(int a[], int n)
{
int i;
printf("\n");
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}
}
//quick sort function
void quick(int a[], int n, int l, int h)
{
int down,up,t,pivot;
pivot=a[l];down=l+1;up=h;
while(down<=up)
{
while(a[down]<=pivot && down<=up)
down++;
while(a[up]>pivot)
up--;
if(down<=up)
{
t=a[down];
a[down]=a[up];
a[up]=t;
down++;up--;
}
}
a[l]=a[up];
a[up]=pivot;
printf("\nPIVOT %d :",pivot);
disp_arr(a,n);
if(l<up-1)
{
quick(a,n,l,up-1);
}
if(down<h)
{
quick(a,n,down,h);
}
}
//function to partition
void partition(int a[], int n, int s, int e)
{
int m;
if(s<e)
{
m=(s+e)/2;
partition(a,n,s,m);
partition(a,n,m+1,e);
merge(a,n,s,m,e);
}
}
//merge sort function
void merge(int a[], int n, int s, int m, int e)
{
int b[30],i,j,k;
i=s;j=m+1;k=s;
while(i<=m && j<=e)
{
if(a[i]<=a[j])
{
b[k]=a[i];
i++;k++;
}
else
{
b[k]=a[j];
j++;k++;
}
}
while(j<=e)
{
b[k]=a[j];
j++;k++;
}
while(i<=m)
{
b[k]=a[i];
i++;k++;
}
for(i=s;i<=e;i++)
{
a[i]=b[i];
}
}
0 comments:
Post a Comment