Notes

PROGRAM 1: Program for insertion sort algorithm
Source code:
#include <stdio.h>
#include <stdlib.h>
void insertionSort(int a[ ], int n)
{
int i, j, key;
for (j = 1; j < n; j++)
{
key = a[j];
i = j - 1;
while (i >= 0 && key < a[i])
{
a[i + 1] = a[i];
i--;
}
a[i + 1] = key;
}
}

int main()
{
int i, a[100], n;
printf("n Enter the size of the array: ");
scanf("%d", &n);
printf("n Enter the elements of the array: n");
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
printf("nBefore Sorting: ");
for (i = 0; i < n; i++)
printf("%dt", a[i]);
insertionSort(a, n);
printf("nAfter Sorting: ");
for (i = 0; i < n; i++)
printf("%dt", a[i]);
return 0;
}


Output:


PROGRAM 2: Program for Selection sort algorithm
Source code:
#include <stdio.h>
void SelectSort(int a[], int n);
int main()
{
int a[100], n, i;
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter the elements of array: n");
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
SelectSort(a, n);
return 0;
}

void SelectSort(int a[], int n)
{
int i, j, position, swap;
for (i = 0; i < (n - 1); i++)
{
position = i;
for (j = i + 1; j < n; j++)
{
if (a[position] > a[j])
position = j;
}
if (position != i)
{
swap = a[i];
a[i] = a[position];
a[position] = swap;
}
}
printf("Sorted Array:t");
for (i = 0; i < n; i++)
printf("%dt", a[i]);
}
Output:



PROGRAM 3: Program to implement Bubble Sort algorithm.
Source code:
#include <stdio.h>
void bubbleSort(int array[], int size)
{
for (int step = 0; step < size - 1; ++step)
{
for (int i = 0; i < size - step - 1; ++i) {
if (array[i] > array[i + 1]) {
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
}
}
}
}
int main()
{
int i,size;
printf("Enter the total number of elements: ");
scanf("%d",&size);
int data[size];
printf("Enter the element of array: n");
for(i=0;i<size;i++)
{
scanf("%d",&data[i]);
}
bubbleSort(data, size);
printf("Sorted Array: ");
for(i=0;i<size;i++){
printf(" %dt",data[i]);
}
}
Output:





3. IMPLEMENTATION:
PROGRAM : To find the GCD of two integer.
Source code:
#include <stdio.h>
int gcdExtended(int a, int b, int *x, int *y)
{
if (a == 0)
{
*x = 0;
*y = 1;
return b;
}
int x1, y1;
int gcd = gcdExtended(b%a, a, &x1, &y1);
*x = y1 - (b/a) * x1;
*y = x1;

return gcd;
}
int main()
{
int x, y, b ,a;
printf("nEnter the numbers a & b: n");
scanf("%d%d",&a,&b);
int g = gcdExtended(a, b, &x, &y);
printf("gcd(%d, %d) = %d", a, b, g);
return 0;
}
Output:



PROGRAM 1: program to implement merge sort.
Source code:
#include <stdio.h>
void merge(int arr[ ], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;

int L[n1], R[n2];

for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];

i = 0; j = 0; k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else { arr[k] = R[j];
j++; }
k++; }

while (i < n1) {
arr[k] = L[i];
i++;
k++; }
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}}
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;

mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);

merge(arr, l, m, r);}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("n");}

int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int arr_size = sizeof(arr) / sizeof(arr[0]);

printf("Unsorted array: n");
printArray(arr, arr_size);

mergeSort(arr, 0, arr_size - 1);

printf("Sorted array: n");
printArray(arr, arr_size);

return 0;
}
Output:


PROGRAM 2: program to implement quick sort.
Source code:
#include<stdio.h>
void quicksort(int number[25],int first,int last){
int j;
if(first<last){
j=partition(number,first,last);
quicksort(number,first,j-1);
quicksort(number,j+1,last);
}
}
int partition(int number[],int i,int j){
int l, r, pivot, temp;
pivot=i;
l=i;
r=j;
while(l<r){
while(number[l]<=number[pivot]&&l<=j){
l++;
}
while(number[r]>number[pivot]){
r--;
}

if(l<r){
temp=number[l];
number[l]=number[r];
number[r]=temp;
}
}
temp=number[pivot];
number[pivot]=number[r];
number[r]=temp;
return r;
}
int main(){
int i, count, number[25];
printf("Enter the total number of elements: ");
scanf("%d",&count);
printf("Enter the element of array: n");
for(i=0;i<count;i++)
{
scanf("%d",&number[i]);
}
quicksort(number,0,count-1);
printf("Sorted array: ");
for(i=0;i<count;i++){
printf(" %dt",number[i]);
}

return 0;
}

Output:


3. IMPLEMENTATION:
PROGRAM 1: To implement the heap sort algorithm in c program
Source code:
#include <stdio.h>
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}

void heapify(int arr[ ], int n, int i)
{
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;

if (left < n && arr[left] > arr[largest])
largest = left;

if (right < n && arr[right] > arr[largest])
largest = right;

if (largest != i)
{
swap(&arr[i], &arr[largest]);
heapify(arr, n, largest);
}
}

