Program-1
Program for Binary Search, Insertion Sort and Bubble Sort.
#include <stdio.h>
#include <stdlib.h>
typedef struct bst {
int data;
struct bst *left, *right;
} node;
void insert(node *, node *);
void inorder(node *);
node *search(node *, int, node **);
void del(node *, int);
node *getnode();
int main() {
int choice, key;
char ans = 'N';
node *new, *root = NULL, *tmp, *parent;
printf("\n\tProgram for Binary Search Tree");
do {
printf("\n1. Create\n2. Search\n3. Delete\n4. Display\n5. Exit");
printf("\n\nEnter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
do {
new = getnode();
printf("\nEnter the element: ");
scanf("%d", &new->data);
if (root == NULL)
root = new;
else
insert(root, new);
printf("\nDo you want to enter more elements? (y/n): ");
scanf(" %c", &ans); // Use space before %c to capture input correctly
} while (ans == 'y' || ans == 'Y');
break;
case 2:
printf("\nEnter the element which you want to search: ");
scanf("%d", &key);
tmp = search(root, key, &parent);
if (tmp) {
printf("\nElement %d found. Parent is %d.\n", tmp->data, parent ? parent->data : -1);
} else {
printf("\nElement not found.");
break;
case 3:
printf("\nEnter the element you wish to delete: ");
scanf("%d", &key);
del(root, key);
break;
case 4:
if (root == NULL)
printf("Tree is not created");
else {
printf("\nThe tree is: ");
inorder(root);
printf("\n");
break;
} while (choice != 5);
return 0;
void insertion_sort(int a[], int n) {
int i, j, temp, k;
printf("\nUnsorted Data:");
for (k = 0; k < n; k++)
printf("%5d", a[k]);
for (i = 1; i < n; i++) {
temp = a[i];
for (j = i - 1; j >= 0 && a[j] > temp; j--) {
a[j + 1] = a[j];
a[j + 1] = temp;
// Print array after each pass
printf("\nAfter pass %d: ", i);
for (k = 0; k < n; k++)
printf("%5d", a[k]);
void bubble_sort(int a[], int n) {
int i, j, k, temp;
printf("\nUnsorted Data:");
for (k = 0; k < n; k++)
printf("%5d", a[k]);
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - 1 - i; j++) {
if (a[j] > a[j + 1]) {
// Swap elements
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
// Print array after each pass
printf("\nAfter pass %d: ", i + 1);
for (k = 0; k < n; k++)
printf("%5d", a[k]);
int main() {
int a[50], n, i, op;
do {
printf("\n1) Insertion Sort\n2) Bubble Sort\n3) Quit");
printf("\nEnter your choice: ");
scanf("%d", &op);
switch (op) {
case 1:
printf("\nEnter number of elements: ");
scanf("%d", &n);
printf("\nEnter array elements: ");
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
insertion_sort(a, n);
break;
case 2:
printf("\nEnter number of elements: ");
scanf("%d", &n);
printf("\nEnter array elements: ");
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
bubble_sort(a, n);
break;
} while (op != 3);
return 0;
// Output for binary search
1. Create
2. Search
3. Delete
4. Display
5. Exit
Enter your choice: 1
Enter the element: 5
Do you want to enter more elements? (y/n) y
Enter the element: 3
Do you want to enter more elements? (y/n) y
Enter the element: 8
Do you want to enter more elements? (y/n) n
Enter your choice: 2
Enter the element you want to search: 3
The element 3 is present.
Parent of node 3 is 5
Enter your choice: 3
Enter the element you wish to delete: 5
Now deleted it
Enter your choice: 4
The tree is:
38
Enter your choice: 5
// Output for insertion sort
Elements: 9, 5, 3
Unsorted Data: 9 5 3
After pass 1: 5 9 3
After pass 2: 3 5 9
Sorted Data: 3 5 9
// Output for Bubble sort
Elements: 4, 2, 7
Unsorted Data: 4 2 7
After pass 1: 2 4 7
Sorted Data: 2 4 7
Program -2
Program for Selection, Shell Sort and Counting Sort.
#include <stdio.h>
void selectionSort(int arr[], int n);
void shellSort(int arr[], int n);
void countingSort(int arr[], int n);
void printArray(int arr[], int n);
int main() {
int arr[100], n, choice;
printf("Enter the number of elements: ");
scanf("%d", &n);
printf("Enter the elements:\n");
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
// Menu for sorting options
do {
printf("\nChoose a sorting method:\n");
printf("1. Selection Sort\n");
printf("2. Shell Sort\n");
printf("3. Counting Sort\n");
printf("4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
selectionSort(arr, n);
printf("Sorted Array (Selection Sort): ");
printArray(arr, n);
break;
case 2:
shellSort(arr, n);
printf("Sorted Array (Shell Sort): ");
printArray(arr, n);
break;
case 3:
countingSort(arr, n);
printf("Sorted Array (Counting Sort): ");
printArray(arr, n);
break;
case 4:
printf("Exiting...\n");
break;
default:
printf("Invalid choice. Please try again.\n");
} while (choice != 4);
return 0;
}
// Selection Sort implementation
void selectionSort(int arr[], int n) {
int i, j, minIndex, temp;
for (i = 0; i < n - 1; i++) {
minIndex = i;
for (j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex])
minIndex = j;
temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
// Shell Sort implementation
void shellSort(int arr[], int n) {
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
arr[j] = temp;
}
// Counting Sort implementation
void countingSort(int arr[], int n) {
int output[100], max = arr[0], i;
// Find the maximum value in the array
for (i = 1; i < n; i++) {
if (arr[i] > max)
max = arr[i];
// Create a count array to store the count of each unique object
int count[max + 1];
for (i = 0; i <= max; i++)
count[i] = 0;
// Store the count of each element
for (i = 0; i < n; i++)
count[arr[i]]++;
// Store the cumulative count of each array
for (i = 1; i <= max; i++)
count[i] += count[i - 1];
// Place the elements in sorted order
for (i = n - 1; i >= 0; i--) {
output[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
// Copy the sorted elements into the original array
for (i = 0; i < n; i++)
arr[i] = output[i];
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
printf("\n");
Enter the number of elements: 5
Enter the elements:
29 10 14 37 13
Choose a sorting method:
1. Selection Sort
2. Shell Sort
3. Counting Sort
4. Exit
Enter your choice: 1
Sorted Array (Selection Sort): 10 13 14 29 37
Choose a sorting method:
1. Selection Sort
2. Shell Sort
3. Counting Sort
4. Exit
Enter your choice: 2
Sorted Array (Shell Sort): 10 13 14 29 37
Choose a sorting method:
1. Selection Sort
2. Shell Sort
3. Counting Sort
4. Exit
Enter your choice: 3
Sorted Array (Counting Sort): 10 13 14 29 37
Anshul Kotwal -> 2200270110019
Program -3
Program for Quick Sort, Merge Sort and Heap Sort.
#include <stdio.h>
void quickSort(int arr[], int low, int high);
void mergeSort(int arr[], int left, int right);
void heapSort(int arr[], int n);
void printArray(int arr[], int n);
// Quick Sort helper functions
int partition(int arr[], int low, int high);
void merge(int arr[], int left, int mid, int right);
void heapify(int arr[], int n, int i);
int main() {
int arr[100], n, choice;
// User input
printf("Enter the number of elements: ");
scanf("%d", &n);
printf("Enter the elements:\n");
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
// Menu for sorting options
do {
printf("\nChoose a sorting method:\n");
printf("1. Quick Sort\n");
printf("2. Merge Sort\n");
printf("3. Heap Sort\n");
printf("4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
quickSort(arr, 0, n - 1);
printf("Sorted Array (Quick Sort): ");
printArray(arr, n);
break;
case 2:
mergeSort(arr, 0, n - 1);
printf("Sorted Array (Merge Sort): ");
printArray(arr, n);
break;
case 3:
heapSort(arr, n);
printf("Sorted Array (Heap Sort): ");
printArray(arr, n);
break;
case 4:
printf("Exiting...\n");
break;
default:
printf("Invalid choice. Please try again.\n");
} while (choice != 4);
return 0;
// Quick Sort implementation
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 partition(int arr[], int low, int high) {
int pivot = arr[high], i = low - 1, temp;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return (i + 1);
// Merge Sort implementation
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1, n2 = right - mid;
int L[n1], R[n2];
for (int i = 0; i < n1; i++) L[i] = arr[left + i];
for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) arr[k++] = L[i++];
else arr[k++] = R[j++];
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
// Heap Sort implementation
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--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
void heapify(int arr[], int n, int i) {
int largest = i, left = 2 * i + 1, right = 2 * i + 2, temp;
if (left < n && arr[left] > arr[largest]) largest = left;
if (right < n && arr[right] > arr[largest]) largest = right;
if (largest != i) {
temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
// Function to print an array
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
printf("\n");
Enter the number of elements: 5
Enter the elements:
22 11 99 88 33
Choose a sorting method:
1. Quick Sort
2. Merge Sort
3. Heap Sort
4. Exit
Enter your choice: 1
Sorted Array (Quick Sort): 11 22 33 88 99
Choose a sorting method:
1. Quick Sort
2. Merge Sort
3. Heap Sort
4. Exit
Enter your choice: 2
Sorted Array (Merge Sort): 11 22 33 88 99
Choose a sorting method:
1. Quick Sort
2. Merge Sort
3. Heap Sort
4. Exit
Enter your choice: 3
Sorted Array (Heap Sort): 11 22 33 88 99
Anshul Kotwal -2200270110019
Program -4
Program for BFS and DFS on a graph represented using
Adjacency list.
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
// Structure for the adjacency list node
struct Node {
int vertex;
struct Node* next;
};
// Structure for the graph
struct Graph {
int numVertices;
struct Node* adjLists[MAX_VERTICES];
int visited[MAX_VERTICES];
};
// Queue for BFS
struct Queue {
int items[MAX_VERTICES];
int front, rear;
};
// Function Prototypes
struct Node* createNode(int v);
struct Graph* createGraph(int vertices);
void addEdge(struct Graph* graph, int src, int dest);
void bfs(struct Graph* graph, int startVertex);
void dfs(struct Graph* graph, int vertex);
struct Queue* createQueue();
void enqueue(struct Queue* q, int value);
int dequeue(struct Queue* q);
int isQueueEmpty(struct Queue* q);
void resetVisited(struct Graph* graph);
int main() {
int vertices = 6;
struct Graph* graph = createGraph(vertices);
// Add edges (undirected graph example)
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 2);
addEdge(graph, 1, 3);
addEdge(graph, 2, 4);
addEdge(graph, 3, 5);
addEdge(graph, 4, 5);
printf("BFS starting from vertex 0:\n");
bfs(graph, 0);
resetVisited(graph); // Reset visited array before DFS
printf("\nDFS starting from vertex 0:\n");
dfs(graph, 0);
return 0;
}
// Create a node
struct Node* createNode(int v) {
struct Node* newNode = malloc(sizeof(struct Node));
newNode->vertex = v;
newNode->next = NULL;
return newNode;
}
// Create a graph
struct Graph* createGraph(int vertices) {
struct Graph* graph = malloc(sizeof(struct Graph));
graph->numVertices = vertices;
for (int i = 0; i < vertices; i++) {
graph->adjLists[i] = NULL;
graph->visited[i] = 0;
}
return graph;
}
// Add edge to graph (undirected)
void addEdge(struct Graph* graph, int src, int dest) {
struct Node* newNode = createNode(dest);
newNode->next = graph->adjLists[src];
graph->adjLists[src] = newNode;
newNode = createNode(src);
newNode->next = graph->adjLists[dest];
graph->adjLists[dest] = newNode;
}
// BFS algorithm
void bfs(struct Graph* graph, int startVertex) {
struct Queue* q = createQueue();
graph->visited[startVertex] = 1;
enqueue(q, startVertex);
while (!isQueueEmpty(q)) {
int currentVertex = dequeue(q);
printf("%d ", currentVertex);
struct Node* temp = graph->adjLists[currentVertex];
while (temp) {
int adjVertex = temp->vertex;
if (graph->visited[adjVertex] == 0) {
graph->visited[adjVertex] = 1;
enqueue(q, adjVertex);
}
temp = temp->next;
}
}
}
// DFS algorithm
void dfs(struct Graph* graph, int vertex) {
graph->visited[vertex] = 1;
printf("%d ", vertex);
struct Node* temp = graph->adjLists[vertex];
while (temp) {
int adjVertex = temp->vertex;
if (graph->visited[adjVertex] == 0) {
dfs(graph, adjVertex);
}
temp = temp->next;
}
}
// Queue Functions
struct Queue* createQueue() {
struct Queue* q = malloc(sizeof(struct Queue));
q->front = -1;
q->rear = -1;
return q;
}
int isQueueEmpty(struct Queue* q) {
return q->front == -1;
}
void enqueue(struct Queue* q, int value) {
if (q->rear == MAX_VERTICES - 1) return;
if (q->front == -1) q->front = 0;
q->items[++q->rear] = value;
}
int dequeue(struct Queue* q) {
if (isQueueEmpty(q)) return -1;
int item = q->items[q->front];
if (q->front >= q->rear) {
q->front = -1;
q->rear = -1;
} else {
q->front++;
}
return item;
}
// Reset visited array for reusing graph
void resetVisited(struct Graph* graph) {
for (int i = 0; i < graph->numVertices; i++) {
graph->visited[i] = 0;
}
}
Output :
BFS starting from vertex 0:
012345
DFS starting from vertex 0:
012453
Anshul Kotwal -2200270110019
Program -5
Program for constructing a Minimum Cost Spanning Tree
using Prim’s and Kruskal’s algorithms.
Prim's Algorithm
#include <stdio.h>
#include <limits.h>
#include <stdbool.h>
#define V 5
int minKey(int key[], bool mstSet[]) {
int min = INT_MAX, minIndex;
for (int v = 0; v < V; v++)
if (!mstSet[v] && key[v] < min)
min = key[v], minIndex = v;
return minIndex;
}
void printMST(int parent[], int graph[V][V]) {
printf("Edge \tWeight\n");
for (int i = 1; i < V; i++)
printf("%d - %d \t%d \n", parent[i], i, graph[i][parent[i]]);
void primMST(int graph[V][V]) {
int parent[V]; // Array to store MST
int key[V]; // Key values used to pick minimum weight edge
bool mstSet[V]; // To represent set of vertices included in MST
for (int i = 0; i < V; i++)
key[i] = INT_MAX, mstSet[i] = false;
key[0] = 0;
parent[0] = -1;
for (int count = 0; count < V - 1; count++) {
int u = minKey(key, mstSet);
mstSet[u] = true;
for (int v = 0; v < V; v++)
if (graph[u][v] && !mstSet[v] && graph[u][v] < key[v])
parent[v] = u, key[v] = graph[u][v];
}
printMST(parent, graph);
int main() {
int graph[V][V] = { {0, 2, 0, 6, 0},
{2, 0, 3, 8, 5},
{0, 3, 0, 0, 7},
{6, 8, 0, 0, 9},
{0, 5, 7, 9, 0} };
printf("Prim's MST:\n");
primMST(graph);
return 0;
Kruskal's Algorithm
#include <stdio.h>
#include <stdlib.h>
#define V 5
#define E 7
struct Edge {
int src, dest, weight;
};
struct Graph {
int V, E;
struct Edge* edge;
};
struct Subset {
int parent;
int rank;
};
struct Graph* createGraph(int V, int E) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->V = V;
graph->E = E;
graph->edge = (struct Edge*)malloc(graph->E * sizeof(struct Edge));
return graph;
int find(struct Subset subsets[], int i) {
if (subsets[i].parent != i)
subsets[i].parent = find(subsets, subsets[i].parent);
return subsets[i].parent;
void unionSets(struct Subset subsets[], int x, int y) {
int xroot = find(subsets, x);
int yroot = find(subsets, y);
if (subsets[xroot].rank < subsets[yroot].rank)
subsets[xroot].parent = yroot;
else if (subsets[xroot].rank > subsets[yroot].rank)
subsets[yroot].parent = xroot;
else {
subsets[yroot].parent = xroot;
subsets[xroot].rank++;
int compare(const void* a, const void* b) {
struct Edge* a1 = (struct Edge*)a;
struct Edge* b1 = (struct Edge*)b;
return a1->weight > b1->weight;
void KruskalMST(struct Graph* graph) {
int V = graph->V;
struct Edge result[V];
int e = 0, i = 0;
qsort(graph->edge, graph->E, sizeof(graph->edge[0]), compare);
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;
while (e < V - 1 && i < graph->E) {
struct Edge nextEdge = graph->edge[i++];
int x = find(subsets, nextEdge.src);
int y = find(subsets, nextEdge.dest);
if (x != y) {
result[e++] = nextEdge;
unionSets(subsets, x, y);
printf("\nKruskal's MST:\nEdge \tWeight\n");
for (i = 0; i < e; i++)
printf("%d - %d \t%d\n", result[i].src, result[i].dest, result[i].weight);
int main() {
int V = 5, E = 7;
struct Graph* graph = createGraph(V, E);
graph->edge[0] = (struct Edge){0, 1, 2};
graph->edge[1] = (struct Edge){0, 3, 6};
graph->edge[2] = (struct Edge){1, 2, 3};
graph->edge[3] = (struct Edge){1, 3, 8};
graph->edge[4] = (struct Edge){1, 4, 5};
graph->edge[5] = (struct Edge){2, 4, 7};
graph->edge[6] = (struct Edge){3, 4, 9};
KruskalMST(graph);
return 0;
Prim's MST:
Edge Weight
0-1 2
1-2 3
0-3 6
1-4 5
Kruskal's MST:
Edge Weight
0-1 2
1-2 3
1-4 5
0-3 6
Anshul Kotwal -2200270110019
