| Sr. No. |
NAME OF PROGRAM | DATE | REMARK | |
| 1. | Write a program to Implement Insertion Sort | | | |
| 2. | Write a program to Implemen Merge Sort | | | |
| 3. | Write a program to implement Heap Sort | | | |
| 4. | Write a program to implement Bucket Sort | | | |
| 5. | Write a program to implement Radix Sort | | | |
| 6. | Write a program to implement Rabin Karp string matching algorithm | | | |
| 7. | Write a program to implement counting Sort algo | | | |
| 8. | Write a program to implement quick sort | | | |
| 9. | Write a program to implement N Queen’s Problem. | | | |
| 10. | Writa a program to implement Brute Force String machine algorithm | | |
Faculty’s Signature
1.WAP to implement Insertion sort.
#include<stdio.h>
#include<conio.h>
void insertion(int a[],int n)
{
int i,j,x,k
;
for(i=1;i<=n-1;i++)
{
j=i;
x=a[i];
while(a[j-1]>x && j>0)
{
a[j]=a[j-1];
j=j-1;
}
a[j]=x;
printf("\n\n The array after pass no.%d: ",i);
for(k=0;k<=n-1;k++)
printf("%4d",a[k]);
}
}
void main()
{
int a[1000],n,i;
clrscr();
printf("\n\nEnter an integer value for total no.s of elements to be sorted: ");
scanf("%3d",&n);
for(i=0;i<=n-1;i++)
{
printf("\n\nEnter an integer value for element no.%d: ",i+1);
scanf("%4d",&a[i]);
}
insertion(a,n);
printf("\n\n\nFinally sorted array is : ");
for(i=0;i<=n-1;i++)
printf("%4d",a[i]);
}
2.WAP to implement Merge sort.
#include<stdio.h>
void getdata(int arr[],int n)
{
int i;
printf("enter the data:");
for(i=0;i<n;i+
+)
{
scanf("%d",&arr[i]);
}
}
void display(int arr[],int n)
{
int i;
printf("");
for(i=0;i<n;i++)
{
printf("%d ",arr[i]);
}
getchar();
}
void sort(int arr[],int low,int mid,int high)
{
int i,j,k,l,b[20];
l=low;
i=low;
j=mid+1;
while((l<=mid)&&(j<=high))
{
if(arr[l]<=arr[j])
{
b[i]=arr[l];
l++;
}
else
{
b[i]=arr[j];
j++;
}
i++;
}
if(l>mid)
{
for(k=j;k<=high;k++)
{
b[i]=arr[k];
i++;
}
}
else
{
for(k=l;k<=mid;k++)
{
b[i]=arr[k];
i++;
}
}
for(k=low;k<=high;k++)
{
arr[k]=b[k];
}
}
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);
sort(arr,low,mid,high);
}
}
void main()
{
int arr[20];
int n;
printf("Enter number of data:");
scanf("%d",&n);
getdata(arr,n);
partition(arr,0,n-1);
display(arr,n);
getchar();
}
3. WAP to implement Heap Sort.
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
void main()
{
int *x,i,n;
int temp;
void heap(int *,int);
clrscr();
fflush(stdin);
printf("Heap Sort");
printf("Enter How many Numbers : ");
scanf("%d",&n);
x = (int *)malloc(n * sizeof(int));
for(i=0;i<n;i++)
{
fflush(stdin);
scanf("%d",&x[i]);
}
heap(x,n);
for(i=n-1;i>=1;i--)
{
temp = x[i];
x[i] = x[0];
x[0] = temp;
heap(x,i-1);
}
printf("Resultant Array");
for(i=0;i<n;i++)
printf("%d",x[i]);
free(x);
getch();
}
void heap(int *a,int n)
{
int i,temp;
for(i=n/2;i>=0;i--)
{
if(a[(2*i)+1] < a[(2*i)+2] && (2*i+1)<=n && (2*i+2)<=n)
{
temp = a[(2*i)+1];
a[(2*i)+1] = a[(2*i)+2];
a[(2*i)+2] = temp;
}
if(a[(2*i)+1] > a[i] && (2*i+1)<=n && i<=n)
{
temp = a[(2*i)+1];
a[(2*i)+1] = a[i];
a[i] = temp;
}
}
}
4. WAP to implement bucket sort
#include <stdio.h>
#include <stdlib.h>
const int RANGE = 200;
enum SearchResult
{
FOUND,
NOT_FOUND
};
void initLookupTable(enum SearchResult lookup[], int array[], int sizeOfData, int RANGE)
{
int v;
for(int m=0; m<RANGE; m++)
{
lookup[m] = NOT_FOUND;
}
for(int mm=0; mm<sizeOfData; mm++)
{
v = array[mm];
lookup[v] = FOUND;
}
}
enum SearchResult searchLookupTable(enum SearchResult lookup[], int key)
{
return lookup[key];
}
void fill_array(int array[], int sizeOfData)
{
for (int i = 0; i<=sizeOfData; i++)
{
array[i] = rand() % RANGE;
}
}
void print_array(int array[], int sizeOfData)
{
for (int j = 0; j<=sizeOfData; j++)
{
printf("Item %d is %d\t", j, array[j]);
}
}
int main()
{
srand ( time (0) );
for (int ij=0; ij <100; ij++)
{
const int arraySize = 100;
int a [arraySize];
enum SearchResult lookup[RANGE];
enum SearchResult result;
int searchKey = rand() % RANGE;
fill_array(a, arraySize);
print_array(a, arraySize);
initLookupTable(lookup, a, arraySize, RANGE);
result = searchLookupTable(lookup, searchKey);
if (result == FOUND)
printf("\nKEY %d FOUND \n", searchKey);
else
printf("\nKEY %d NOT FOUND \n", searchKey);
}
return (0);
}
5.WAP to implement Radix sort.
#include <stdio.h>
#define MAX 5
#define SHOWPASS
void print(int *a,int n)
{
int i;
for(i=0;i<n;i++)
printf("%d\t",a[i]);
}
void radixsort(int *a,int n)
{
int i,b[MAX],m=0,exp=1;
for(i=0;i<n;i++)
{
if(a[i]>m)
m=a[i];
}
while(m/exp>0)
{
int bucket[10]={0};
for(i=0;i<n;i++)
bucket[a[i]/exp%10]++;
for(i=1;i<10;i++)
bucket[i]+=bucket[i-1];
for(i=n-1;i>=0;i--)
b[--bucket[a[i]/exp%10]]=a[i];
for(i=0;i<n;i++)
a[i]=b[i];
exp*=10;
#ifdef SHOWPASS
printf("\nPASS : ");
print(a,n);
#endif
}
}
int main()
{
int arr[MAX];
int i,n;
printf("Enter total elements (n < %d) : ",MAX);
scanf("%d",&n);
printf("Enter %d Elements : ",n);
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
printf("\nARRAY : ");
print(&arr[0],n);
radixsort(&arr[0],n);
printf("\nSORTED : ");
print(&arr[0],n);
printf("\n");
return 0;
}
6.Program to implement Rabin Karp String Matching Algorithm
#include<stdio.h>
#include<string.h>
#include<conio.H>
#include<math.H>
#include<iostream.h>
//Macro Defined
#define ToNum(c) (c >= 'A' && c <= 'Z' ? c - 'A' : c - 'a') //converts alphabets to numbers
//Function Declaration :
int RabinKarp(char *T,char *P,int d,int q) ;
void main()
{ char Text[]="Hello How are you. Fine. ";
char Pattern[]="llo";
int Radix=10; // Radix is 10 becoz we r using Decimal Number system.
int Prime=17 ; // I have taken 17 as a Prime Number, can be anything like 31, 37, 43, 103, 117 etc.
clrscr();
int ans=RabinKarp(Text,Pattern,Radix, Prime);
if(ans==-1)
printf("\nNot Found !"); // ans =-1 means Unsuccessful search
else
printf("\nFound at Pos. %d", ans); //Successful search
getch();
}
int RabinKarp(char *T,char *P,int d,int q)
{ int i,j,p,t,n,m,h,found;
n = strlen(T);
m = strlen(P);
h = (int)pow(d,m) %q;
cout<<endl<<d <<" "<< m << " " << q;
cout<<endl<<h;
h=Mod(d,m-1,q); //Please Check Is This OK ?
cout<<endl<<h;
p = t = 0;
for (i=0; i<m; i++)
{ p = (d*p + ToNum(P[i])) % q;
t = (d*t + ToNum(T[i])) % q;
}
for (i=0; i<=n-m; i++) //NOTE loop runs upto n-m
{ if (p == t)
{ found = 1;
for (j=0; j<m; j++)
{
if (P[j] != T[i+j])
{
found = 0;
break;
}
}
if (found)
return i; //found. Go back to main() with i
}
else
t = (d*(t - ((ToNum(T[i])*h) % q)) + ToNum(T[i+m])) % q;
}//end of for loop.
return -1; // at end of loop, return 1, coz, not found
} //end of function RabinKarp()
#include<string.h>
#include<conio.H>
#include<math.H>
#include<iostream.h>
//Macro Defined
#define ToNum(c) (c >= 'A' && c <= 'Z' ? c - 'A' : c - 'a') //converts alphabets to numbers
//Function Declaration :
int RabinKarp(char *T,char *P,int d,int q) ;
void main()
{ char Text[]="Hello How are you. Fine. ";
char Pattern[]="llo";
int Radix=10; // Radix is 10 becoz we r using Decimal Number system.
int Prime=17 ; // I have taken 17 as a Prime Number, can be anything like 31, 37, 43, 103, 117 etc.
clrscr();
int ans=RabinKarp(Text,Pattern,Radix, Prime);
if(ans==-1)
printf("\nNot Found !"); // ans =-1 means Unsuccessful search
else
printf("\nFound at Pos. %d", ans); //Successful search
getch();
}
int RabinKarp(char *T,char *P,int d,int q)
{ int i,j,p,t,n,m,h,found;
n = strlen(T);
m = strlen(P);
h = (int)pow(d,m) %q;
cout<<endl<<d <<" "<< m << " " << q;
cout<<endl<<h;
h=Mod(d,m-1,q); //Please Check Is This OK ?
cout<<endl<<h;
p = t = 0;
for (i=0; i<m; i++)
{ p = (d*p + ToNum(P[i])) % q;
t = (d*t + ToNum(T[i])) % q;
}
for (i=0; i<=n-m; i++) //NOTE loop runs upto n-m
{ if (p == t)
{ found = 1;
for (j=0; j<m; j++)
{
if (P[j] != T[i+j])
{
found = 0;
break;
}
}
if (found)
return i; //found. Go back to main() with i
}
else
t = (d*(t - ((ToNum(T[i])*h) % q)) + ToNum(T[i+m])) % q;
}//end of for loop.
return -1; // at end of loop, return 1, coz, not found
} //end of function RabinKarp()
7. WAP to impliment counting sort algorithm.
#include <stdlib.h>
void counting_sort(int array[], int size)
{
int i, min, max;
min = max = array[0];
for(i = 1; i < size; i++)
{
if (array[i] < min)
min = array[i];
else if (array[i] > max)
max = array[i];
}
int range = max - min + 1;
int *count = malloc(range * sizeof(int));
for(i = 0; i < range; i++)
count[i] = 0;
for(i = 0; i < size; i++)
count[ array[i] - min ]++;
int j, z = 0;
for(i = min; i <= max; i++)
for(j = 0; j < count[ i - min ]; j++)
array[z++] = i;
free(count);
}
void single_pass_counting_sort(int *array, int size, int range, int **output, int *next)
{
int key, i;
*output = ReserveAddressSpace(range*size*sizeof(int));
for(key = 0; key < range; key++)
next[key] = key*size;
for(i = 0; i < size; i++)
(*output)[next[array[i]]++] = array[i];
}
void iterate_over_sorted(int size, int range, int **output, int *next)
{
int key, i;
for(key = 0; key < range; key++)
for(i = key*size; i < next[key]; i++)
do_work((*output)[i]);
}
8.WAP to implement quicksort algorithm.
#include<stdio.h>
#include<conio.h>
#include<conio.h>
void main()
{
int arr[5],sarr[5],i,j,k;
int flag=0;
clrscr();
{
int arr[5],sarr[5],i,j,k;
int flag=0;
clrscr();
printf("Enter the Elements : \n");
for(i=0; i<5; i++)
{
scanf("%d",&arr[i]);
}
for(i=0; i<5; i++)
{
scanf("%d",&arr[i]);
}
printf("\n\nEntered Elements are : \n\n");
for(i=0; i<5; i++)
{
printf("%d\t",arr[i]);
}
for(i=0; i<5; i++)
{
printf("%d\t",arr[i]);
}
printf("\n\nSorted Elements are : \n\n");
sarr[0]=arr[0];
for(i=1; i<5; i++)
{
flag=0;
for(j=0; j<=i; j++)
{
if(arr[i]<sarr[j])
{
for(k=i; k>j; k--)
{
sarr[k]=sarr[k-1];
}
sarr[j]=arr[i];
flag=1;
break;
}
else if(arr[i]>sarr[j] && arr[i]<sarr[j+1])
{
for(k=i; k>j+1; k--)
{
sarr[k]=sarr[k-1];
}
sarr[j+1]=arr[i];
flag=1;
break;
}
}
f(flag==0)
{
sarr[i]=arr[i];
}
}
sarr[0]=arr[0];
for(i=1; i<5; i++)
{
flag=0;
for(j=0; j<=i; j++)
{
if(arr[i]<sarr[j])
{
for(k=i; k>j; k--)
{
sarr[k]=sarr[k-1];
}
sarr[j]=arr[i];
flag=1;
break;
}
else if(arr[i]>sarr[j] && arr[i]<sarr[j+1])
{
for(k=i; k>j+1; k--)
{
sarr[k]=sarr[k-1];
}
sarr[j+1]=arr[i];
flag=1;
break;
}
}
f(flag==0)
{
sarr[i]=arr[i];
}
}
for(i=0; i<5; i++)
{
printf("%d\t",sarr[i]);
}
{
printf("%d\t",sarr[i]);
}
getch();
}
}
9.WAP to implement N-Queen Problem using backtracking approach.
#include< stdio.h>
#include< conio.h>
#include< math.h>
char a[10][10];
int n;
void printmatrix()
{
int i,j;
printf("\n");
for(i=0;i < n;i++)
{
for(j=0;j < n;j++)
printf("%c\t",a[i][j]);
printf("\n\n");
}
}
int getmarkedcol(int row)
{
int i,j;
for(i=0;i < n;i++)
if(a[row][i]=='Q')
{
return(i);
break;
}
}
int feasible(int row, int col)
{
int i,tcol;
for(i=0;i < n;i++)
{
tcol=getmarkedcol(i);
if(col==tcol || abs(row-i)==abs(col-tcol))
return 0;
}
return 1;
}
void nqueen(int row)
{
int i,j;
if(row < n)
{
for(i=0;i < n;i++)
if(feasible(row,i))
a[row][i]='Q';
nqueen(row+1);
a[row][i]='.';
}
}
}
else
{
printf("\nThe solution is:- ");
printmatrix();
}
}
void main()
{
int i,j;
clrscr();
printf("\n Enter the no. of queens:- ");
scanf("%d",&n);
for(i=0;i < n;i++)
for(j=0;j < n;j++)
a[i][j]=' ,’;
nqueen(0);
getch();
}
10.WAP to implement brute force string matching algorithm.
#include<stdio.h>
#include<conio.h>
int main(void)
{
long int p,q,e,n,inv,s=0,d=1,C[100],M;
char m[100];
unsigned long int c;
int i,j,t;
printf("Enter the value of p and q: ");
scanf("%d%d",&p,&q);
n=p*q;
inv=(p-1)*(q-1);
printf("\nEnter the e value: ");
scanf("%d",&e);
do
{
s=(d*e)%inv;
d++;
}while(s!=1);
d=d-1;
printf("\nEnter the message to encrypt:");
scanf("%s",&m);
for(j=0;j<strlen(m);j++)
{
m[j]=tolower(m[j]);
t=m[j]-96;
c=1;
for(i=0;i<e;i++)
c=c*t%n;
c=c%n;
printf("%d ",c);
}
printf("\n\nEnter encrypted message to decrpyt :\n");
for(i=0;i<strlen(m);i++)
scanf("%d",&C[i]);
printf("\n\nDecrypted (original) message: ");
for(j=0;j<strlen(m);j++)
{
M=1;
for(i=0;i<d;i++)
M=M*C[j]%n;
M=M%n;
M=M+96;
printf("%c",M);
}
getch();
return 0;
}
No comments:
Post a Comment