C Programs

Algorithms implemented by C programming language which are as follows:

1. Quick Sort

C program to implement the Quick Sort algorithm

// Quick Sort Algorithm

#include <stdio.h>
#include <stdlib.h>

void quickSort(int *arr, int left, int right);
int partition(int *arr, int left, int right);
void swap(int *a, int *b);

int main()
{
    int n, i;
    printf("Enter the number of elements: ");
    scanf("%d", &n);
    int *arr = (int *)malloc(n * sizeof(int));
    printf("Enter the elements: ");
    for (i = 0; i < n; i++)
        scanf("%d", &arr[i]);
    quickSort(arr, 0, n - 1);
    printf("Sorted array: ");
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
    // Print time complexity of the algorithm
    printf("Time complexity: O(nlogn)");
    return 0;
}

void quickSort(int *arr, int left, int right)
{
    if (left < right)
    {
        int pivot = partition(arr, left, right);
        quickSort(arr, left, pivot - 1);
        quickSort(arr, pivot + 1, right);
    }
}

int partition(int *arr, int left, int right)
{
    int pivot = arr[right];
    int i = left - 1;
    for (int j = left; j < right; j++)
    {
        if (arr[j] < pivot)
        {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[right]);
    return i + 1;
}

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Output

// Enter the number of elements: 5
// Enter the elements: 5 4 3 2 1
// Sorted array: 1 2 3 4 5

2. Merge Sort

C program to implement the Merge Sort algorithm

// Merge Sort Algorithm

#include <stdio.h>
#include <stdlib.h>

void mergeSort(int *arr, int left, int right);
void merge(int *arr, int left, int mid, int right);

int main()
{
    int n, i;
    printf("Enter the number of elements: ");
    scanf("%d", &n);
    int *arr = (int *)malloc(n * sizeof(int));
    printf("Enter the elements: ");
    for (i = 0; i < n; i++)
        scanf("%d", &arr[i]);
    mergeSort(arr, 0, n - 1);
    printf("Sorted array: ");
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
    // Print time complexity of the algorithm
    printf("Time complexity: O(nlogn)");
    return 0;
}

void mergeSort(int *arr, int left, int right)
{
    if (left < right)
    {
        int mid = (left + right) / 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 i, j, k;
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int *L = (int *)malloc(n1 * sizeof(int));
    int *R = (int *)malloc(n2 * sizeof(int));
    for (i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];
    i = 0;
    j = 0;
    k = left;
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// Output
//
// Enter the number of elements: 5
// Enter the elements: 5 4 3 2 1
// Sorted array: 1 2 3 4 5

3. Insertion Sort

C program to implement the Insertion Sort algorithm

// Insertion sort in C

#include <stdio.h>
#include <stdlib.h>

void insertionSort(int *arr, int n);

int main()
{
    int n, i;
    printf("Enter the number of elements: ");
    scanf("%d", &n);
    int *arr = (int *)malloc(n * sizeof(int));
    printf("Enter the elements: ");
    for (i = 0; i < n; i++)
        scanf("%d", &arr[i]);
    insertionSort(arr, n);
    printf("Sorted array: ");
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
    // Print time complexity of the algorithm
    printf("Time complexity: O(n^2)");
    return 0;
}

void insertionSort(int *arr, int n)
{
    int i, j, key;
    for (i = 1; i < n; i++)
    {
        key = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

// output
// Enter the number of elements: 5
// Enter the elements: 5 4 3 2 1
// Sorted array: 1 2 3 4 5
// Time complexity: O(n^2)

4. Heap Sort

C program to implement the Heap Sort algorithm

// Heap Sort Algorithm

#include <stdio.h>
#include <stdlib.h>

void heapSort(int *arr, int n);
void heapify(int *arr, int n, int i);
void swap(int *a, int *b);

int main()
{
    int n, i;
    printf("Enter the number of elements: ");
    scanf("%d", &n);
    int *arr = (int *)malloc(n * sizeof(int));
    printf("Enter the elements: ");
    for (i = 0; i < n; i++)
        scanf("%d", &arr[i]);
    heapSort(arr, n);
    printf("Sorted array: ");
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
    // Print time complexity of the algorithm
    printf("Time complexity: O(nlogn)");
    return 0;
}

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--)
    {
        swap(&arr[0], &arr[i]);
        heapify(arr, i, 0);
    }
}

void heapify(int *arr, int n, int i)
{
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < n && arr[left] > arr[largest])
        largest = left;
    if (right < n && arr[right] > arr[largest])
        largest = right;
    if (largest != i)
    {
        swap(&arr[i], &arr[largest]);
        heapify(arr, n, largest);
    }
}

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

//  Output

// Enter the number of elements: 5
// Enter the elements: 5 4 3 2 1
// Sorted array: 1 2 3 4 5

5. N-Queen Problem

C program to solve N-queen Problem using backtracking

//  C program to solve the N-Queen problem
//  using backtracking

#include <stdio.h>
#include <stdlib.h>

#define N 4

int board[N][N];

void print_board(void)
{
    int i, j;
    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
            printf("%d ", board[i][j]);
        }
        printf(" \n");
    }
}

