external

Selection sort

#include <stdio.h>

int main() {
    int n, i, j;

    printf("Enter the number of elements: ");
    scanf("%d", &n);

    int arr[n];

    // Input array elements
    printf("Enter %d elements:\n", n);
    for (i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    // Selection Sort logic
    for (i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        // Swap
        int temp = arr[i];
        arr[i] = arr[minIdx];
        arr[minIdx] = temp;
    }

    // Print sorted array
    printf("Sorted array using Selection Sort:\n");
    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }

    return 0;
}

Insertion sort 

#include <stdio.h>

int main() {
    int n, i, j;

    printf("Enter the number of elements: ");
    scanf("%d", &n);

    int arr[n];

    // Input array elements
    printf("Enter %d elements:\n", n);
    for (i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    // Insertion Sort logic
    for (i = 1; i < n; i++) {
        int key = arr[i];
        j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }

    // Print sorted array
    printf("Sorted array using Insertion Sort:\n");
    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }

    return 0;
}

Quick sort

#include <stdio.h>

int main() {
    int n, i, j, pivot, temp;

    printf("Enter number of elements: ");
    scanf("%d", &n);

    int arr[n];

    printf("Enter %d elements:\n", n);
    for (i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    // Basic iterative quick sort using nested loops (not efficient, but basic)
    for (i = 0; i < n - 1; i++) {
        pivot = arr[i];
        for (j = i + 1; j < n; j++) {
            if (arr[j] < pivot) {
                // Swap arr[i] and arr[j]
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                pivot = arr[i]; // Update pivot
            }
        }
    }

    printf("Sorted array using Quick Sort logic (basic):\n");
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);

    return 0;
}

Merge sort

#include <stdio.h>

int main() {
    int n, i, j, k, size, left, mid, right;

    printf("Enter number of elements: ");
    scanf("%d", &n);

    int arr[n], temp[n];

    printf("Enter %d elements:\n", n);
    for (i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    // Bottom-up merge sort using only loops
    for (size = 1; size < n; size = 2 * size) {
        for (left = 0; left < n - 1; left += 2 * size) {
            mid = left + size - 1;
            right = (left + 2 * size - 1 < n - 1) ? (left + 2 * size - 1) : (n - 1);

            i = left;
            j = mid + 1;
            k = left;

            while (i <= mid && j <= right) {
                if (arr[i] <= arr[j]) {
                    temp[k] = arr[i];
                    i++;
                } else {
                    temp[k] = arr[j];
                    j++;
                }
                k++;
            }

            while (i <= mid) {
                temp[k] = arr[i];
                i++;
                k++;
            }

            while (j <= right) {
                temp[k] = arr[j];
                j++;
                k++;
            }

            for (i = left; i <= right; i++) {
                arr[i] = temp[i];
            }
        }
    }

    printf("Sorted array using Merge Sort:\n");
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);

    return 0;
}

Fractional knapsack

#include <stdio.h>

int main() {
    int n, capacity, i, j;
    float totalValue = 0;

    // Read number of items
    printf("Enter number of items: ");
    scanf("%d", &n);

    // Create an array to store value, weight, and value/weight ratio of items
    int value[n], weight[n];
    float ratio[n];

    // Input value and weight for each item
    printf("Enter value and weight for each item:\n");
    for (i = 0; i < n; i++) {
        printf("Item %d:\n", i + 1);
        printf("Value: ");
        scanf("%d", &value[i]);
        printf("Weight: ");
        scanf("%d", &weight[i]);

        // Calculate value/weight ratio for each item
        ratio[i] = (float)value[i] / weight[i];
    }

    // Input the capacity of the knapsack
    printf("Enter capacity of knapsack: ");
    scanf("%d", &capacity);

    // Sort items by value/weight ratio in descending order using bubble sort
    for (i = 0; i < n - 1; i++) {
        for (j = i + 1; j < n; j++) {
            if (ratio[j] > ratio[i]) {
                // Swap value, weight, and ratio if needed
                int tempValue = value[i];
                value[i] = value[j];
                value[j] = tempValue;

                int tempWeight = weight[i];
                weight[i] = weight[j];
                weight[j] = tempWeight;

                float tempRatio = ratio[i];
                ratio[i] = ratio[j];
                ratio[j] = tempRatio;
            }
        }
    }

    // Apply the Greedy method to fill the knapsack
    for (i = 0; i < n && capacity > 0; i++) {
        // If the item can be completely added to the knapsack
        if (weight[i] <= capacity) {
            totalValue += value[i];
            capacity -= weight[i];
        } else {
            // Take the fraction of the item
            totalValue += ratio[i] * capacity;
            capacity = 0;
        }
    }

    // Output the result
    printf("\nMaximum value in Knapsack = %.2f\n", totalValue);

    return 0;
}

