Sarthak Srivastava

2100271540049
Experiment -1
Write a program to implement insertion sort.

#include <stdio.h>int

main()

int i, j, k, n;

printf("Enter number of elements in array:");

scanf("%d",&n);

int a[n];

printf("Enter elements of array:\n");

for(i=0; i<n; i++)

scanf("%d",&a[i]);

for(i=1;i<n;i++)

k=a[i];j=i-

1;

while(j>=0 && a[j]>k)

a[j+1]=a[j]; j=j-

1;

a[j+1]=k;

printf("Array after sorting is:\n");

1
 for(i=0; i<n; i++)

printf("%d\t",a[i]);

return 0;

Output:

Enter number of elements in array:6

Enter elements of array:

12 45 10 8 46 33

Array after sorting is:

8 10 12 33 45 46

2
 Sarthak Srivastava
2100271540049
Experiment - 2
Write a program to implement merge sort.

#include <stdio.h>
#include <stdlib.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)

3
{
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 A[], int size)

{
int i;
for (i = 0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
}

int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
int arr_size = sizeof(arr) / sizeof(arr[0]);

printf("Given array is \n");

printArray(arr, arr_size);

mergeSort(arr, 0, arr_size - 1);

printf("\nSorted array is \n");

printArray(arr, arr_size); return 0;
}

Output:

Given array is

12 11 13 5 6 7

Sorted array is

5 6 7 11 12 13

4
 Sarthak Srivastava
2100271540049
Experiment - 3
Write a program in C to implement Quick sort.

#include<stdio.h>
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}

int partition( int a[], int low, int high)

{
int pivot = low;
int i = low + 1;
int j = high;
while(i < j)
{
while(i < (high + 1) && a[i] <=
a[pivot])i++;
while(a[j] > a[pivot])
j--;
if(i < j)
swap(&a[i], &a[j]);
}
swap(&a[pivot],
&a[j]);return j;
}

void quicksort(int a[], int low, int high)

{
if(low<high)
{
int pi = partition(a, low, high);
quicksort(a, low, pi - 1);
quicksort(a, pi + 1, high);
}
}

int main()
{
int n;
printf("Enter the total no. of elements in array: ");scanf("%d",
&n);

int a[n];
printf("Enter array elements: ");
for(int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
printf("Array before sorting: [ ");

5
 for(int i = 0; i < n; i++)
{
printf("%d", a[i]);if(i
!= n-1)
printf(", ");
}
printf("]");
quicksort(a, 0, n - 1);
printf("\nArray after sorting: [ ");
for(int i = 0; i < n; i++)
{
printf("%d", a[i]);if(i
!= n-1)
printf(", ");
}
printf("]");
return 0;
}

Output:
Enter the total no. of elements in array: 6
Enter array elements: 12 45 34 11 6 38
Array before sorting: [ 12, 45, 34, 11, 6, 38]
Array after sorting: [ 6, 11, 12, 34, 38, 45]

6
 Experiment – 4
Write a program to implement Heap Sort.

#include <stdio.h>
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}

void heapify(int a[], int n, int i)

{
int largest = i;
int left = 2 * i +
1;int right = 2 * i
+ 2;

if(left < n && a[left] >

a[largest]) largest =
left;

if(right < n && a[right] >

a[largest]) largest = right;

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

void heapsort(int a[], int n)

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

for(int i = n - 1; i >= 0; i--)

{
swap(&a[0],
&a[i]);heapify(a, i,
0);
}
}