int is_safe(int row, int col)
{
    int i, j;

    // Check this row on left side
    for (i = 0; i < col; i++)
        if (board[row][i])
            return 0;

    // Check upper diagonal on left side
    for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
        if (board[i][j])
            return 0;

    // Check lower diagonal on left side
    for (i = row, j = col; j >= 0 && i < N; i++, j--)
        if (board[i][j])
            return 0;

    return 1;
}

int solve(int col)
{
    int i;
    if (col >= N)
        return 1;

    for (i = 0; i < N; i++) {
        if (is_safe(i, col)) {
            board[i][col] = 1;
            if (solve(col + 1))
                return 1;
            board[i][col] = 0; // BACKTRACK
        }
    }
    return 0;
}

int main(void)
{
    int i, j;
    for (i = 0; i < N; i++)
        for (j = 0; j < N; j++)
            board[i][j] = 0;

    if (solve(0) == 0) {
        printf("Solution does not exist");
        return 0;
    }

    print_board();
    return 0;
}

// Output:
// 0 0 1 0 0 0 0 0  0 0 0 0 0 1 0 0  0 0 0 0 0 0 0 1  0 1 0 0 0 0 0 0  0 0 0 0 0 0 1 0  0 0 0 0 1 0 0 0  0 0 0 0 0 0 0 0  1 0 0 0 0 0 0 0

6. Hamiltonian Cycle

A Hamiltonian cycle, also known as a Hamiltonian circuit, is a path in a graph that visits every vertex exactly once and returns to the starting vertex.

Here is a program in C that finds a Hamiltonian cycle in a graph using the backtracking approach:

/* C program for solution of Hamiltonian Cycle problem
using backtracking */
#include<stdio.h>

// Number of vertices in the graph
#define V 5

void printSolution(int path[]);

/* A utility function to check if the vertex v can be added at
index 'pos' in the Hamiltonian Cycle constructed so far (stored
in 'path[]') */
bool isSafe(int v, bool graph[V][V], int path[], int pos)
{
	/* Check if this vertex is an adjacent vertex of the previously
	added vertex. */
	if (graph [ path[pos-1] ][ v ] == 0)
		return false;

	/* Check if the vertex has already been included.
	This step can be optimized by creating an array of size V */
	for (int i = 0; i < pos; i++)
		if (path[i] == v)
			return false;

	return true;
}

/* A recursive utility function to solve hamiltonian cycle problem */
bool hamCycleUtil(bool graph[V][V], int path[], int pos)
{
	/* base case: If all vertices are included in Hamiltonian Cycle */
	if (pos == V)
	{
		// And if there is an edge from the last included vertex to the
		// first vertex
		if ( graph[ path[pos-1] ][ path[0] ] == 1 )
		return true;
		else
		return false;
	}

	// Try different vertices as a next candidate in Hamiltonian Cycle.
	// We don't try for 0 as we included 0 as starting point in hamCycle()
	for (int v = 1; v < V; v++)
	{
		/* Check if this vertex can be added to Hamiltonian Cycle */
		if (isSafe(v, graph, path, pos))
		{
			path[pos] = v;

			/* recur to construct rest of the path */
			if (hamCycleUtil (graph, path, pos+1) == true)
				return true;

			/* If adding vertex v doesn't lead to a solution,
			then remove it */
			path[pos] = -1;
		}
	}

	/* If no vertex can be added to Hamiltonian Cycle constructed so far,
	then return false */
	return false;
}

