Insertion Sort

#include <stdio.h>
void main()
{
int n, i, j, key, a[100];
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter elements of array\n");
for (i = 1; i <= n; i++)
{
scanf("%d\t", &a[i]);
}
for (j = 2; j <= n; j++)
{
key = a[j];
i = j-1;

while (i > 0 && a[i] > key)

{
a[i+1] = a[i];
i = i-1;
}
a[i+1] = key;
}
printf("Sorted list in ascending order:\n");
for (i = 1; i <= n; i++)
{
printf("%d\t", a[i]);
}
}
Selection Sort

#include <stdio.h>
void selectionSort(int a[], int n)
{
int i, j, min, temp;
for (i = 0 ; i < n-1 ;i++)
{
min = i;
for (j = i+1 ; j < n; j++)
{
if (a[j] < a[min])
{
min = j;
}
}
temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}

void main()
{
int a[10], i, n;
printf("Enter number of elements in array: ");
scanf("%d", &n);
printf("Enter elements of array: \n");
for (i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
selectionSort(a, n);
printf("Sorted array is ");
for (i = 0; i < n;i++)
{
printf("%d ", a[i]);
}
}
Quick Sort

#include <stdio.h>

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

{
int pivot = a[high]; //last element
int i = low - 1;

for (int j = low; j < high; j++)

{
if (a[j] < pivot)
{
i++;
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
int temp = a[i + 1]; // Place pivot in the correct position
a[i + 1] = a[high];
a[high] = temp;

return i + 1;
}

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, i, a[100];
printf("Enter number of elements: ");
scanf("%d", &n);

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

for (i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}

quickSort(a, 0, n - 1);
 printf("Sorted array:\n");
for (i = 0; i < n; i++)
{
printf("%d\t", a[i]);
}
return 0;
}
Merge Sort

#include <stdio.h>

void combine(int a[], int low, int mid, int high)

{
int l1,l2,i,j,k;
l1 = mid - low + 1;
l2 = high - mid;

int left[l1], right[l2];

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

{
left[i] = a[low + i];
}

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

{
right[j] = a[mid + 1 + j];
}

i = 0, j = 0, k = low;
while (i < l1 && j < l2)
{
if(left[i] <= right[j])
{
a[k] = left[i];
i++;
}
else
{
a[k] = right[j];
j++;
}
k++;
}

while(i < l1)

{
a[k++] = left[i++];
}

while(j < l2)

{
a[k++] = right[j++];
}
}
void mergesort(int a[], int low, int high)
{
if(low < high)
{
int mid = (low + high) / 2;
mergesort(a, low, mid);
mergesort(a, mid+1, high);
combine(a, low, mid, high);
}
}

int main()
{
int n, i, a[100];
printf("Enter the number of elements : ");
scanf("%d", &n);
printf("Enter the elements of array : \n");
for(i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}

mergesort(a, 0, n-1);

printf("\nSorted array : ");

for(i = 0; i < n; i++)
{
printf("%d\t", a[i]);
}
return 0;
}
Binary Search

#include <stdio.h>

int binarySearch(int a[], int low, int high, int x)

{
while (low <= high)
{
int mid = low + (high - low) / 2; // Prevent integer overflow

if (a[mid] == x)
{
return mid;
}
else if (a[mid] < x)
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
return -1;
}

void main()
{
int n, i, a[100], x;
printf("Enter the number of elements : ");
scanf("%d", &n);
printf("\nEnter the elements of sorted array : \n");
for(i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}

printf("\nEnter the element to be search : ");

scanf("%d", &x);

int result = binarySearch(a, 0, n-1, x);

if(result == -1)
{
printf("\nElement is not present in array");
}
else
{
printf("Element is present at index %d (0-based index)",result);
}
}
void main()
{
int n, i, j, temp, a[100], x;
printf("Enter the number of elements : ");
scanf("%d", &n);
printf("\nEnter the elements of array : \n");
for(i=0; i < n; i++)
{
scanf("%d", &a[i]);
}

/* Bubble sorting begins */

for (i = 0; i < n; 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;
}
}
}
printf("Sorted array is...\n");
for (i = 0; i < n; i++)
{
printf("%d\t", a[i]);
}
printf("\nEnter the element to be search : ");
scanf("%d", &x);

int result = binarySearch(a, 0, n-1, x);

if(result == -1)
{
printf("\nElement is not present in array");
}
else
{
printf("Element is present at index %d",result);
}
}
Fractional Knapsack

#include<stdio.h>

int main()
{
float weight[50], profit[50], ratio[50], totalvalue = 0, capacity, temp;
int i, j, n;

printf("Enter number of items :");

scanf("%d", &n);

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

{
printf("\nEnter weight and profit for item[%d] : ", i);
scanf("%f %f", &weight[i], &profit[i]);
}

printf("\nEnter the capacity of Knapsack : ");

scanf("%f", &capacity);

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

{
ratio[i] = profit[i] / weight[i];
}

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

{
for(j = i + 1; j < n; j++)
{
if(ratio[i] < ratio[j])
{
temp = ratio[j];
ratio[j] = ratio[i];
ratio[i] = temp;

temp = weight[j];
weight[j] = weight[i];
weight[i] =temp;

temp = profit[j];
profit[j] = profit [i];
profit[i] = temp;
}
}
}
 for(i = 0; i < n; i++)
{
if(weight[i] > capacity)
{
break;
}
else
{
totalvalue = totalvalue + profit[i];
capacity = capacity - weight[i];
}
}

if(i < n)
{
totalvalue = totalvalue + (ratio[i] * capacity);
printf("Total profit : %f ", totalvalue);
}
return 0;
}

Enter number of items :5

Enter weight and profit for item[0] : 10 20

Enter weight and profit for item[1] : 20 30

Enter weight and profit for item[2] : 30 40

Enter weight and profit for item[3] : 40 50

Enter weight and profit for item[4] : 50 60

Enter the capacity of Knapsack : 70

Total profit : 102.500000
Prim

# include<stdio.h>
# include <limits.h>
#define MAX 50

int n, i, j, k, G[MAX][MAX], select[MAX], min_dist, cost = 0, u, v;

void Prim()
{
// Initialize the select array to 0
for (int i = 0; i < n; i++)
{
select[i] = 0;
}
select[0] = 1; // Start with the first node

printf("\nMinimum Spanning Tree Edges is:\n");

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

{
min_dist = INT_MAX; // Set min_dist to infinity
for (i = 0 ; i < n ; i++)
for (j = 0 ; j < n ; j++)
if (G[i][j] && ((select[i] && !select[j]) || (!select[i] &&
select[j])))
if (G[i][j] < min_dist)
{
min_dist = G[i][j];
u = i;
v = j;
}
printf("\n Edge (%d %d) and weight = %d",u,v,min_dist);
select[u] = select[v] = 1; // Mark the node as selected
cost = cost + min_dist;
}
printf("\n\n\t Total Path Length Is = %d",cost);
}

int main()
{
printf("Enter Number of Nodes in The Graph: ");
scanf("%d",&n);

printf("Enter the adjacency matrix (0 for no edge):\n");

for(i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
{
printf("G[%d][%d]: ",i,j);
scanf("%d",&G[i][j]);
}
}
Prim();
return 0;
}
0 → 1 → 2 → 0 (circular/triangular) Prim
1 1 2

Enter Number of Nodes in The Graph: 3

Enter the adjacency matrix (0 for no edge):
G[0][0]: 0
G[0][1]: 1
G[0][2]: 2
G[1][0]: 1
G[1][1]: 0
G[1][2]: 1
G[2][0]: 2
G[2][1]: 1
G[2][2]: 0

Minimum Spanning Tree Edges is:

Edge (0 1) and weight = 1

Edge (1 2) and weight = 1

Total Path Length Is = 2

1→ 2 → 3 → 1 (circular/triangular)
1 1 2

Enter the no. of vertices:3 Kruskal

Enter the cost adjacency matrix (use 0 for no edge):
cost[1][1]: 0
cost[1][2]: 1
cost[1][3]: 2
cost[2][1]: 1
cost[2][2]: 0
cost[2][3]: 1
cost[3][1]: 2
cost[3][2]: 1
cost[3][3]: 0
The edges of Minimum Cost Spanning Tree are

Edge (1, 2) with weight 1

Edge (2, 3) with weight 1

Minimum cost = 2
Kruskal

#include<stdio.h>
#include <limits.h> // For INT_MAX
#define MAX 50

int i, j, a, b, u, v, n;
int min, mincost = 0, cost[MAX][MAX], parent[MAX], edges = 0;

//find root of a vertex

int find(int i)
{
while(parent[i])
i = parent[i];
return i;
}

//perform union of two sets

int uni(int i, int j)
{
if(i != j)
{
parent[j] = i;
return 1;
}
return 0;
}

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

printf("Enter the cost adjacency matrix (use 0 for no edge):\n");

for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
{
printf("cost[%d][%d]: ", i, j);
scanf("%d", &cost[i][j]);
if (cost[i][j] == 0)
{
cost[i][j] = INT_MAX;
}
}
}

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

 while(edges < n-1)
{
min = INT_MAX;
for(i = 1; i <= n; i++)
{
for(j = 1; j <= n; j++)
{
if(cost[i][j] < min)
{
min = cost[i][j];
a = u = i;
b = v = j;
}
}
}
u = find(u);
v = find(v);

// If the edge does not form a cycle, include it in the MST

if(uni(u,v))
{
printf("Edge (%d, %d) with weight %d\n", a, b, min);
mincost += min;
edges++;
}
cost[a][b] = cost[b][a] = INT_MAX; // Mark the edge as included in
MST
}
printf("\n\tMinimum cost = %d\n", mincost);
return 0;
}
Floydd Warshall

