Divide and Conquer Algorithms in C: Merge Sort, Quick Sort, Fractional Knapsack, Kruskal’s, Prim’s, LCS, N-Queens, and Rabin-Karp
Merge Sort using Divide and Conquer
C Code
#include
void merge(int a[], int beg, int mid, int end)
{
int i, j, k;
int n1 = mid – beg + 1;
int n2 = end – mid;
int LeftArray[n1], RightArray[n2];
for (int i = 0; i < n1; i++)
LeftArray[i] = a[beg + i];
for (int j = 0; j < n2; j++)
RightArray[j] = a[mid + 1 + j];
i = 0;
j = 0;
k = beg;
while (i < n1 && j < n2)
{
if(LeftArray[i] <= RightArray[j])
{
a[k] = LeftArray[i];
i++;
}
else
{
a[k] = RightArray[j];
j++;
}
k++;
}
while (i{
a[k] = LeftArray[i];
i++;
k++;
}
while (j{
a[k] = RightArray[j];
j++;
k++;
}
}
void mergeSort(int a[], int beg, int end)
{
if (beg < end)
{
int mid = (beg + end) / 2;
mergeSort(a, beg, mid);
mergeSort(a, mid + 1, end);
merge(a, beg, mid, end);
}
}
void printArray(int a[], int n)
{
int i;
for (i = 0; i < n; i++)
printf(“%d “, a[i]);
printf(“\n”);
}
int main()
{
int a[] = { 12, 31, 25, 8, 32, 17, 40, 42 };
int n = sizeof(a) / sizeof(a[0]);
printf(“Before sorting array elements are – \n”);
printArray(a, n);
mergeSort(a, 0, n – 1);
printf(“After sorting array elements are – \n”);
printArray(a, n);
return 0;
}
Quick Sort using Divide and Conquer
C Code
#include
void quicksort(int num[25], int first, int last)
{
int i, j, pivot, temp;
if(first{
pivot = first;
i= first;
j= last;
while(i{
while(num[i]<=num[pivot]&&ii++;
while(num[j]>num[pivot])
j–;
if(i{
temp = num[i];
num[i] = num[j];
num[j] = temp;
}
}
temp = num[pivot];
num[pivot] = num[j];
num[j] = temp;
quicksort(num,first,j-1);
quicksort(num,j+1,last);
}
}
int main()
{
int i, count, num[25];
printf(“How many elements are you going to enter?: “);
scanf(“%d”,&count);
printf(“Enter %d elements: “, count);
for(i=0;iscanf(“%d”,&num[i]);
quicksort(num,0,count-1);
printf(“Order of Sorted elements: “);
for(i=0;iprintf(” %d”,num[i]);
return 0;
}
Fractional Knapsack Problem using Greedy Method
C Code
#include
void knapsack(int n,float weight[],float profit[],float capacity){
float x[20],tp=0;
int i,j,u;
u=capacity;
for (i = 0; i < n; i++)
x[i] = 0.0;
for (i = 0; i < n; i++) {
if (weight[i] > u)
break;
else {
x[i] = 1.0;
tp = tp + profit[i];
u = u – weight[i];
}
}
if (i < n)
x[i] = u / weight[i];
tp = tp + (x[i] * profit[i]);
printf(“\nThe result vector is:- “);
for (i = 0; i < n; i++)
printf(“%f\t”, x[i]);
printf(“\nMaximum profit is:- %f”, tp);
}
int main() {
float weight[20], profit[20], capacity;
int num, i, j;
float ratio[20], temp;
printf(“\nEnter the no. of objects:- “);
scanf(“%d”, &num);
printf(“\nEnter the weights and profits of each object:- “);
for (i = 0; i < num; i++) {
scanf(“%f %f”, &weight[i], &profit[i]);
}
printf(“\nEnter the capacity of knapsack:- “);
scanf(“%f”, &capacity);
for (i = 0; i < num; i++) {
ratio[i] = profit[i] / weight[i];
}
for (i = 0; i < num; i++) {
for (j = i + 1; j < num; j++) {
if (ratio[i] < ratio[j]) {
temp = ratio[j];
ratio[j] = ratio[i];
ratio[i] = temp;
temp = weight[j];
weight[j] = weight[i];
weight[i] = temp;
temp = profit[j];
profit[j] = profit[i];
profit[i] = temp;
}
}
}
knapsack(num, weight, profit, capacity);
return(0);
}
Minimum Cost Spanning Tree using Kruskal’s and Prim’s Algorithm
C Code
#include
#include
#include
int i,j,a,b,u,v,n,ne=1;
int min,mincost=0,cost[9][9],parent[9];
int find(int);
int uni(int,int);
void main(){
printf(“\n\tImplementation of Kruskal’s algorithm\n”);
printf(“\nEnter the no. of vertices:”);
scanf(“%d”,&n);
printf(“\nEnter the cost adjacency matrix:\n”);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf(“%d”,&cost[i][j]);
if(cost[i][j]==0)
cost[i][j]=999;
}}
printf(“The edges of Minimum Cost Spanning Tree are\n”);
while(ne < n)
{
for(i=1,min=999;i<=n;i++){
for(j=1;j <= n;j++)
{
if(cost[i][j] < min)
{
min=cost[i][j];
a=u=i;
b=v=j;
}}}
u=find(u);
v=find(v);
if(uni(u,v)){
printf(“%d edge (%d,%d)=%d\n”,ne++,a,b,min);
mincost +=min;
}
cost[a][b]=cost[b][a]=999;
}
printf(“\n\tMinimum cost = %d\n”,mincost);
getch();
}
int find(int i){
while(parent[i])
i=parent[i];
return i;
}
int uni(int i,int j){
if(i!=j){
parent[j]=i;
return 1;
}
return 0;
}
Longest Common Subsequence Algorithm
C Code
#include
#include
int i, j, m, n, LCS_table[20][20];
char S1[20] = “abcabc”, S2[20] = “aaccbb”, b[20][20];
void lcsAlgo() {
m = strlen(S1);
n = strlen(S2);
for (i = 0; i <= m; i++)
LCS_table[i][0] = 0;
for (i = 0; i <= n; i++)
LCS_table[0][i] = 0;
for (i = 1; i <= m; i++)
for (j = 1; j <= n; j++) {
if (S1[i – 1] == S2[j – 1]) {
LCS_table[i][j] = LCS_table[i – 1][j – 1] + 1;
} else if (LCS_table[i – 1][j] >= LCS_table[i][j – 1]) {
LCS_table[i][j] = LCS_table[i – 1][j];
} else {
LCS_table[i][j] = LCS_table[i][j – 1];
}
}
int index = LCS_table[m][n];
char lcsAlgo[index + 1];
lcsAlgo[index] = ‘\0’;
int i = m, j = n;
while (i > 0 && j > 0) {
if (S1[i – 1] == S2[j – 1]) {
lcsAlgo[index – 1] = S1[i – 1];
i–;
j–;
index–;
}
else if (LCS_table[i – 1][j] > LCS_table[i][j – 1])
i–;
else
j–;
}
printf(“S1 : %s \nS2 : %s \n”, S1, S2);
printf(“LCS: %s”, lcsAlgo);
}
int main() {
lcsAlgo();
printf(“\n”);}
N-Queens Problem using Backtracking
C Code
#define N 4
#include
#include
/* A utility function to print solution */
void printSolution(int board[N][N])
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
printf(” %d “, board[i][j]);
printf(“\n”);
}
}
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; // BACKTRACK
}
}
return false;
}
bool solveNQ()
{
int board[N][N] = { { 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }};
if (solveNQUtil(board, 0) == false) {
printf(“Solution does not exist”);
return false;
}
printSolution(board);
return true;
}
int main()
{
solveNQ();
printf(“\nSEQUENCE IS <3,1,4,2>”);
return 0;
}
Rabin-Karp Algorithm
C Code
#include
#include
#define d 256
void search(char pat[], char txt[], int q)
{
int M = strlen(pat);
int N = strlen(txt);
int i, j;
int p = 0;
int t = 0;
int h = 1;
for (i = 0; i < M – 1; i++)
h = (h * d) % q;
for (i = 0; i < M; i++) {
p = (d * p + pat[i]) % q;
t = (d * t + txt[i]) % q;
}
for (i = 0; i <= N – M; i++) {
if (p == t) {
for (j = 0; j < M; j++) {
if (txt[i + j] != pat[j])
break;
}
if (j == M)
printf(“Pattern found at index %d \n”, i);
}
if (i < N – M) {
t = (d * (t – txt[i] * h) + txt[i + M]) % q;
if (t < 0)
t = (t + q);
}
}
}
int main()
{
char txt[] = “Good Morning”;
char pat[] = “Morning”;
int q = 101;
search(pat, txt, q);
return 0;
}