/* This function solves the Hamiltonian Cycle problem using Backtracking.
It mainly uses hamCycleUtil() to solve the problem. It returns false
if there is no Hamiltonian Cycle possible, otherwise return true and
prints the path. Please note that there may be more than one solutions,
this function prints one of the feasible solutions. */
bool hamCycle(bool graph[V][V])
{
	int *path = new int[V];
	for (int i = 0; i < V; i++)
		path[i] = -1;

	/* Let us put vertex 0 as the first vertex in the path. If there is
	a Hamiltonian Cycle, then the path can be started from any point
	of the cycle as the graph is undirected */
	path[0] = 0;
	if ( hamCycleUtil(graph, path, 1) == false )
	{
		printf("\nSolution does not exist");
		return false;
	}

	printSolution(path);
	return true;
}

/* A utility function to print solution */
void printSolution(int path[])
{
	printf ("Solution Exists:"
			" Following is one Hamiltonian Cycle \n");
	for (int i = 0; i < V; i++)
		printf(" %d ", path[i]);

	// Let us print the first vertex again to show the complete cycle
	printf(" %d ", path[0]);
	printf("\n");
}

// driver program to test above function
int main()
{
/* Let us create the following graph
	(0)--(1)--(2)
	| / \ |
	| / \ |
	| /	 \ |
	(3)-------(4) */
bool graph1[V][V] = {{0, 1, 0, 1, 0},
					{1, 0, 1, 1, 1},
					{0, 1, 0, 0, 1},
					{1, 1, 0, 0, 1},
					{0, 1, 1, 1, 0},
					};

	// Print the solution
	hamCycle(graph1);

/* Let us create the following graph
	(0)--(1)--(2)
	| / \ |
	| / \ |
	| /	 \ |
	(3)	 (4) */
	bool graph2[V][V] = {{0, 1, 0, 1, 0},
					{1, 0, 1, 1, 1},
					{0, 1, 0, 0, 1},
					{1, 1, 0, 0, 0},
					{0, 1, 1, 0, 0},
					};

	// Print the solution
	hamCycle(graph2);

	return 0;
}

Explanation:

hamCycleUtil: This is a recursive function that tries different vertices as a next vertex in Hamiltonian cycle. It keeps moving forward and if there are no vertices left to visit and all vertices are covered then it returns true.
isSafe: This function checks if adding vertex v to the path followed so far results in a solution or not.
hamCycle: This function first initializes the path array with -1 and path[0] as 0. Then it calls hamCycleUtil. If hamCycleUt

7. Prim's Algorithm

Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. It starts with an arbitrary vertex and adds edges that connect it to the vertices with the lowest weight until all vertices are connected.

Here is a C program that implements Prim's algorithm:

#include <stdio.h>
#include <stdbool.h>
#define V 5
#define INF 99999

int minKey(int key[], bool mstSet[]) 
{
   int min = INF, min_index;
 
   for (int v = 0; v < V; v++) 
     if (mstSet[v] == false && key[v] < min) 
         min = key[v], min_index = v;
 
   return min_index;
}
 
void primMST(int graph[V][V]) 
{
   int parent[V]; 
   int key[V];   
   bool mstSet[V];  
 
   for (int i = 0; i < V; i++) 
      key[i] = INF, 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] == false && graph[u][v] <  key[v]) 
            parent[v]  = u, key[v] = graph[u][v];
   }
 
   printf("Edge   Weight\n");
   for (int i = 1; i < V; i++)
      printf("%d - %d    %d \n", parent[i], i, graph[i][parent[i]]);
}
 
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},
                     };
 
   primMST(graph);
 
   return 0;
}

Explanation:

minKey: This function returns the vertex with the minimum key value, which is not yet included in the MST.
primMST: This function builds the MST by maintaining two sets of vertices: the set of vertices included in the MST and the set of vertices not yet included. Initially, all vertices are not yet included in the MST and the key values are set to a high value (INF). The minimum key vertex is then selected and added to the MST set. Its adjacent vertices are updated with the new minimum weight if a shorter edge is found. This process continues until all vertices are included in the MST.
The main function initializes a sample graph and calls the primMST function to build the MST, which is then printed to the console. The output shows the edges and their weights that form the minimum spanning tree.