void heapSort(int arr[ ], int n)
{

for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);

for (int i = n - 1; i >= 0; i--)
{
swap(&arr[0], &arr[i]);

heapify(arr, i, 0);
}
}

int main()
{

int i, n, arr[25];
printf("Enter the total number of elements: ");
scanf("%d", &n);
printf("Enter the element of array: n");
for (i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
heapSort(arr, n);
printf("Sorted array: ");
for (i = 0; i < n; i++)
{
printf(" %dt", arr[i]);
}
}
Output:


3. IMPLEMENTATION:
PROGRAM : To implement the Longest Common Subsequences Problem. in c program
Source code:
#include <stdio.h>
#include <string.h>

int i, j, m, n, c[20][20];
char x[20], y[20], b[20][20];

void print(int i, int j)
{
if (i == 0 || j == 0)
return;
if (b[i][j] == 'd')
{
print(i - 1, j - 1);
printf("%c", x[i - 1]);
}
else if (b[i][j] == 'u')
print(i - 1, j);
else
print(i, j - 1);
}

void lcs()
{
m = strlen(x);
n = strlen(y);
for (i = 0; i <= m; i++)
c[i][0] = 0;
for (i = 0; i <= n; i++)
c[0][i] = 0;

for (i = 1; i <= m; i++)
for (j = 1; j <= n; j++)
{
if (x[i - 1] == y[j - 1])
{
c[i][j] = c[i - 1][j - 1] + 1;
b[i][j] = 'd';
}
else if (c[i - 1][j] >= c[i][j - 1])
{
c[i][j] = c[i - 1][j];
b[i][j] = 'u';
}
else
{
c[i][j] = c[i][j - 1];
b[i][j] = 'l';
}
}
}
int main()
{
printf("Enter 1st sequence:");
scanf("%s", x);
printf("Enter 2nd sequence:");
scanf("%s", y);
printf("nThe Longest Common Subsequence is ");
lcs();
print(m, n);
return 0;
}

Output:


3. IMPLEMENTATION:
PROGRAM : To implement the 0-1KnapSack. in c program
Source code:
#include <stdio.h>
int max(int a, int b) { return (a > b) ? a : b; }
int knapSack(int W, int wt[], int val[], int n)
{
if (n == 0 || W == 0)
return 0;
if (wt[n - 1] > W)
return knapSack(W, wt, val, n - 1);
else
return max(
val[n - 1]+ knapSack(W - wt[n - 1], wt, val, n - 1),knapSack(W, wt, val, n - 1));
}
int main()
{ int i;
int val[4], wt[4],W;
for( i=0; i<4;i++){
printf("Enter the value and weight of item %d t",i+1);
scanf("%d%d",&val[i],&wt[i]);
}
printf("Enter the Size of bag t");
scanf("%d",&W);
int n = sizeof(val) / sizeof(val[0]);
printf("%d", knapSack(W, wt, val, n));
return 0;
}
Output:




3. IMPLEMENTATION:
PROGRAM : Matrix Chain Multiplication. in c program

Source code:
#include <limits.h>
#include <stdio.h>
#include <limits.h>
#include <stdio.h>
int MatrixChainOrder(int p[], int i, int j)
{
if (i == j)
return 0;
int k;
int min = INT_MAX;
int count;
for (k = i; k < j; k++)
{
count = MatrixChainOrder(p, i, k)+ MatrixChainOrder(p, k + 1, j)+ p[i - 1] * p[k] * p[j];
if (count < min)
min = count;
}
return min;
}

int main()
{
int arr[] = { 2,5,3,5,2,3,5 };
int N = sizeof(arr) / sizeof(arr[0]);
printf("Minimum number of multiplications is %d ",
MatrixChainOrder(arr, 1, N - 1));
getchar();
return 0;

}
Output:


3. IMPLEMENTATION:
PROGRAM : Floyd Warshall Algorithm. in c program
Source code:
#include <stdio.h>
#define nV 3 // defining the number of vertices
#define INF 999
void printMatrix(int matrix[][nV]);
void floydWarshall(int graph[][nV]) {
int matrix[nV][nV], i, j, k;
for (i = 0; i < nV; i++)
for (j = 0; j < nV; j++)
matrix[i][j] = graph[i][j];
for (k = 0; k < nV; k++) {
for (i = 0; i < nV; i++) {
for (j = 0; j < nV; j++) {
if (matrix[i][k] + matrix[k][j] < matrix[i][j])
matrix[i][j] = matrix[i][k] + matrix[k][j];
}}}
printMatrix(matrix);
}
void printMatrix(int matrix[][nV]) {
printf("nThe following matrix shows the shortest distances between every pair of verticesn");
for (int i = 0; i < nV; i++) {
for (int j = 0; j < nV; j++) {
if (matrix[i][j] == INF)
printf("%4s", "INF");
else
printf("%4d", matrix[i][j]);
}
printf("n");
}
}

int main() {
int graph[nV][nV] = { {0, 4, 11},
{6, 0, 2},
{3, INF, 0}
};
floydWarshall(graph);
}
Output: