Aim: To sort elements by heap order( max heap) in C program
program:
#include<stdio.h>
void main()
{
int n,a[50],i;
clrscr();
printf("enter elements to be entered");
scanf("%d",&n); printf("enter elements");
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
heapsort(a,n);
printf("after sorting the elements are");
for(i=1;i<=n;i++)
printf("%d ",a[i]);
getch();
}
int heapsort(int a[],int n)
{
int t,i; heapify(a,n);
for(i=n;i>=2;i--)
{
t=a[i];
a[i]=a[1];
a[1]=t;
adjust(a,1,i-1);
}
return;
}
int heapify(int a[],int n)
{
int i; for(i=n/2;i>=1;i--)
adjust(a,i,n);
return;
}
int adjust(int a[],int i,int n)
{
int j,item,t;
j=2*i; item=a[i];
while(j<=n)
{
if(j<n && a[j]<a[j+1])
j=j+1;
if(item<=a[j])
{
t=a[j/2];
a[j/2]=a[j];
a[j]=t;
}
j=2*j;
}
}
Output:
Aim : To Implement Quick Sort Using C program
Program:
#include<stdio.h>
int a[50];
void main()
{
int i,n;
clrscr();
printf(" Enter no of elements to be entered");
scanf("%d",&n);
printf("\n Enter elements");
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
quicksort(1,n);
printf("\nElements after sorting");
for(i=1;i<=n;i++)
printf("%d ",a[i]);
getch();
}
int quicksort(int low,int high)
{
int j;
if(low<high)
{
j=partition(low,high);
quicksort(low,j-1);
quicksort(j+1,high);
}
return;
}
int partition(int low,int high)
{
int i,j,temp,pivot;
i=low;
j=high+1;
pivot=a[low];
while(i<j)
{
do
{
i=i+1;
}while(i<high && pivot>=a[i]);
do
{
j=j-1;
}while(j>low && pivot<=a[j]);
if(i<j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
a[low]=a[j];
a[j]=pivot;
return j;
}
Output:
Aim: Merge Sort Using C program
Program:
#include<stdio.h>
void main()
{
int i,a[50],n;
clrscr();
printf(" Enter no of elements to be entered");
scanf("%d",&n);
printf(" Enter elements");
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
mergesort(a,1,n);
printf(" Merge sort=");
for(i=1;i<=n;i++)
printf("%d ",a[i]);
getch();
}
int 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,mid,high);
}
return;
}
int merge(int a[],int low,int mid,int high)
{
int i,j,k,l,b[50];
i=low;
j=mid+1;
k=low;
while(i<=mid&&j<=high)
{
if(a[i]<a[j])
{
b[k]=a[i];
i++;
}
else
{
b[k]=a[j];
j++;
}
k++;
}
if(i>mid)
{
for(l=j;l<=high;l++)
{
b[k]=a[l];
k++;
}
}
else
{
for(l=i;l<=mid;l++)
{
b[k]=a[l];
k++;
}
for(l=low;l<=high;l++)
{
a[l]=b[l];
}
}
}
Merge Sort:
Merge sort is an algorithm that has a fairly efficient space time complexity -
O(n log n) and is fairly trivial to implement. The algorithm is based on splitting
a list, into two similar sized lists (left, and right) and sorting each list and then
merging the sorted lists back together.
Note: the function MergeOrdered simply takes two ordered lists and makes
them one.
Output:
Aim : To write Insertion Sorting Program in C program
Program:
#include<stdio.h>
void main()
{
int a[50],n,i;
clrscr();
printf("\n Enter no of elements to be entered");
scanf("%d",&n);
printf(" Enter elements");
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
insort(a,n);
printf(" Insertion sorting");
for(i=1;i<=n;i++)
printf(" %d",a[i]);
getch();
}
insort(int a[],int n)
{
int k,ele,loc;
for(k=2;k<=n;k++)
{
ele=a[k];
loc=k-1;
while(loc>=1&&ele<a[loc])
{
a[loc+1]=a[loc];
loc=loc-1;
}
a[loc+1]=ele;
}
}
Output :
Aim: To write a Bubble Sort Program using C program
Program :
#include<stdio.h>
void main()
{
int a[20],n,i;
clrscr();
printf(" Enter the size of the list");
scanf("%d",&n);
printf(" Enter the elements :");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
bubblesort(a,n); //sort the elements using bubble sort
printf(" Bubble sort");
for(i=0;i<n;i++)
printf(" %d",a[i]);
getch();
}
bubblesort(int a[],int n)
{
int i,j,temp;
for(i=0;i<n-1;i++)
{
for(j=0;j<n-i-1;j++)
{
if(a[j] > a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
}
Output:
