Fundamental C Algorithms: Search, Sort, Recursion, and Optimization
Fundamental C Algorithms: Search, Sort, and Optimization
This document presents implementations of several core algorithms in C, including searching, sorting, recursion, and optimization techniques like the Traveling Salesman Problem (TSP) and the Fractional Knapsack problem.
1. Linear Search Algorithm
Linear search is a straightforward method for finding an element within a list. It sequentially checks each element until a match is found or the entire list has been traversed.
C Code for Linear Search
#include <stdio.h>
int linearsearch(int arr[], int size, int key) {
int i;
for (i = 0; i < size; i++) {
if (arr[i] == key) {
return i; // Return index if key is found
}
}
return -1; // Return -1 if key not found
}
int main() {
int arr[] = {10, 50, 20, 90, 60, 40, 30, 80, 70};
int size = sizeof(arr) / sizeof(arr[0]);
int key = 50; // Element to be searched
int result = linearsearch(arr, size, key);
if (result != -1) {
printf("Key %d found in the array at index: %d\n", key, result);
} else {
printf("Key %d not found in the array.\n", key);
}
return 0;
}
Output of Linear Search
Key 50 found in the array at index: 1
2. Recursive Factorial Calculation
The factorial function calculates the product of all positive integers less than or equal to a given non-negative integer $n$. This implementation uses recursion.
C Code for Factorial
#include <stdio.h>
int factorial(int n) {
if (n == 0 || n == 1) {
return 1; // Base case
}
else {
return n * factorial(n - 1); // Recursive call
}
}
int main() {
int num;
long int result;
printf("Enter a non-negative integer: ");
scanf("%d", &num);
if (num < 0) {
printf("Factorial of a negative number is not defined.\n");
}
else {
result = factorial(num);
printf("The factorial of %d is %ld.\n", num, result);
}
return 0;
}
Output of Factorial Calculation
Enter a non-negative integer: 5
The factorial of 5 is 120.
3. Traveling Salesman Problem (TSP) using Backtracking
The Traveling Salesman Problem (TSP) seeks the shortest possible route that visits a set of cities exactly once and returns to the origin city. This solution uses a backtracking approach to find the minimum cost tour.
C Code for TSP Backtracking
#include <stdio.h>
#include <limits.h>
#define MAX 10
int n;
int dist[MAX][MAX];
int visited[MAX];
int min_cost = INT_MAX;
void tsp(int city, int count, int cost, int start) {
if (count == n && dist[city][start]) {
if (min_cost > cost + dist[city][start]) {
min_cost = cost + dist[city][start];
}
return;
}
for (int i = 0; i < n; i++) {
if (!visited[i] && dist[city][i]) {
visited[i] = 1;
tsp(i, count + 1, cost + dist[city][i], start);
visited[i] = 0; // Backtrack
}
}
}
int main() {
printf("Enter number of cities: ");
scanf("%d", &n);
printf("Enter distance matrix:\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &dist[i][j]);
}
}
for (int i = 0; i < n; i++) {
visited[i] = 0;
}
visited[0] = 1; // Start from city 0
tsp(0, 1, 0, 0);
printf("The minimum cost of the tour is: %d\n", min_cost);
return 0;
}
Output of TSP Calculation
Enter number of cities: 3
Enter distance matrix:
0 4 7
4 5 6
3 6 5
The minimum cost of the tour is: 13
4. Fractional Knapsack Problem (Greedy Approach)
The Fractional Knapsack problem aims to maximize the total value of items placed into a knapsack with a limited weight capacity, allowing fractions of items to be included. This solution uses a greedy strategy based on the value-to-weight ratio.
C Code for Fractional Knapsack
#include <stdio.h>
struct item {int w, v;};
double Knapsack(int W, struct item a[], int n)
{
for (int i = 0; i < n - 1; i++)
for (int j = i + 1; j < n; j++) {
if ((double)a[i].v / a[i].w < (double)a[j].v / a[j].w)
{
struct item t = a[i];
a[i] = a[j];
a[j] = t;
}
double Val = 0; {
if (a[i].w <= W) {
W -= a[i].w;
Val += a[i].v;
} else {
Val += a[i].v * ((double)W / a[i].w);
}
} return Val;
}
int main() {
struct item a[] = {{10, 60}, {20, 100}, {30, 120}};
int W = 50, n = 3;
printf("Max Value = %lf\n", Knapsack(W, a, n));
return 0;
}
Output of Fractional Knapsack
Max Value = 120.000000
5. Quick Sort Implementation
Quick Sort is an efficient, comparison-based sorting algorithm that uses a divide-and-conquer strategy. It selects a ‘pivot’ element and partitions the other elements into two sub-arrays according to whether they are less than or greater than the pivot.
C Code for Quick Sort
#include <stdio.h>
void swap(int *a, int *b) {
int t = *a;
*a = *b;
*b = t;
}
int partition(int a[], int l, int h) {
int p = a[h];
int i = l - 1;
for (int j = l; j < h; j++) {
if (a[j] <= p) {
swap(&a[++i], &a[j]);
}
}
swap(&a[i + 1], &a[h]);
return i + 1;
}
void quicksort(int a[], int l, int h) {
if (l < h) {
int pi = partition(a, l, h);
quicksort(a, l, pi - 1);
quicksort(a, pi + 1, h);
}
}
int main() {
int a[] = {10, 7, 8, 9, 1, 5};
int n = 6;
quicksort(a, 0, n - 1);
for (int i = 0; i < n; i++)
printf("%d ", a[i]);
return 0;
}
Output of Quick Sort
Original array: 10 7 8 9 1 5
Sorted array: 1 5 7 8 9 10