8. Kruskal's Algorithm

Kruskal's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. It starts with an empty tree and adds edges one by one until it forms a tree that includes every vertex. The added edges are always the ones with the lowest weight.

Here is a C program that implements Kruskal's algorithm:

// C prgram for Kruskal's algorithm to find Minimum Spanning Tree
// of a given connected, undirected and weighted graph
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#define V 5
#define INF 99999
// A structure to represent a graph
struct Graph
{
    int V, E;
    struct Edge* edge;
};
// A structure to represent a edge in graph
struct Edge
{
    int src, dest, weight;
};
// A structure to represent a subset for union-find
struct subset
{
    int parent;
    int rank;
};
// A utility function to find set of an element i
// (uses path compression technique)
int find(struct subset subsets[], int i)
{
    // find root and make root as parent of i (path compression)
    if (subsets[i].parent != i)
        subsets[i].parent = find(subsets, subsets[i].parent);
    return subsets[i].parent;
}
// A function that does union of two sets of x and y
// (uses union by rank)
void Union(struct subset subsets[], int x, int y)
{
    int xroot = find(subsets, x);
    int yroot = find(subsets, y);
    // Attach smaller rank tree under root of high rank tree
    // (Union by Rank)
    if (subsets[xroot].rank < subsets[yroot].rank)
        subsets[xroot].parent = yroot;
    else if (subsets[xroot].rank > subsets[yroot].rank)
        subsets[yroot].parent = xroot;
    // If ranks are same, then make one as root and increment
    // its rank by one
    else
    {
        subsets[yroot].parent = xroot;
        subsets[xroot].rank++;
    }
}
// Compare two edges according to their weights.
// Used in qsort() for sorting an array of edges
int myComp(const void* a, const void* b)
{
    struct Edge* a1 = (struct Edge*)a;
    struct Edge* b1 = (struct Edge*)b;
    return a1->weight > b1->weight;
}
// The main function to construct MST using Kruskal's algorithm
void KruskalMST(struct Graph* graph)
{
    int V = graph->V;
    struct Edge result[V]; // Tnis will store the resultant MST
    int e = 0; // An index variable, used for result[]
    int i = 0; // An index variable, used for sorted edges
    // Step 1:  Sort all the edges in non-decreasing order of their
    // weight.  If we are not allowed to change the given graph, we
    // can create a copy of array of edges
    qsort(graph->edge, graph->E, sizeof(graph->edge[0]), myComp);
    // Allocate memory for creating V ssubsets
    struct subset *subsets =
        (struct subset*) malloc( V * sizeof(struct subset) );
    // Create V subsets with single elements
    for (int v = 0; v < V; ++v)
    {
        subsets[v].parent = v;
        subsets[v].rank = 0;
    }
    // Number of edges to be taken is equal to V-1
    while (e < V - 1)
    {
        // Step 2: Pick the smallest edge. And increment the index
        // for next iteration
        struct Edge next_edge = graph->edge[i++];
        int x = find(subsets, next_edge.src);
        int y = find(subsets, next_edge.dest);
        // If including this edge does't cause cycle, include it
        // in result and increment the index of result for next edge
        if (x != y)
        {
            result[e++] = next_edge;
            Union(subsets, x, y);
        }
        // Else discard the next_edge
    }
    // print the contents of result[] to display the built MST
    printf("Following are the edges in the constructed MST \n");
    for (i = 0; i < e; ++i)
        printf("%d -- %d == %d \n", result[i].src, result[i].dest,
                                                 result[i].weight);
    return;
}
// Driver program to test above functions
int main()
{
    /* Let us create following weighted graph
             10
        0--------1
        |  \     |
       6|   5\   |15
        |      \ |
        2--------3
            4       */
    int V = 4; // Number of vertices in graph
    int E = 5; // Number of edges in graph
    struct Graph* graph = createGraph(V, E);
    // add edge 0-1
    graph->edge[0].src = 0;
    graph->edge[0].dest = 1;
    graph->edge[0].weight = 10;
    // add edge 0-2
    graph->edge[1].src = 0;
    graph->edge[1].dest = 2;
    graph->edge[1].weight = 6;
    // add edge 0-3
    graph->edge[2].src = 0;
    graph->edge[2].dest = 3;
    graph->edge[2].weight = 5;
    // add edge 1-3
    graph->edge[3].src = 1;
    graph->edge[3].dest = 3;
    graph->edge[3].weight = 15;
    // add edge 2-3
    graph->edge[4].src = 2;
    graph->edge[4].dest = 3;
    graph->edge[4].weight = 4;
    KruskalMST(graph);
    return 0;
}
// A utility function to create a graph with V vertices and E edges
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;
}

