/*----------------------------------------------------------------------------------------------
Program : Implement Sorting Methods using recursion
–
1. Quick Sort
2. Merge Sort.
Name : JABIR DAUD PATHAN
Branch : COMPUTER ENGINEERING
----------------------------------------------------------------------------------------------*/
/*--------------------<< Header File
>>---------------------*/
#include<stdio.h>
#include<conio.h>
/*------------<<
Global Declaration of Functions
>>-----------*/
void
accept(int[]);
void
display(int[]);
int
part(int[],int,int);
void
quicksort(int[],int,int);
void
merge_sort(int[],int,int);
void
merge(int[],int,int,int);
int
a[20],n,i,ch; //Global Declaration of variables
/*-----<<
function defination for accept array element >>-----*/
void
accept(int a[])
{
printf("\nHow many elements you want to
enter in array==>");
scanf("%d",&n);
printf("\nEnter elements==>\n");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]); //accept
array element from user
}
printf("\nAccepted elements
are==>\n");
for(i=0;i<n;i++)
{
printf("\na[%d]=%d",i,a[i]);
//display accepted element
}
}
/*-----<<
function defination for display array element >>-----*/
void
display(int a[])
{
printf("\n\nSorted elements
are==>\n");
for(i=0;i<n;i++)
{
printf("\na[%d]=%d",i,a[i]);//display sorted list
}
}
/*-------<<
function defination for Merge sort >>------*/
void
merge_sort(int a[],int i,int j)
{
int k;
if(i<j)
{
k=(i+j)/2;
merge_sort(a,i,k);
merge_sort(a,k+1,j);
merge(a,i,k,j);
}
}
void
merge(int a[],int l,int m,int u)
{
int i,j,k,c[20];
k=0;
i=l;
j=m+1;
while(i<=m&&j<=u)
{
if(a[i]<a[j])
{
c[k]=a[i];
i++;
k++;
}
else
{
c[k]=a[j];
j++;
k++;
}
}
while(i<=m)
{
c[k]=a[i];
i++;
k++;
}
while(j<=u)
{
c[k]=a[j];
j++;
k++;
}
for(i=l,j=0;i<=u;i++,j++)
{
a[i]=c[j];
}
}
/*-------<<
function defination for Quick sort >>------*/
void
quicksort(int a[],int l,int u)
{
int j;
if(l<u)
{
j=part(a,l,u);
quicksort(a,l,j-1);
quicksort(a,j+1,u);
}
}
int
part(int a[],int l,int u)
{
int k,v,i,j,temp;
v=a[l];
i=l;
j=u+1;
do
{
do
i++;
while(a[i]<v&&i<=u);
do
j--;
while(v<a[j]);
if(i<j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}while(i<j);
a[l]=a[j];
a[j]=v;
return(j);
}
/*-----------<< Main Function Starts >>------------*/
void
main()
{
char ans;//variable declaration
do
{
clrscr();
printf("\n\t\t\t-------<< MENU
>>------");
printf("\n\n\t\t\t1.Quick Sort");
printf("\n\t\t\t2.Merge Sort");
printf("\n\t\t\t3.Exit");
printf("\n\n\t\t\t-----------------------");
printf("\n\n\t\t\tEnter your
choice==>");
scanf("%d",&ch); //accept
choice from user
switch(ch)
{
case 1:
accept(a);
quicksort(a,0,n-1); //function call
display(a);
break;
case 2:
accept(a);
merge_sort(a,0,n-1);
display(a);
break;
case 3:
exit(0);
break;
default:
printf("\ninvalid choice");
break;
}
printf("\n\nDo you want to
continue(Y/N)?==>");
ans=getch();
}while(ans=='Y'||ans=='y');
getch();
}
/*-----------<< End Of Main Function >>-----------*/
/*-----------------<< OUTPUT
SCREEN >>-------------------*/
-------<< MENU
>>------
1.Quick Sort
2.Merge Sort
3.Exit
-----------------------
Enter your
choice==>1
How
many elements you want to enter in array==>5
Enter
elements==>
7
5
6
8
3
Accepted
elements are==>
a[0]=7
a[1]=5
a[2]=6
a[3]=8
a[4]=3
Sorted
elements are==>
a[0]=3
a[1]=5
a[2]=6
a[3]=7
a[4]=8
Do
you want to continue(Y/N)?==>Y
-------<< MENU
>>------
1.Quick Sort
2.Merge Sort
3.Exit
-----------------------
Enter your
choice==>2
How
many elements you want to enter in array==>5
Enter
elements==>
6
4
5
2
1
Accepted
elements are==>
a[0]=6
a[1]=4
a[2]=5
a[3]=2
a[4]=1
Sorted
elements are==>
a[0]=1
a[1]=2
a[2]=4
a[3]=5
a[4]=6
Do
you want to continue(Y/N)?==>Y
-------<< MENU
>>------
1.Quick Sort
2.Merge Sort
3.Exit
-----------------------
Enter your
choice==>3
No comments:
Post a Comment