#include<stdio.h>
#define INF 99999 // Define a large value to represent infinity
int i, j, k, n, dist[10][10];

void floydWarshell ()
{
for (k = 0; k < n; k++)
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
int main()
{
printf("Enter the number of vertices: ");
scanf("%d", &n);

printf("\nEnter the adjacency matrix (use %d for no edge):\n", INF);

for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
printf("dist[%d][%d]: ", i, j);
scanf("%d", &dist[i][j]);
}
}

floydWarshell();

printf("\nShortest distances between every pair of vertices:\n");

for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
if (dist[i][j] == INF)
{
printf("INF\t");
} else
{
printf("%d\t", dist[i][j]);
}
}
printf("\n");
}
return 0;
}
Enter the number of vertices: 3

Enter the adjacency matrix (use 99999 for no edge):

dist[0][0]: 0
dist[0][1]: 4
dist[0][2]: 11
dist[1][0]: 6
dist[1][1]: 0
dist[1][2]: 2
dist[2][0]: 3
dist[2][1]: 99999
dist[2][2]: 0

Shortest distances between every pair of vertices:

0 4 6
5 0 2
3 7 0
N-Queen

#include<stdio.h>
#include<math.h>

int board[20], count = 0;

//check if a queen can be placed at the given position

int place(int row, int column)
{
int i;
for(i = 1; i <= row-1; i++)
{
//checking for column and diagonal conflicts
if (board[i] == column || abs(board[i] - column) == abs(i - row))
{
return 0; // Conflict found
}
}
return 1; //no conflicts, Queen can be placed
}