0/1 knapsack

#include <stdio.h>

#define MAX_ITEMS 10

int main() {
    int weight[MAX_ITEMS], value[MAX_ITEMS], dp[MAX_ITEMS+1][MAX_ITEMS+1];
    int W, N, i, w;

    // Input number of items and capacity of the knapsack
    printf("Enter the number of items: ");
    scanf("%d", &N);
    printf("Enter the capacity of the knapsack: ");
    scanf("%d", &W);

    // Input the weight and value for each item
    printf("Enter the weight and value of each item:\n");
    for (i = 0; i < N; i++) {
        printf("Item %d - Weight: ", i + 1);
        scanf("%d", &weight[i]);
        printf("Item %d - Value: ", i + 1);
        scanf("%d", &value[i]);
    }

    // Initialize the DP table
    for (i = 0; i <= N; i++) {
        for (w = 0; w <= W; w++) {
            if (i == 0 || w == 0) {
                dp[i][w] = 0;  // If there are no items or knapsack capacity is 0, value is 0
            } else if (weight[i-1] <= w) {
                dp[i][w] = (value[i-1] + dp[i-1][w - weight[i-1]] > dp[i-1][w]) ? 
                           value[i-1] + dp[i-1][w - weight[i-1]] : dp[i-1][w];
            } else {
                dp[i][w] = dp[i-1][w];  // If the item cannot be included
            }
        }
    }

    // Output the maximum value that can be obtained with the given knapsack capacity
    printf("Maximum value that can be obtained: %d\n", dp[N][W]);

    // Output the selected items
    printf("Items included in the knapsack are:\n");
    w = W;
    for (i = N; i > 0 && w > 0; i--) {
        if (dp[i][w] != dp[i-1][w]) {
            printf("Item %d (Weight: %d, Value: %d)\n", i, weight[i-1], value[i-1]);
            w -= weight[i-1];
        }
    }

    return 0;
}

Floyed warshal

#include <stdio.h>

#define MAX_VERTICES 10

int main() {
    int graph[MAX_VERTICES][MAX_VERTICES], dist[MAX_VERTICES][MAX_VERTICES];
    int V, i, j, k;

    // Input number of vertices
    printf("Enter the number of vertices: ");
    scanf("%d", &V);

    // Input adjacency matrix for the graph
    printf("Enter the adjacency matrix (enter 0 if no direct edge exists between two vertices):\n");
    for (i = 0; i < V; i++) {
        for (j = 0; j < V; j++) {
            scanf("%d", &graph[i][j]);
            dist[i][j] = graph[i][j];  // Initialize distance matrix
        }
    }

    // Floyd-Warshall Algorithm: Compute all pairs shortest paths
    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];
                }
            }
        }
    }

    // Output the shortest distances between every pair of vertices
    printf("The shortest distances between every pair of vertices are:\n");
    for (i = 0; i < V; i++) {
        for (j = 0; j < V; j++) {
            if (dist[i][j] == 0 && i != j) {
                printf("INF ");  // No path exists
            } else {
                printf("%d ", dist[i][j]);
            }
        }
        printf("\n");
    }

    return 0;
}

Lcs

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

#define MAX_LENGTH 100