int main()
{
int n;
printf("Enter the total no. of elements in array: ");
scanf("%d", &n);

7
 int a[n];
printf("Enter array elements: ");
for(int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
printf("Array before sorting: [ ");
for(int i = 0; i < n; i++)
{
printf("%d",
a[i]);if(i != n-1)
printf(", ");
}
printf("]");
heapsort(a, n);
printf("\nArray after sorting: [ ");
for(int i = 0; i < n; i++)
{
printf("%d",
a[i]);if(i != n-1)
printf(", ");
}
printf("]");
}

Output:
Enter the total no. of elements in array:
6Enter array elements: 12 46 34 10 6
25
Array before sorting: [ 12, 46, 34, 10, 6, 25]
Array after sorting: [ 6, 10, 12, 25, 34, 46]

8
 Sarthak Srivastava
2100271540049

Experiment - 5
Write a program to implement counting sort.

#include <stdio.h>int

main()

int i, j, n;

printf("Enter length of array: ");

scanf("%d", &n);

int input[n];

printf("Enter array elements: ");

for(i = 0; i < n; i++)

scanf("%d", &input[i]);

int max = input[0]; for(i

= 1; i < n; i++)

if(input[i] > max)

max=input[i];

int count[max + 1], c; for(i

= 0; i <= max; i++)

c = 0;

for(j = 0; j < n; j++)

9
 {

if(input[j] == i)

c++;

count[i] = c;

for(i = 1; i <= max; i++)

count[i] = count[i-1] + count[i];

int output[n];

for(i = 0; i < n; i++)

output[count[input[i]] - 1] = input[i];

count[input[i]] = count[input[i]] - 1;

printf("Array after sorting: ");

for(i = 0; i < n; i++)

printf("%d ", output[i]);

Output:

Enter length of array: 6

Enter array elements: 12 34 67 45 10 6 27

Array after sorting: 6 10 12 34 45 67

10
 Sarthak Srivastava
2100271540049
Experiment - 6
Write a program to implement shell sort.

#include<stdio.h>

void ShellSort(int a[], int n)

int i, j, increment, tmp;

for(increment = n/2; increment > 0; increment /= 2)

for(i = increment; i < n; i++)

tmp = a[i];

for(j = i; j >= increment; j -= increment)

if(tmp < a[j-increment])a[j] =

a[j-increment];

else

break;

a[j] = tmp;

int main()

11
 int i, n, a[10];

printf("Enter the number of elements : ");

scanf("%d",&n);

printf("Enter the elements : ");for(i

= 0; i < n; i++)

scanf("%d",&a[i]);

ShellSort(a,n);

printf("The sorted elements are : ");for(i

= 0; i < n; i++)

printf("%d ",a[i]);

printf("\n");

return 0;

Output:

Enter the number of elements : 6 Enter the

elements : 12 34 78 6 33 27

The sorted elements are : 6 12 27 33 34 78

12
 Sarthak Srivastava
Experiment-7 2100271540049

Write a program in C to perform matrix chain multiplication.

#include <limits.h>

#include <stdio.h>

int MatrixChainOrder(int p[], int i, int j)

if (i == j)

return 0;

int k, count, min = INT_MAX;

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[] = { 1, 2, 3, 4, 3 };

int N = sizeof(arr) / sizeof(arr[0]);

printf("Minimum number of multiplications is %d ", MatrixChainOrder(arr, 1, N - 1));

return 0;

Output:

Minimum number of multiplications is 30.

13
 Sarthak Srivastava
Experiment-8 2100271540049
Write a program in C to implement Kruskal’s minimum spanning tree algorithm.

#include<stdio.h>

#include<stdlib.h>

int i,j,k,a,b,u,v,n,ne=1;

int min,mincost=0,cost[9][9],parent[9];

int find(int);

int uni(int,int);

void main()

printf("\nEnter the no. of vertices:");

scanf("%d",&n);

printf("\nEnter the cost adjacency matrix:\n");

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

scanf("%d",&cost[i][j]);

if(cost[i][j]==0)

cost[i][j]=999;

printf("The edges of Minimum Cost Spanning Tree are\n");

while(ne < n)

for(i=1,min=999;i<=n;i++)

for(j=1;j <= n;j++)

if(cost[i][j] < min)

14
 {

min=cost[i][j];

a=u=i;

b=v=j;

u=find(u);

v=find(v);

if(uni(u,v))

printf("%d edge (%d,%d) =%d\n",ne++,a,b,min);

mincost +=min;

cost[a][b]=cost[b][a]=999;

printf("\nMinimum cost = %d\n",mincost);

int find(int i)

while(parent[i])

i=parent[i];

return i;

int uni(int i,int j)

if(i!=j)

parent[j]=i;

return 1;

15
 }

return 0;

Output:

Enter the no. of vertices:6

Enter the cost adjacency matrix:

123050

269404

207412

375000

315703

007080

The edges of Minimum Cost Spanning Tree are

1 edge (3,5) =1

2 edge (5,2) =1

3 edge (1,2) =2

4 edge (3,6) =2

5 edge (4,1) =3

Minimum cost = 9

16