//print the board configuration for a solution

void print_board(int n)
{
int i,j;
//number of solution
printf("\n\nSolution %d : \n\n", ++count);
for(i = 1; i <= n; i++)
{
printf("\t%d", i); // for column
}
for(i = 1; i <= n; i++)
{
printf("\n\n%d\t",i); // for row
for(j=1;j<=n;j++)
{
if(board[i]==j)
{
printf("Q\t"); //Queen at i,j position
}
else
{
printf("-\t"); // empty slot
}
}
}
}
//Function to solve the N-Queens problem using backtracking
void Queen(int row,int n)
{
int column;
for(column = 1; column <= n; column++)
{
// Check if the queen can be placed
if(place(row,column))
{
board[row] = column; // Place the queen
if(row==n)
{
print_board(n); //If all queens are placed, print the
solution
}
else
{
Queen(row+1,n); // Try placing the next queen
}
}
}
}

int main()
{
int n;
printf("Enter Number of Queen's: ");
scanf("%d",&n);
Queen(1,n); // Start solving from the first row

if (count == 0)
{
printf("\nNo solutions exist for %d queens.\n", n);
}
else
{
printf("\n\nTotal number of solutions: %d\n", count);
}

return 0;
}
Enter Number of Queen's: 4

Solution 1 :

1 2 3 4

1 - Q - -

2 - - - Q

3 Q - - -

4 - - Q -

Solution 2 :

1 2 3 4

1 - - Q -

2 Q - - -

3 - - - Q

4 - Q - -

Total number of solutions: 2

Naïve String

#include<stdio.h>
#include<string.h>

void naive_string_matcher(char text[],char pat[])

{
int n, m, i, j;
int count = 0;
n = strlen(text);
m = strlen(pat);

printf("Pattern found at positions: ");

int found = 0;

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

{
for (j = 0; j < m; j++)
{
if (text[i + j] != pat[j])
break;
}

if (j == m)
{
printf("%d ", i);
found = 1;
count++;
}
}

if (!found)
{
printf("No match found.");
}
else
{
printf("\nNo. of matches found: %d", count);
}
}
int main()
{
char text[100],pat[100];
printf("Enter the text : ");
fgets(text, sizeof(text), stdin);
// Remove newline character
text[strcspn(text, "\n")] = 0;
printf("Enter the pattern : ");
fgets(pat, sizeof(pat), stdin);
pat[strcspn(pat, "\n")] = 0;
naive_string_matcher(text,pat);
return 0;
}