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 :
Binary search without recursion c program
Program:
#include<stdio.h>
void main()
{
int a[50],n,i,key,f;
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]);
printf("enter the key to search");
scanf("%d",&key);
f=bsearch(a,n,key);
if(f==0)
printf("the key not found");
else
printf("the %d is found at %d",key,f);
getch();
}
int bsearch(int a[],int n,int key)
{
int low=1,high=n,mid;
while(low<=high)
{
mid=(low+high)/2;
if(key==a[mid])
return mid;
else if(key>a[mid])
low=mid+1;
else
high=mid+1;
}
return 0;
}
Output:
TOWERS OF HANOIC CPROGRAM WITH RECURSION
#include<stdio.h>
void main()
{
int n;
clrscr();
printf("enter no of disks=");
scanf("%d",&n);
towersofhanoi(n,'A','B','C');
getch();
}
int towersofhanoi(int n,char source,char dest,char inter)
{
if(n>=1)
{
towersofhanoi(n-1,source,inter,dest);
printf("\nmove disk from %c to tower %c ",source,dest);
towersofhanoi(n-1,inter,dest,source);
}
}
Binary Search With Recursion Using C program
Program:
#include<stdio.h>
void main()
{
int a[50],n,i,key,f;
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]);
printf("enter the key to search");
scanf("%d",&key);
f=bsearch(a,n,key);
if(f==0)
printf("the key not found");
else
printf("the %d is found at %d",key,f);
getch();
}
int bsearch(int a[],int n,int key)
{
int low=1,high=n,mid;
while(low<=high)
{
mid=(low+high)/2;
if(key==a[mid])
return mid;
else if(key>a[mid])
low=mid+1;
else
high=mid+1;
}
return 0;
}
Output:
#include<stdio.h>
2's complement cprogram
#include<string.h>
void main()
{
char b[20];
int i,j,l;
clrscr();
printf("Enter a binary num");
scanf("%s",b);
l=strlen(b);
for(i=l-1;i>=0;i--)
{
if(b[i]=='1')
{
for(j=i-1;j>=0;j--)
{
if(b[j]=='1')
b[j]='0';
else
b[j]='1';
}
}
}
printf("2's compliment is %s",b);
getch();
}
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:
Linear Search Without Recursion Using C Program
Program:
#include<stdio.h>
void main()
{
int a[50],n,f,key,i;
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]);
printf("enter the key value to find");
scanf("%d",&key);
f=lsearch(a,n,key);
if(f==0)
printf("the key not found");
else
printf("the %d is found at %d",key,f);
getch();
}
int lsearch(int a[],int n,int key)
{
int i;
for(i=1;i<=n;i++)
{
if(a[i]==key)
return i;
}
return 0;
}
Output:
Linear Search With Recursion Using C program
Program:
#include<stdio.h>
void main()
{
int n,a[20],i,j,key;
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]);
printf("enter the key to search");
scanf("%d",&key);
j=rlsearch(a,1,n,key);
if(j==0)
printf("the element is not found");
else
printf("the element found at %d",j);
getch();
}
int rlsearch(int a[],int i,int n,int key)
{
if(i>n)
return 0;
if(a[i]==key)
return i;
else
return rlsearch(a,i+1,n,key);
}
Output:
