INDEX s.no | Name of program | Page no. | Remarks | SORTING PROGRAMS | 1 | program of merge sort | | | 2 | program of quick sort | | | 3 | program of bubble sort | | | 4 | program of insertion sort | | | 5 | program of selection sort | | | SEARCHING PROGRAMS | 6 | program of binary search iterative method | | | 7 | Program of binary search by recursive method | | | MULTIPLICATION PROGRAMS | 8 | program to multiply two matrices using direct method | | | 9 | program to multiply two matrices using recursion | | | 10 | program to multiply two matrices using strassen's method | | |

//program of merge sort
#include<stdio.h>
#include<conio.h>
#define MAX 50 void mergeSort(int arr[],int low,int mid,int high); void partition(int arr[],int low,int high); int main()
{
int merge[MAX],i,n; clrscr(); printf("Enter the total number of elements: "); scanf("%d",&n); printf("Enter the elements which to be sort: "); for(i=0;i<n;i++) { scanf("%d",&merge[i]); } partition(merge,0,n-1); printf("After merge sorting elements are: "); for(i=0;i<n;i++) { printf("%d ",merge[i]); } getch(); } void partition(int arr[],int low,int high)
{
int mid; if(low<high) { mid=(low+high)/2; partition(arr,low,mid); partition(arr,mid+1,high); mergeSort(arr,low,mid,high); }
}
void mergeSort(int arr[],int low,int mid,int high)
{
int i,m,k,l,temp[MAX]; l=low; i=low; m=mid+1; while((l<=mid)&&(m<=high)) { if(arr[l]<=arr[m]) { temp[i]=arr[l]; l++; } else { temp[i]=arr[m]; m++; } i++; } if(l>mid) { for(k=m;k<=high;k++) { temp[i]=arr[k]; i++; } } else { for(k=l;k<=mid;k++) { temp[i]=arr[k]; i++; } } for(k=low;k<=high;k++) { arr[k]=temp[k]; }
}

//program of quick sort
#include<stdio.h>
#include<conio.h> void quicksort(int [10],int,int); int main()
{
int x[20],size,i; clrscr(); printf("Enter size of the array: "); scanf("%d",&size); printf("Enter %d elements: ",size); for(i=0;i<size;i++) scanf("%d",&x[i]); quicksort(x,0,size-1); printf("Sorted elements after quick sort are: "); for(i=0;i<size;i++) printf(" %d",x[i]); getch();
}
void quicksort(int x[10],int first,int last){ int pivot,j,temp,i; if(first<last) { pivot=first; i=first; j=last; while(i<j) { while(x[i]<=x[pivot]&&i<last) i++; while(x[j]>x[pivot]) j--; if(i<j) { temp=x[i]; x[i]=x[j]; x[j]=temp; } } temp=x[pivot]; x[pivot]=x[j]; x[j]=temp; quicksort(x,first,j-1); quicksort(x,j+1,last); }
}

//program of bubble sort
#include<stdio.h>
#include<conio.h> void main()
{
int i,n,temp,j,arr[25]; clrscr(); printf("Enter the number of elements in the Array: "); scanf("%d",&n); printf("\nEnter the elements:\n\n"); for(i=0 ; i<n ; i++) { printf(" Array[%d] = ",i); scanf("%d",&arr[i]); } for(i=0 ; i<n ; i++) { for(j=0 ; j<n-i-1 ; j++) { if(arr[j]>arr[j+1]) //Swapping Condition is Checked { temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; } } } printf("\nThe Sorted Array is:\n\n"); for(i=0 ; i<n ; i++) { printf(" %4d",arr[i]); } getch(); }

//program of insertion sort
#include<stdio.h>
#include<conio.h> int main()
{
int i,j,s,temp,a[20]; clrscr(); printf("Enter total elements: "); scanf("%d",&s); printf("Enter %d elements: ",s); for(i=0;i<s;i++) scanf("%d",&a[i]); for(i=1;i<s;i++) { temp=a[i]; j=i-1; while((temp<a[j])&&(j>=0)) { a[j+1]=a[j]; j=j-1; } a[j+1]=temp; } printf("After insertion sorting: "); for(i=0;i<s;i++) printf(" %d",a[i]); getch(); }

//program of selection sort
#include<stdio.h>
#include<conio.h> int main()
{
int s,i,j,temp,a[20]; clrscr(); printf("Enter total elements: "); scanf("%d",&s); printf("Enter %d elements: ",s); for(i=0;i<s;i++) scanf("%d",&a[i]); for(i=0;i<s;i++) { for(j=i+1;j<s;j++) { if(a[i]>a[j]) { temp=a[i]; a[i]=a[j]; a[j]=temp; } } } printf("After selection sorting is: "); for(i=0;i<s;i++) printf(" %d",a[i]); getch();
}

//program of binary search by iterative method
#include<stdio.h>
#include<conio.h>
#define MAX 10 int main()
{
int a[10],i,n,m,c=0,l,u,mid; clrscr(); printf("\n Enter the size of the array"); scanf("%d",&n); printf("\n Enter the elements in ascending order:"); for(i=0;i<n;i++) { scanf("%d",&a[i]); } printf("\n Enter the element to be searched:"); scanf("%d",&m); l=0,u=n-1; while(l<=u) { mid=(l+u)/2; if(m==a[mid]) { c=1; break; } else if(m<a[mid]) { u=mid-1; } else l=mid+1; } if(c==0) printf("\n The search is unsucessful"); else printf("The search is sucessful"); getch(); }

//program of binary search by recursive method
#include <stdio.h>
#include <conio.h> int bin_srch(int a[], int n, int key, int low, int high) { int mid; if(low <= high) { mid = (low + high)/2; if(a[mid] == key) { return mid; } else if(key < a[mid]) { return bin_srch(a, n, key, low, mid-1); } else if(key > a[mid]) { return bin_srch(a, n, key, mid+1, high); } } else { return -1; } } int main() { int a[10], n, key, low, mid, high, i, indx; printf("\nEnter size of array: "); scanf("%d", &n); printf("\nEnter elements of array: "); for(i=0;i<n;i++) { scanf("%d", &a[i]); } printf("\nEnter the key element to be searched: "); scanf("%d", &key); low = 0; high = n-1; indx = bin_srch(a, n, key, low, high); if(indx == -1) { printf("\nSearch unsuccessful"); } else { printf("\nElement found at position %d\n\n", indx+1); } }

//Program of matrix multiplication
#include<stdio.h>
#include<conio.h> int main()
{
int a[5][5],b[5][5],c[5][5],i,j,k,sum=0,m,n,o,p; printf("\nEnter the row and column of first matrix"); scanf("%d %d",&m,&n); printf("\nEnter the row and column of second matrix"); scanf("%d %d",&o,&p); if(n!=o) { printf("Matrix mutiplication is not possible"); printf("\nColumn of first matrix must be same as row of second matrix"); } else { printf("\nEnter the First matrix->"); for(i=0;i<m;i++) for(j=0;j<n;j++) scanf("%d",&a[i][j]); printf("\nEnter the Second matrix->"); for(i=0;i<o;i++) for(j=0;j<p;j++) scanf("%d",&b[i][j]); printf("\nThe First matrix is\n"); for(i=0;i<m;i++) { printf("\n"); for(j=0;j<n;j++) { printf("%d\t",a[i][j]); } } printf("\nThe Second matrix is\n"); for(i=0;i<o;i++) { printf("\n"); for(j=0;j<p;j++) { printf("%d\t",b[i][j]); } } for(i=0;i<m;i++) for(j=0;j<p;j++) c[i][j]=0; for(i=0;i<m;i++) { //row of first matrix for(j=0;j<p;j++) { //column of second matrix sum=0; for(k=0;k<n;k++) sum=sum+a[i][k]*b[k][j]; c[i][j]=sum; } } } printf("\nThe multiplication of two matrix is\n"); for(i=0;i<m;i++) { printf("\n"); for(j=0;j<p;j++) { printf("%d\t",c[i][j]); } } getch(); }

//progrm to multiply two matrices by recursion:
#include<stdio.h>
#include<conio.h>
#define MAX 10 void multiplyMatrix(int [MAX][MAX],int [MAX][MAX]); int m,n,o,p; int c[MAX][MAX]; int main()
{
int a[MAX][MAX],b[MAX][MAX],i,j,k; clrscr(); printf("Enter the row and column of first matrix: "); scanf("%d %d",&m,&n); printf("Enter the row and column of second matrix: "); scanf("%d %d",&o,&p); if(n!=o) { printf("Matrix multiplication is not possible"); printf("\nColumn of first matrix must be same as row of second matrix"); } else { printf("Enter the First matrix: "); for(i=0;i<m;i++) for(j=0;j<n;j++) scanf("%d",&a[i][j]); printf("Enter the Second matrix: "); for(i=0;i<o;i++) for(j=0;j<p;j++) scanf("%d",&b[i][j]); printf("\nThe First matrix is: \n"); for(i=0;i<m;i++) { printf("\n"); for(j=0;j<n;j++) { printf("%d\t",a[i][j]); } } printf("\nThe Second matrix is: \n"); for(i=0;i<o;i++) { printf("\n"); for(j=0;j<p;j++) { printf("%d\t",b[i][j]); } } multiplyMatrix(a,b); } printf("\nThe multiplication of two matrix is: \n"); for(i=0;i<m;i++) { printf("\n"); for(j=0;j<p;j++) { printf("%d\t",c[i][j]); } } getch();
}
void multiplyMatrix(int a[MAX][MAX],int b[MAX][MAX]){ static int sum,i=0,j=0,k=0; if(i<m) { //row of first matrix if(j<p) { //column of second matrix if(k<n) { sum=sum+a[i][k]*b[k][j]; k++; multiplyMatrix(a,b); } c[i][j]=sum; sum=0; k=0; j++; multiplyMatrix(a,b); } j=0; i++; multiplyMatrix(a,b); }
}

//program to multiply two matrices using strassen's method
#include<stdio.h>
#include<conio.h> int main()
{
int a[2][2],b[2][2],c[2][2],i,j; int m1,m2,m3,m4,m5,m6,m7; printf("Enter the 4 elements of first matrix: "); for(i=0;i<2;i++) for(j=0;j<2;j++) scanf("%d",&a[i][j]); printf("Enter the 4 elements of second matrix: "); for(i=0;i<2;i++) for(j=0;j<2;j++) scanf("%d",&b[i][j]); printf("\nThe first matrix is\n"); for(i=0;i<2;i++){ printf("\n"); for(j=0;j<2;j++) printf("%d\t",a[i][j]); } printf("\nThe second matrix is\n"); for(i=0;i<2;i++){ printf("\n"); for(j=0;j<2;j++) printf("%d\t",b[i][j]); } m1= (a[0][0] + a[1][1])*(b[0][0]+b[1][1]); m2= (a[1][0]+a[1][1])*b[0][0]; m3= a[0][0]*(b[0][1]-b[1][1]); m4= a[1][1]*(b[1][0]-b[0][0]); m5= (a[0][0]+a[0][1])*b[1][1]; m6= (a[1][0]-a[0][0])*(b[0][0]+b[0][1]); m7= (a[0][1]-a[1][1])*(b[1][0]+b[1][1]); c[0][0]=m1+m4-m5+m7; c[0][1]=m3+m5; c[1][0]=m2+m4; c[1][1]=m1-m2+m3+m6; printf("\nAfter multiplication using strassen methods: \n"); for(i=0;i<2;i++) { printf("\n"); for(j=0;j<2;j++) printf("%d\t",c[i][j]); } getch();
}