Program 1: Binary Search (Iterative & Recursive)
Implementation of Binary Search algorithm in C using both iterative and recursive
approaches.
C Source Code
#include <stdio.h>
int iterativeBinarySearch(int arr[], int low, int high, int x) {
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == x) return mid;
if (arr[mid] < x) low = mid + 1;
else high = mid - 1;
}
return -1;
}
int recursiveBinarySearch(int arr[], int low, int high, int x) {
if (high >= low) {
int mid = low + (high - low) / 2;
if (arr[mid] == x) return mid;
if (arr[mid] > x) return recursiveBinarySearch(arr, low, mid - 1, x);
return recursiveBinarySearch(arr, mid + 1, high, x);
}
return -1;
}
int main() {
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 10;
int result = iterativeBinarySearch(arr, 0, n - 1, x);
printf("Iterative: Element found at index %d\n", result);
result = recursiveBinarySearch(arr, 0, n - 1, x);
printf("Recursive: Element found at index %d\n", result);
return 0;
}
Output
Iterative: Element found at index 3
Recursive: Element found at index 3
Program 2: Quick Sort
A divide-and-conquer sorting algorithm that picks an element as pivot and partitions
the array around it.
C Source Code
#include <stdio.h>
void swap(int* a, int* b) {
int t = *a; *a = *b; *b = t;
}
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++; swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
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 arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
printf("Sorted array: ");
for (int i = 0; i < n; i++) printf("%d ", arr[i]);
return 0;
}
Output
Sorted array: 1 5 7 8 9 10
Program 3: Merge Sort
A stable, comparison-based sorting algorithm using the divide and conquer strategy.
C Source Code
#include <stdio.h>
void merge(int arr[], int l, int m, int r) {
int n1 = m - l + 1, n2 = r - m;
int L[n1], R[n2];
for (int i = 0; i < n1; i++) L[i] = arr[l + i];
for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];
int i = 0, j = 0, k = l;
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++];
}
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);
}
}
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = 6;
mergeSort(arr, 0, n - 1);
printf("Sorted array: ");
for (int i = 0; i < n; i++) printf("%d ", arr[i]);
return 0;
}
Output
Sorted array: 5 6 7 11 12 13
Program 4: Heap Sort
A comparison-based sorting technique based on Binary Heap data structure.
C Source Code
#include <stdio.h>
void heapify(int arr[], int n, int i) {
int largest = i, l = 2 * i + 1, r = 2 * i + 2;
if (l < n && arr[l] > arr[largest]) largest = l;
if (r < n && arr[r] > arr[largest]) largest = r;
if (largest != i) {
int temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp;
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--) {
int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp;
heapify(arr, i, 0);
}
}
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = 6;
heapSort(arr, n);
printf("Sorted array: ");
for (int i = 0; i < n; i++) printf("%d ", arr[i]);
return 0;
}
Output
Sorted array: 5 6 7 11 12 13
Program 5: Insertion Sort
A simple sorting algorithm that builds the final sorted array one item at a time.
C Source Code
#include <stdio.h>
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i], j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
int main() {
int arr[] = {12, 11, 13, 5, 6};
int n = 5;
insertionSort(arr, n);
printf("Sorted array: ");
for (int i = 0; i < n; i++) printf("%d ", arr[i]);
return 0;
}
Output
Sorted array: 5 6 11 12 13
Program 6: Selection Sort
An in-place comparison sorting algorithm that divides the list into a sorted and
unsorted part.
C Source Code
#include <stdio.h>
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int min_idx = i;
for (int j = i + 1; j < n; j++)
if (arr[j] < arr[min_idx]) min_idx = j;
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = 5;
selectionSort(arr, n);
printf("Sorted array: ");
for (int i = 0; i < n; i++) printf("%d ", arr[i]);
return 0;
}
Output
Sorted array: 11 12 22 25 64
Program 7: Knapsack Problems
7a. Fractional Knapsack (Greedy)
#include <stdio.h>
#include <stdlib.h>
struct Item { int val, weight; };
int compare(const void* a, const void* b) {
double r1 = (double)((struct Item*)a)->val / ((struct Item*)a)->weight;
double r2 = (double)((struct Item*)b)->val / ((struct Item*)b)->weight;
return (r2 > r1) ? 1 : -1;
}
double fractionalKnapsack(int W, struct Item arr[], int n) {
qsort(arr, n, sizeof(struct Item), compare);
double finalval = 0.0;
for (int i = 0; i < n; i++) {
if (arr[i].weight <= W) { W -= arr[i].weight; finalval += arr[i].val; }
else { finalval += arr[i].val * ((double)W / arr[i].weight); break; }
}
return finalval;
}
7b. 0/1 Knapsack (Dynamic Programming)
int knapSack(int W, int wt[], int val[], int n) {
int K[n+1][W+1];
for (int i = 0; i <= n; i++) {
for (int w = 0; w <= W; w++) {
if (i == 0 || w == 0) K[i][w] = 0;
else if (wt[i-1] <= w) K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);
else K[i][w] = K[i-1][w];
}
}
return K[n][W];
}
Output
Greedy Knapsack Max value: 240.00
DP Knapsack Max value: 220
Program 8: Minimum Spanning Tree (Kruskal's)
Finding MST for an undirected connected graph using Kruskal's algorithm.
C Source Code
#include <stdio.h>
#include <stdlib.h>
struct Edge { int src, dest, weight; };
struct Graph { int V, E; struct Edge* edge; };
struct subset { int parent, rank; };
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 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]), myComp);
struct subset* subsets = 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 next_edge = graph->edge[i++];
int x = find(subsets, next_edge.src), y = find(subsets, next_edge.dest);
if (x != y) { result[e++] = next_edge; Union(subsets, x, y); }
}
}
Output
Edges in MST:
2 -- 3 == 4
0 -- 3 == 5
0 -- 1 == 10
Program 9: Floyd-Warshall Algorithm
All-pairs shortest path algorithm.
C Source Code
#include <stdio.h>
#define INF 99999
#define V 4
void floydWarshall(int graph[][V]) {
int dist[V][V], i, j, k;
for (i = 0; i < V; i++) for (j = 0; j < V; j++) dist[i][j] = graph[i][j];
for (k = 0; k < V; k++) {
for (i = 0; i < V; i++) {
for (j = 0; j < V; j++) {
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
for (i = 0; i < V; i++) {
for (j = 0; j < V; j++) {
if (dist[i][j] == INF) printf("%7s", "INF");
else printf("%7d", dist[i][j]);
}
printf("\n");
}
}
Output
Shortest distances between every pair of vertices:
0 5 8 9
INF 0 3 4
INF INF 0 1
INF INF INF 0
Program 10: N-Queen Problem (Backtracking)
Placing N chess queens on an NxN chessboard so that no two queens threaten each
other.
C Source Code
#include <stdio.h>
#include <stdbool.h>
#define N 4
bool isSafe(int board[N][N], int row, int col) {
int i, j;
for (i = 0; i < col; i++) if (board[row][i]) return false;
for (i = row, j = col; i >= 0 && j >= 0; i--, j--) if (board[i][j]) return false;
for (i = row, j = col; j >= 0 && i < N; i++, j--) if (board[i][j]) return false;
return true;
}
bool solveNQUtil(int board[N][N], int col) {
if (col >= N) return true;
for (int i = 0; i < N; i++) {
if (isSafe(board, i, col)) {
board[i][col] = 1;
if (solveNQUtil(board, col + 1)) return true;
board[i][col] = 0;
}
}
return false;
}
Output
0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0