1) Write a program to sort N numbers using Merge sort techniques
#include<stdio.h>
#include<conio.h>
merge(int a[],int low,int high,int mid)
{
int i,j,k,c[50];
i=low;
j=mid+1;
k=low;
while((i<mid)&&(j<=high))
{
if(a[i]<a[j])
{
c[k]=a[i];
k++;
i++;
}
else
{
c[k]=a[j];
k++;
j++;
}
}
while(i<=mid)
{
c[k]=a[i];
k=k++;
i=i++;
}
while(j<=high)
{
c[k]=a[j];
k=k++;
j=j++;
}
for(i=low;i<k;i++)
{
a[i]=c[i];
}
return 0;
}
mergesort(int a[],int low,int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
mergesort(a,low,mid);
mergesort(a,mid+1,high);
merge(a,low,high,mid);
}
return (0);
}
void main()
{
int a[10];
int i,n;
clrscr();
printf("Enter the number of elements: ");
scanf("%d",&n);
printf("Enter the elements :\n");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
mergesort(a,0,n-1);
printf("The sorted elemnts are \n");
for(i=0;i<n;i++)
printf("%d\n",a[i]);
getch();
}
2) Write a program to sort N numbers using Quick sort technique.
#include<stdio.h>
#include<conio.h>
void quicksort(int a[],int low,int high);
int partition(int a[],int low,int high);
void quicksort(int a[],int low,int high)
{
int k;
if(low<high)
{
k=partition(a,low,high);
quicksort(a,low,k-1);
quicksort(a,k+1,high);
}
}
int partition(int a[],int low,int high)
{
int key,i,j,temp;
key=a[low];
i=low;
j=high+1;
while(i<=j)
{
do
{
i=i+1;
}
while(key>=a[i]);
do
{
j=j-1;
}
while(key<a[j]);
{
if(i<j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}}
}
temp=a[low];
a[low]=a[j];
a[j]=temp;
return j;
}
void main()
{
int i,n,a[10];
clrscr();
printf("\n Enter the number of elements: \n");
scanf("%d",&n);
printf("\nEnter the elements");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
quicksort(a,0,n-1);
printf("\n Sorted array is \n");
for(i=0;i<n;i++)
printf("%d\n",a[i]);
getch();
}
3) Write a program to sort N numbers using Selection Sort
#include<stdio.h>
#include<conio.h>
void main()
{
int a[20],i,j,n,pos,temp;
printf("Enter the value of n: ");
scanf("%d",&n);
printf("\nEnter the elements of array\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=0;i<n;i++)
{
pos=i;
for(j=i+1;j<n;j++)
{
if(a[j]<a[pos])
{
pos=j;
}
}
temp=a[pos];
a[pos]=a[i];
a[i]=temp;
}
printf("sorted array is: \n");
for(i=0;i<n;i++)
printf("%d\n",a[i]);
getch();
}
4) Write a program to find the minimum and maximum number in a set of N numbers using
divide and conquer method
#include<stdio.h>
#include<conio.h>
void maxmin(int,int);
int max,min,i,j,mid,a[10],n;
void maxmin(int i,int j)
{
int min1,min2,max1,max2;
if(i==j)
max=min=a[i];
else
if(i==j-1)
{
if(a[i]>a[j])
{
max=a[i];
min=a[j];
}
else
{
max=a[j];
min=a[i];
}
}
else
{
mid=(i+j)/2;
maxmin(i,mid);
min1=min;
max1=max;
maxmin(mid+1,j);
min2=min;
max2=max;
if(max1<max2)
max=max2;
else
max=max1;
if(min1>min2)
min=min2;
else
min=min1;
}
}
void main()
{
int n;
clrscr();
printf("Enter size;\n");
scanf("%d",&n);
printf("Enter Elements: \n");
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
maxmin(1,n);
printf("Max=%d \n,Min=%d\n",max,min);
getch();
}
