Sorting, Heaps, and Graph Algorithms
Merge sort:
#include <stdio.H>
#include <stdlib.H>
#include <string.H>
#define MAX 10000
Int noofcomparision = 0;
Void merge(int arr[], int l, int mid, int h) {
Int n1 = mid + 1 – l;
Int n2 = h – mid;
Int a[n1], b[n2];
For (int i = 0; i < n1; i++) {
A[i] = arr[i + l];
}
For (int i = 0; i < n2; i++) {
B[i] = arr[i + mid + 1];
}
Int i = 0, j = 0, k = l;
While (i < n1 && j < n2) {
Noofcomparision++;
if (a[i] <= b[j]) {
arr[k] = a[i];
i++;
} else {
arr[k] = b[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = a[i];
k++;
i++;
}
while (j < n2) {
arr[k] = b[j];
k++;
j++;
}
}
void mergesort(int arr[], int low, int high) {
if (low < high) {
int mid = (low + high) / 2;
mergesort(arr, low, mid);
mergesort(arr, mid + 1, high);
merge(arr, low, mid, high);
}
}
int main() {
int arr[] = {38, 27, 43, 3, 9, 82, 10};
int n = sizeof(arr) / sizeof(arr[0]);
printf(“Unsorted array: “);
for (int i = 0; i < n; i++)
printf(“%d “, arr[i]);
Printf(“\n”);
mergeSort(arr, 0, n – 1);
printf(“Sorted array with Merge Sort: “);
for (int i = 0; i < n; i++)
printf(“%d “, arr[i]);
Printf(“\n”);
return 0;
}
Quick sort: #include
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low – 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi – 1);
quickSort(arr, pi + 1, high);
}
}
int main() {
int arr2[] = {38, 27, 43, 3, 9, 82, 10};
quickSort(arr2, 0, n – 1);
printf(“Sorted array with Quick Sort: “);
for (int i = 0; i < n; i++)
printf(“%d “, arr2[i]);
Printf(“\n”);
return 0;
HEAP: #include
#include <stdlib.H>
#include <string.H>
struct person {
int id;
char name[50];
int age;
int height;
int weight;
};
struct person *people = NULL;
int personCount = 0;
void swap(struct person *a, struct person *b) {
struct person temp = *a;
*a = *b;
*b = temp;
}
void maxHeapify(struct person *arr, int n, int i) {
int largest = i;
Int left = 2 * i + 1;
Int right = 2 * i + 2;
if (left < n && arr[left].Weight > arr[largest].Weight)
Largest = left;
If (right < n && arr[right].Weight > arr[largest].Weight)
Largest = right;
If (largest != i) {
Swap(&arr[i], &arr[largest]);
MaxHeapify(arr, n, largest);
}
}
Void buildMaxHeap(struct person *arr, int n) {
For (int i = n / 2 – 1; i >= 0; i–)
MaxHeapify(arr, n, i);
}
Void minHeapify(struct person *arr, int n, int i) {
Int smallest = i;
Int left = 2 * i + 1;
Int right = 2 * i + 2;
If (left < n && arr[left].Age < arr[smallest].Age)
Smallest = left;
If (right < n && arr[right].Age < arr[smallest].Age)
Smallest = right;
If (smallest != i) {
Swap(&arr[i], &arr[smallest]);
MinHeapify(arr, n, smallest);
}
}
Void buildMinHeap(struct person *arr, int n) {
For (int i = n / 2 – 1; i >= 0; i–)
MinHeapify(arr, n, i);
}
Void displayYoungestWeight() {
BuildMinHeap(people, personCount);
Printf(“Weight of youngest student: %.2f kg\n”, people[0].Weight * 0.453592);
}
Void insertPerson(struct person newPerson) {
PersonCount++;
People = realloc(people, personCount * sizeof(struct person));
People[personCount – 1] = newPerson;
BuildMinHeap(people, personCount);
}
Void deleteOldest() {
BuildMaxHeap(people, personCount);
Printf(“Deleting oldest person with age: %d\n”, people[0].Age);
People[0] = people[–personCount];
BuildMaxHeap(people, personCount);
}
Void readDataFromFile(const char *filename) {
FILE *file = fopen(filename, “r”);
If (!File) {
Printf(“Error opening file.\n”);
Return;
}
Fscanf(file, “%d”, &personCount);
People = malloc(personCount * sizeof(struct person));
For (int i = 0; i < personCount; i++) {
fscanf(file, “%d %s %d %d %d”, &people[i].Id, people[i].Name, &people[i].Age, &people[i].Height, &people[i].Weight);
}
Fclose(file);
Printf(“Data loaded from file.\n”);
}
Void displayData() {
Printf(“Id\tName\t\tAge\tHeight\tWeight\n”);
For (int i = 0; i < personCount; i++) {
Printf(“%d\t%s\t\t%d\t%d\t%d\n”, people[i].Id, people[i].Name, people[i].Age, people[i].Height, people[i].Weight);
}
}
Int main() {
Int option;
Struct person newPerson;
While (1) {
Printf(“MAIN MENU (HEAP)\n”);
Printf(“1. Read Data\n”);
Printf(“2. Create a Min-heap based on the age\n”);
Printf(“3. Create a Max-heap based on the weight\n”);
Printf(“4. Display weight of the youngest person\n”);
Printf(“5. Insert a new person into the Min-heap\n”);
Printf(“6. Delete the oldest person\n”);
Printf(“7. Exit\n”);
Printf(“Enter option: “);
Scanf(“%d”, &option);
Switch (option) {
Case 1:
ReadDataFromFile(“students.Txt”);
Break;
Case 2:
BuildMinHeap(people, personCount);
Printf(“Min-heap created based on age.\n”);
Break;
Case 3:
BuildMaxHeap(people, personCount);
Printf(“Max-heap created based on weight.\n”);
break;
Case 4:
DisplayYoungestWeight();
break;
Case 5:
Printf(“Enter Id, Name, Age, Height, Weight: “);
scanf(“%d %s %d %d %d”, &newPerson.Id, newPerson.Name, &newPerson.Age, &newPerson.Height, &newPerson.Weight);
InsertPerson(newPerson);
Printf(“New person inserted into Min-heap.\n”);
break;
Case 6:
DeleteOldest();
break;
Case 7:
Free(people);
Printf(“Exiting.\n”);
Return 0;
Default:
Printf(“Invalid option. Try again.\n”);
}
}
}
LCS of given two String
#include <stdio.H>
#include <string.H>
#define MAX 100
void findLCS(char *str1, char *str2) {
int len1 = strlen(str1);
int len2 = strlen(str2);
int LCS_table[MAX][MAX];
for (int i = 0; i <= len1; i++) {
for (int j = 0; j <= len2; j++) {
if (i == 0 || j == 0)
LCS_table[i][j] = 0;
else if (str1[i – 1] == str2[j – 1])
LCS_table[i][j] = LCS_table[i – 1][j – 1] + 1;
else
LCS_table[i][j] = (LCS_table[i – 1][j] > LCS_table[i][j – 1]) ? LCS_table[i – 1][j] : LCS_table[i][j – 1];
}
}
int index = LCS_table[len1][len2];
char lcs[index + 1];
lcs[index] = ‘\0’; // Null-terminate the LCS string
// Trace the LCS string from the table
int i = len1, j = len2;
while (i > 0 && j > 0) {
if (str1[i – 1] == str2[j – 1]) {
lcs[index – 1] = str1[i – 1];
I–;
J–;
index–;
} else if (LCS_table[i – 1][j] > LCS_table[i][j – 1])
I–;
else
J–;
}
// Print the LCS and its length
printf(“LCS: %s\n”, lcs);
printf(“LCS Length: %d\n”, LCS_table[len1][len2]);
}
int main() {
char str1[MAX], str2[MAX];
// Input the strings
printf(“Enter the first string into an array: “);
scanf(“%s”, str1);
printf(“Enter the second string into an array: “);
scanf(“%s”, str2);
// Find and print the LCS
findLCS(str1, str2);
return 0;
}
Kruskal algo:
#include <stdio.H>
#include <stdlib.H>
#define MAX_EDGES 100
Struct Edge {
Int u, v, weight;
};
Struct Graph {
Int V, E;
Struct Edge edges[MAX_EDGES];
};
Struct Subset {
Int parent;
Int rank;
};
Int compareEdges(const void *a, const void *b) {
Struct Edge *edge1 = (struct Edge *)a;
Struct Edge *edge2 = (struct Edge *)b;
Return edge1->weight – edge2->weight;
}
Int findSet(struct Subset subsets[], int i) {
If (subsets[i].Parent != i)
Subsets[i].Parent = findSet(subsets, subsets[i].Parent);
Return subsets[i].Parent;
}
Void unionSets(struct Subset subsets[], int x, int y) {
Int rootX = findSet(subsets, x);
Int rootY = findSet(subsets, y);
If (subsets[rootX].Rank < subsets[rootY].Rank)
Subsets[rootX].Parent = rootY;
Else if (subsets[rootX].Rank > subsets[rootY].Rank)
subsets[rootY].Parent = rootX;
Else {
subsets[rootY].Parent = rootX;
Subsets[rootX].Rank++;
}
}
Void kruskalMST(struct Graph *graph) {
Int V = graph->V;
Struct Edge result[MAX_EDGES];
Int e = 0;
Int i = 0;
Qsort(graph->edges, graph->E, sizeof(graph->edges[0]), compareEdges);
Struct Subset *subsets = (struct Subset *)malloc(V * sizeof(struct Subset));
For (int v = 0; v < V; ++v) {
Subsets[v].Parent = v;
Subsets[v].Rank = 0;
}
Int totalWeight = 0;
While (e < V – 1 && i < graph->E) {
Struct Edge nextEdge = graph->edges[i++];
Int x = findSet(subsets, nextEdge.U – 1);
Int y = findSet(subsets, nextEdge.V – 1);
If (x != y) {
Result[e++] = nextEdge;
TotalWeight += nextEdge.Weight;
UnionSets(subsets, x, y);
}
}
Printf(“Edge Cost\n”);
For (i = 0; i < e; ++i)
Printf(“%d–%d %d\n”, result[i].U, result[i].V, result[i].Weight);
Printf(“Total Weight of the Spanning Tree: %d\n”, totalWeight);
Free(subsets);
}
Int main() {
Printf(“22054058\n”);
Int n, m;
Printf(“Enter the number of nodes and edges: “);
Scanf(“%d %d”, &n, &m);
Struct Graph graph;
Graph.V = n;
Graph.E = m;
Printf(“Enter each edge (u v weight):\n”);
For (int i = 0; i < m; i++) {
Scanf(“%d %d %d”, &graph.Edges[i].U, &graph.Edges[i].V, &graph.Edges[i].Weight);
}
KruskalMST(&graph);
Return 0;
}
DIjkistra:
#include <stdio.H>
#include <stdlib.H>
#include <limits.H>
#define MAX_VERTICES 100
#define INFINITY INT_MAX
Int graph[MAX_VERTICES][MAX_VERTICES];
Int dist[MAX_VERTICES];
Int previous[MAX_VERTICES];
Int visited[MAX_VERTICES];
Int n;
Void initializeSingleSource(int source) {
For (int i = 0; i < n; i++) {
Dist[i] = INFINITY;
Previous[i] = -1;
Visited[i] = 0;
}
Dist[source] = 0;
}
Int extractMin() {
Int minDist = INFINITY;
Int minVertex = -1;
For (int v = 0; v < n; v++) {
If (!Visited[v] && dist[v] < minDist) {
MinDist = dist[v];
MinVertex = v;
}
}
Return minVertex;
}
Void relax(int u, int v, int weight) {
If (dist[u] != INFINITY && dist[u] + weight < dist[v]) {
Dist[v] = dist[u] + weight;
Previous[v] = u;
}
}
Void dijkstra(int source) {
InitializeSingleSource(source);
For (int i = 0; i < n – 1; i++) {
Int u = extractMin();
If (u == -1) break;
Visited[u] = 1;
For (int v = 0; v < n; v++) {
If (graph[u][v] && !Visited[v]) {
Relax(u, v, graph[u][v]);
}
}
}
}
Void printPath(int vertex) {
If (previous[vertex] == -1) {
Printf(“%d”, vertex + 1);
Return;
}
PrintPath(previous[vertex]);
Printf(“->%d”, vertex + 1);
}
Int main() {
Printf(“22054058\n”);
FILE *file = fopen(“inDiAdjMat1.Dat”, “r”);
If (!File) {
Printf(“Error: Cannot open the input file.\n”);
Return 1;
}
Printf(“Enter the Number of Vertices: “);
Scanf(“%d”, &n);
For (int i = 0; i < n; i++) {
For (int j = 0; j < n; j++) {
Fscanf(file, “%d”, &graph[i][j]);
If (graph[i][j] == 0 && i != j) {
Graph[i][j] = INFINITY;
}
}
}
Fclose(file);
Int source;
Printf(“Enter the Source Vertex: “);
Scanf(“%d”, &source);
Source–;
Dijkstra(source);
Printf(“Source Destination Cost Path\n”);
For (int i = 0; i < n; i++) {
Printf(“%d %d “, source + 1, i + 1);
If (dist[i] == INFINITY) {
Printf(“INF -\n”);
} else {
Printf(“%d “, dist[i]);
PrintPath(i);
Printf(“\n”);
}
}
Return 0;}
matrix chain (optimal parentheiss): #include
#include <limits.H>
Void printOptimalParenthesization(int s[][100], int i, int j) {
If (i == j)
Printf(“A%d”, i + 1);
Else {
Printf(“(“);
PrintOptimalParenthesization(s, i, s[i][j]);
PrintOptimalParenthesization(s, s[i][j] + 1, j);
Printf(“)”);
}
}
Int main() {
Printf(“22054058\n”);
Int n, i, j, k, L, q;
Printf(“Enter number of matrices: “);
Scanf(“%d”, &n);
Int p[100];
Int m[100][100], s[100][100];
For (i = 0; i < n; i++) {
Int row, col;
Printf(“Enter row and col size of A%d: “, i + 1);
Scanf(“%d %d”, &row, &col);
If (i == 0)
P[i] = row;
P[i + 1] = col;
}
For (i = 0; i < n; i++)
M[i][i] = 0;
For (L = 2; L
for (i = 0; i < n – L + 1; i++) {
j = i + L – 1;
m[i][j] = INT_MAX;
for (k = i; k < j; k++) {
q = m[i][k] + m[k + 1][j] + p[i] * p[k + 1] * p[j + 1];
if (q < m[i][j]) {
m[i][j] = q;
s[i][j] = k;
}
}
}
}
printf(“\nM Table:\n”);
For (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
if (i <= j)
printf(“%d\t”, m[i][j]);
else
printf(“\t”);
}
Printf(“\n”);
}
printf(“\nS Table:\n”);
For (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
if (i <= j)
printf(“%d\t”, s[i][j]);
else
printf(“\t”);
}
Printf(“\n”);
}
printf(“\nOptimal parenthesization: “);
printOptimalParenthesization(s, 0, n – 1);
Printf(“\n”);
printf(“The optimal ordering of the given matrices requires %d scalar multiplications.\n”, m[0][n – 1]);
return 0;
}
ALL pair shortest path (Floyd-Warshall’s): #include
#include <stdlib.H>
#define INF 99999
void floydWarshall(int n, int dist[n][n], int next[n][n]) {
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
For (int j = 0; j < n; j++) {
if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
next[i][j] = next[i][k];
}
}
}
}
}
void printPath(int next[][5], int u, int v) {
if (next[u][v] == -1) {
printf(“No path”);
return;
}
printf(“%d”, u + 1);
while (u != v) {
u = next[u][v];
printf(” -> %d”, u + 1);
}
Printf(“\n”);
}
int main() {
printf(“22054058\n”);
FILE *file = fopen(“inDiAdjMat2.Dat”, “r”);
if (!File) {
printf(“Error: Could not open file\n”);
Return 1;
}
Int n;
printf(“Enter the number of vertices: “);
scanf(“%d”, &n);
int dist[n][n], next[n][n];
for (int i = 0; i < n; i++) {
For (int j = 0; j < n; j++) {
fscanf(file, “%d”, &dist[i][j]);
if (i != j && dist[i][j] == 0) {
dist[i][j] = INF;
}
next[i][j] = (dist[i][j] == INF) ? -1 : j;
}
}
fclose(file);
floydWarshall(n, dist, next);
printf(“Shortest path distance matrix:\n”);
for (int i = 0; i < n; i++) {
For (int j = 0; j < n; j++) {
if (dist[i][j] == INF) {
printf(“INF “);
} else {
printf(“%d “, dist[i][j]);
}
}
Printf(“\n”);
}
int src, dest;
printf(“Enter the source and destination vertices: “);
scanf(“%d %d”, &src, &dest);
src–;
dest–;
printf(“Shortest Path from vertex %d to vertex %d: “, src + 1, dest + 1);
printPath(next, src, dest);
printf(“Path weight: %d\n”, dist[src][dest] == INF ? -1 : dist[src][dest]);
return 0;
}