Insertion sort

#include <math.h>
#include <stdio.h>

void insertionSort(int arr[], int N) {

// Starting from the second element

for (int i = 1; i < N; i++) {
int key = arr[i];
int j = i - 1;

// Move elements of arr[0..i-1], that are

// greater than key, to one position to
// the right of their current position
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}

// Move the key to its correct position

arr[j + 1] = key;
}
}

int main() {
int arr[] = { 12, 11, 13, 5, 6 };
int N = sizeof(arr) / sizeof(arr[0]);

printf("Unsorted array: ");

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

// Calling insertion sort on array arr

insertionSort(arr, N);

printf("Sorted array: ");

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

return 0;
}

Shell sort

// Shell Sort in C programming

#include <stdio.h>
// Shell sort

void shellSort(int array[], int n) {

// Rearrange elements at each n/2, n/4, n/8, ... intervals

for (int interval = n / 2; interval > 0; interval /= 2) {

for (int i = interval; i < n; i += 1) {

int temp = array[i];

int j;

for (j = i; j >= interval && array[j - interval] > temp; j -= interval) {

array[j] = array[j - interval];

array[j] = temp;

// Print an array

void printArray(int array[], int size) {

for (int i = 0; i < size; ++i) {

printf("%d ", array[i]);

printf("\n");

// Driver code
int main() {

int data[] = {9, 8, 3, 7, 5, 6, 4, 1};

int size = sizeof(data) / sizeof(data[0]);

shellSort(data, size);

printf("Sorted array: \n");

printArray(data, size);

Merge sort

// Merge sort in C

#include <stdio.h>

// Merge two subarrays L and M into arr

void merge(int arr[], int p, int q, int r) {

// Create L ← A[p..q] and M ← A[q+1..r]

int n1 = q - p + 1;

int n2 = r - q;

int L[n1], M[n2];

for (int i = 0; i < n1; i++)

L[i] = arr[p + i];

for (int j = 0; j < n2; j++)

M[j] = arr[q + 1 + j];

// Maintain current index of sub-arrays and main array

int i, j, k;

i = 0;

j = 0;

k = p;

// Until we reach either end of either L or M, pick larger among

// elements L and M and place them in the correct position at A[p..r]

while (i < n1 && j < n2) {

if (L[i] <= M[j]) {

arr[k] = L[i];

i++;

} else {

arr[k] = M[j];

j++;

k++;

// When we run out of elements in either L or M,

// pick up the remaining elements and put in A[p..r]

while (i < n1) {

arr[k] = L[i];

i++;
 k++;

while (j < n2) {

arr[k] = M[j];

j++;

k++;

// Divide the array into two subarrays, sort them and merge them

void mergeSort(int arr[], int l, int r) {

if (l < r) {

// m is the point where the array is divided into two subarrays

int m = l + (r - l) / 2;

mergeSort(arr, l, m);

mergeSort(arr, m + 1, r);

// Merge the sorted subarrays

merge(arr, l, m, r);

}
// Print the array

void printArray(int arr[], int size) {

for (int i = 0; i < size; i++)

printf("%d ", arr[i]);

printf("\n");

// Driver program

int main() {

int arr[] = {6, 5, 12, 10, 9, 1};

int size = sizeof(arr) / sizeof(arr[0]);

mergeSort(arr, 0, size - 1);

printf("Sorted array: \n");

printArray(arr, size);

Quick sort

// Quick sort in C

#include <stdio.h>

// function to swap elements

void swap(int *a, int *b) {

int t = *a;
 *a = *b;

*b = t;

// function to find the partition position

int partition(int array[], int low, int high) {

// select the rightmost element as pivot

int pivot = array[high];

// pointer for greater element

int i = (low - 1);

// traverse each element of the array

// compare them with the pivot

for (int j = low; j < high; j++) {

if (array[j] <= pivot) {

// if element smaller than pivot is found

// swap it with the greater element pointed by i

i++;

// swap element at i with element at j

swap(&array[i], &array[j]);

}
 }

// swap the pivot element with the greater element at i

swap(&array[i + 1], &array[high]);

// return the partition point

return (i + 1);

void quickSort(int array[], int low, int high) {

if (low < high) {

// find the pivot element such that

// elements smaller than pivot are on left of pivot

// elements greater than pivot are on right of pivot

int pi = partition(array, low, high);

// recursive call on the left of pivot

quickSort(array, low, pi - 1);

// recursive call on the right of pivot

quickSort(array, pi + 1, high);

}
// function to print array elements

void printArray(int array[], int size) {

for (int i = 0; i < size; ++i) {

printf("%d ", array[i]);

printf("\n");

// main function

int main() {

int data[] = {8, 7, 2, 1, 0, 9, 6};

int n = sizeof(data) / sizeof(data[0]);

printf("Unsorted Array\n");

printArray(data, n);

// perform quicksort on data

quickSort(data, 0, n - 1);

printf("Sorted array in ascending order: \n");

printArray(data, n);

Count sort

// Counting sort in C programming

#include <stdio.h>

void countingSort(int array[], int size) {

int output[10];

// Find the largest element of the array

int max = array[0];

for (int i = 1; i < size; i++) {

if (array[i] > max)

max = array[i];

// The size of count must be at least (max+1) but

// we cannot declare it as int count(max+1) in C as

// it does not support dynamic memory allocation.

// So, its size is provided statically.

int count[10];

// Initialize count array with all zeros.

for (int i = 0; i <= max; ++i) {

count[i] = 0;

// Store the count of each element

 for (int i = 0; i < size; i++) {

count[array[i]]++;

// Store the cummulative count of each array

for (int i = 1; i <= max; i++) {

count[i] += count[i - 1];

// Find the index of each element of the original array in count array, and

// place the elements in output array

for (int i = size - 1; i >= 0; i--) {

output[count[array[i]] - 1] = array[i];

count[array[i]]--;

// Copy the sorted elements into original array

for (int i = 0; i < size; i++) {

array[i] = output[i];

// Function to print an array

void printArray(int array[], int size) {

for (int i = 0; i < size; ++i) {

 printf("%d ", array[i]);

printf("\n");

// Driver code

int main() {

int array[] = {4, 2, 2, 8, 3, 3, 1};

int n = sizeof(array) / sizeof(array[0]);

countingSort(array, n);

printArray(array, n);

Heap sort

// C Program for HeapSort

#include <stdio.h>

// Heapify function

void heapify(int arr[], int n, int i)

int temp, maximum, left_index, right_index;

// currently assuming i postion to

// be holding the largest value

maximum = i;

// right child index

right_index = 2 * i + 2;

// left child index

 left_index = 2 * i + 1;

// if left index value is grater than the current index

// value

if (left_index < n && arr[left_index] > arr[maximum])

maximum = left_index;

// if right index value is grater than the current index

// value

if (right_index < n && arr[right_index] > arr[maximum])

maximum = right_index;

// checking if we needed swaping the elements or not

if (maximum != i) {

temp = arr[i];

arr[i] = arr[maximum];

arr[maximum] = temp;

heapify(arr, n, maximum);

// HeapSorting function

void heapsort(int arr[], int n)

int i, temp;
 // performing heapify on the non leaf nodes so n/2 - 1

// to 0 are the non leaf nodes

for (i = n / 2 - 1; i >= 0; i--) {

heapify(arr, n, i);

// the current array is changed to max heap

for (i = n - 1; i > 0; i--) {

temp = arr[0];

arr[0] = arr[i];

arr[i] = temp;

heapify(arr, i, 0);

// Driver code

int main()

// initializing the array

int arr[] = { 20, 18, 5, 15, 3, 2 };

int n = 6;

// Displaying original array

printf("Original Array : ");

 for (int i = 0; i < n; i++) {

printf("%d ", arr[i]);

printf("\n");

heapsort(arr, n);

// Displaying sorted array

printf("Array after performing heap sort: ");

for (int i = 0; i < n; i++) {

printf("%d ", arr[i]);

return 0;

MATRIX CHAIN MULTIPLICATION

#include <limits.h>

#include <stdio.h>

// Matrix Ai has dimension p[i-1] x p[i]

// for i = 1 . . . n

int MatrixChainOrder(int p[], int i, int j)

if (i == j)

return 0;

int k;

int min = INT_MAX;

int count;

for (k = i; k < j; k++)

 {

count = MatrixChainOrder(p, i, k)

+ MatrixChainOrder(p, k + 1, j)

+ p[i - 1] * p[k] * p[j];

if (count < min)

min = count;

// Return minimum count

return min;

int main()

int arr[] = { 1, 2, 3, 4, 3 };

int N = sizeof(arr) / sizeof(arr[0]);

// Function call

printf("Minimum number of multiplications is %d ",

MatrixChainOrder(arr, 1, N - 1));

getchar();

return 0;

}
 LONGEST COMMON SEQUENCE
// C program to find longest common subsequence using
// recursion

#include <stdio.h>
#include <string.h>

// Function to return the maximum of two integers

int max(int a, int b)
{
// Return a if a is greater than b, otherwise return b
return (a > b) ? a : b;
}

// Function to find the length of the Longest Common

// Subsequence (LCS) using recursion
int lcsRecursive(char* X, char* Y, int m, int n)
{
// Base case: If either string is empty, LCS length is 0
if (m == 0 || n == 0)
return 0;

// If the characters match, include them in LCS and

// recur for the remaining strings
if (X[m - 1] == Y[n - 1])
return 1 + lcsRecursive(X, Y, m - 1, n - 1);

// If the characters do not match, recursively find LCS

// by excluding one character at a time
 else
// Return the maximum of LCS by excluding either the
// last character of X or Y
return max(lcsRecursive(X, Y, m, n - 1),
lcsRecursive(X, Y, m - 1, n));
}

int main()
{
// First string
char X[] = "AGGTAB";
// Second string
char Y[] = "GXTXAYB";

// Length of first string

int m = strlen(X);
// Length of second string
int n = strlen(Y);

// Calculate and print the length of Longest Common

// Subsequence (LCS)
printf("Length of LCS is %d\n",
lcsRecursive(X, Y, m, n));

return 0;
}

NAÏVE STRING MATCHING

#include <stdio.h>
#include <string.h>

void search(char* pat, char* txt) {

int M = strlen(pat);
int N = strlen(txt);

// A loop to slide pat[] one by one

for (int i = 0; i <= N - M; i++) {
int j;

// For current index i, check for pattern match

for (j = 0; j < M; j++) {
if (txt[i + j] != pat[j]) {
break;
}
}

// If pattern matches at index i

if (j == M) {
printf("Pattern found at index %d\n", i);
}
}
}

int main() {
// Example 1
 char txt1[] = "AABAACAADAABAABA";
char pat1[] = "AABA";
printf("Example 1:\n");
search(pat1, txt1);

// Example 2
char txt2[] = "agd";
char pat2[] = "g";
printf("\nExample 2:\n");
search(pat2, txt2);

return 0;
}

FLOYDD WARSHAL

#include <stdio.h>

// defining the number of vertices

#define nV 4

#define INF 999

void printMatrix(int matrix[][nV]);

// Implementing floyd warshall algorithm

void floydWarshall(int graph[][nV]) {

int matrix[nV][nV], i, j, k;

for (i = 0; i < nV; i++)

for (j = 0; j < nV; j++)

matrix[i][j] = graph[i][j];

// Adding vertices individually

 for (k = 0; k < nV; k++) {

for (i = 0; i < nV; i++) {

for (j = 0; j < nV; j++) {

if (matrix[i][k] + matrix[k][j] < matrix[i][j])

matrix[i][j] = matrix[i][k] + matrix[k][j];

printMatrix(matrix);

void printMatrix(int matrix[][nV]) {

for (int i = 0; i < nV; i++) {

for (int j = 0; j < nV; j++) {

if (matrix[i][j] == INF)

printf("%4s", "INF");

else

printf("%4d", matrix[i][j]);

printf("\n");

int main() {

int graph[nV][nV] = {{0, 3, INF, 5},

 {2, 0, INF, 4},

{INF, 1, 0, INF},

{INF, INF, 2, 0}};

floydWarshall(graph);