int main() {
    char str1[MAX_LENGTH], str2[MAX_LENGTH];
    int i, j;
    int dp[MAX_LENGTH][MAX_LENGTH];  // DP table for storing LCS lengths

    // Input two strings
    printf("Enter the first string: ");
    scanf("%s", str1);
    printf("Enter the second string: ");
    scanf("%s", str2);

    // Lengths of the two strings
    int len1 = strlen(str1);
    int len2 = strlen(str2);

    // Initialize the DP table
    for (i = 0; i <= len1; i++) {
        for (j = 0; j <= len2; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0;  // If either string is empty, LCS length is 0
            }
        }
    }

    // Fill the DP table based on the LCS relation
    for (i = 1; i <= len1; i++) {
        for (j = 1; j <= len2; j++) {
            if (str1[i - 1] == str2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;  // If characters match, increase LCS length
            } else {
                dp[i][j] = (dp[i - 1][j] > dp[i][j - 1]) ? dp[i - 1][j] : dp[i][j - 1];  // Otherwise, take the maximum of the previous values
            }
        }
    }

    // The length of the LCS is stored in dp[len1][len2]
    printf("The length of Longest Common Subsequence is: %d\n", dp[len1][len2]);

    // To find the actual LCS, we backtrack through the DP table
    int index = dp[len1][len2];  // Length of LCS
    char lcs[index + 1];  // Array to store the LCS string
    lcs[index] = '\0';  // Null-terminate the LCS string

    i = len1;
    j = len2;

    // Backtracking to construct the LCS string
    while (i > 0 && j > 0) {
        if (str1[i - 1] == str2[j - 1]) {
            lcs[index - 1] = str1[i - 1];  // If characters match, it's part of LCS
            i--;
            j--;
            index--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--;  // Move in the direction where the larger value is
        } else {
            j--;
        }
    }

    // Output the Longest Common Subsequence
    printf("The Longest Common Subsequence is: %s\n", lcs);

    return 0;
}

N queen 

#include <stdio.h>

#define MAX_N 10

int main() {
    int n, board[MAX_N][MAX_N], row, col;

    // Input the size of the chessboard (n x n)
    printf("Enter the size of the chessboard (n): ");
    scanf("%d", &n);

    // Initialize the board with all 0s (empty spaces)
    for (row = 0; row < n; row++) {
        for (col = 0; col < n; col++) {
            board[row][col] = 0;
        }
    }

    row = 0; // Start placing queens from the first row
    while (row < n) {
        col = 0;
        while (col < n) {
            // Check if it's safe to place the queen at (row, col)
            int safe = 1;
            for (int i = 0; i < row; i++) {
                // Check column
                if (board[i][col] == 1) {
                    safe = 0;
                    break;
                }
                // Check diagonal (top-left to bottom-right)
                if (col - (row - i) >= 0 && board[i][col - (row - i)] == 1) {
                    safe = 0;
                    break;
                }
                // Check diagonal (top-right to bottom-left)
                if (col + (row - i) < n && board[i][col + (row - i)] == 1) {
                    safe = 0;
                    break;
                }
            }

            if (safe) {
                board[row][col] = 1; // Place the queen
                row++;  // Move to the next row
                break;
            } else {
                col++; // Try next column
            }
        }

        // Backtrack if no safe column was found
        if (col == n) {
            row--; // Move back to the previous row
            while (board[row][col] == 1) {
                board[row][col] = 0;  // Remove the queen
                col--;  // Try previous column
            }
            col++;  // Move to the next column
        }
    }

    // Print the final board with queens placed
    printf("Solution to the N-Queens problem is:\n");
    for (row = 0; row < n; row++) {
        for (col = 0; col < n; col++) {
            if (board[row][col] == 1) {
                printf("Q ");
            } else {
                printf(". ");
            }
        }
        printf("\n");
    }

    return 0;
}

 Sum of subset

#include <stdio.h>

#define MAX_SIZE 10

int main() {
    int arr[MAX_SIZE], subset[MAX_SIZE], n, target, sum = 0;

    // Input the number of elements in the set
    printf("Enter the number of elements in the set: ");
    scanf("%d", &n);

    // Input the elements of the set
    printf("Enter the elements of the set:\n");
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    // Input the target sum
    printf("Enter the target sum: ");
    scanf("%d", &target);

    // Initialize subset array with -1 (no elements included yet)
    for (int i = 0; i < n; i++) {
        subset[i] = -1;
    }

    printf("Subsets with sum %d are:\n", target);

    // Backtracking to find subsets with the target sum
    for (int i = 0; i < (1 << n); i++) {  // Loop through all subsets (2^n possibilities)
        sum = 0;  // Reset sum for this subset

        // Generate the subset by checking which elements are included
        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) {  // Check if the j-th element is included in the subset
                subset[j] = arr[j];  // Include element in the subset
                sum += arr[j];  // Add to the sum
            } else {
                subset[j] = -1;  // Exclude element from the subset
            }
        }

        // If the sum equals the target, print the subset
        if (sum == target) {
            printf("{ ");
            for (int k = 0; k < n; k++) {
                if (subset[k] != -1) {
                    printf("%d ", subset[k]);
                }
            }
            printf("}\n");
        }
    }

    return 0;
}