9. Graph Coloring

Graph coloring is the process of assigning colors to the vertices of a graph such that no two adjacent vertices have the same color. The number of colors used is referred to as the chromatic number.

Here is a C program that implements a backtracking algorithm for graph coloring:

// C program for the above approach

#include <stdbool.h>
#include <stdio.h>

// Number of vertices in the graph
#define V 4

void printSolution(int color[]);

// check if the colored
// graph is safe or not
bool isSafe(bool graph[V][V], int color[])
{
	// check for every edge
	for (int i = 0; i < V; i++)
		for (int j = i + 1; j < V; j++)
			if (graph[i][j] && color[j] == color[i])
				return false;
	return true;
}

/* This function solves the m Coloring
problem using recursion. It returns
false if the m colours cannot be assigned,
otherwise, return true and prints
assignments of colours to all vertices.
Please note that there may be more than
one solutions, this function prints one
of the feasible solutions.*/
bool graphColoring(bool graph[V][V], int m, int i,
				int color[V])
{
	// if current index reached end
	if (i == V) {
		// if coloring is safe
		if (isSafe(graph, color)) {
			// Print the solution
			printSolution(color);
			return true;
		}
		return false;
	}

	// Assign each color from 1 to m
	for (int j = 1; j <= m; j++) {
		color[i] = j;

		// Recur of the rest vertices
		if (graphColoring(graph, m, i + 1, color))
			return true;

		color[i] = 0;
	}

	return false;
}

/* A utility function to print solution */
void printSolution(int color[])
{
	printf("Solution Exists:"
		" Following are the assigned colors \n");
	for (int i = 0; i < V; i++)
		printf(" %d ", color[i]);
	printf("\n");
}

// Driver code
int main()
{
	/* Create following graph and
	test whether it is 3 colorable
	(3)---(2)
	| / |
	| / |
	| / |
	(0)---(1)
	*/
	bool graph[V][V] = {
		{ 0, 1, 1, 1 },
		{ 1, 0, 1, 0 },
		{ 1, 1, 0, 1 },
		{ 1, 0, 1, 0 },
	};
	int m = 3; // Number of colors

	// Initialize all color values as 0.
	// This initialization is needed
	// correct functioning of isSafe()
	int color[V];
	for (int i = 0; i < V; i++)
		color[i] = 0;

	// Function call
	if (!graphColoring(graph, m, 0, color))
		printf("Solution does not exist");

	return 0;
}

Explanation:

isSafe: This function checks if it is safe to color a vertex with a given color by checking if any of its adjacent vertices have the same color.
graphColoringUtil: This is the recursive function that implements the backtracking algorithm. It assigns a color to each vertex and checks if it is a feasible solution by calling itself for the next vertex. If a solution is not possible with the current assignment, it backtracks by changing the color and trying a different color for the current vertex.
graphColoring: This function initializes the color array and calls the graphColoringUtil function. If a solution exists, it prints the assigned colors for each vertex.

C Programs #

1. Quick Sort #

2. Merge Sort #

3. Insertion Sort #

4. Heap Sort #

5. N-Queen Problem #

6. Hamiltonian Cycle #

7. Prim's Algorithm #

8. Kruskal's Algorithm #

9. Graph Coloring #

C Programs

1. Quick Sort

2. Merge Sort

3. Insertion Sort

4. Heap Sort

5. N-Queen Problem

6. Hamiltonian Cycle

7. Prim's Algorithm

8. Kruskal's Algorithm

9. Graph Coloring