popo

bubblesort,insertionsort,selectionsort.****

#include <stdio.h>

// Function prototypes
void bubble_sort(int a[], int n);
void selection_sort(int a[], int n);
void insertion_sort(int a[], int n);
void display(int arr[], int size);

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

do {
    printf("\nEnter number of elements to sort: ");
    scanf("%d", &n);
    int arr[n];

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

    printf("\nSelect the desired option:");
    printf("\n1. Bubble Sort\n2. Selection Sort\n3. Insertion Sort\n4. Exit the Program.\n");
    printf("\nEnter your Choice: ");
    scanf("%d", &ch);

    switch (ch) {
        case 1:
            bubble_sort(arr, n);
            break;
        case 2:
            selection_sort(arr, n);
            break;
        case 3:
            insertion_sort(arr, n);
            break;
        case 4:
            printf("Exiting the program.\n");
            return 0;
        default:
            printf("\nInvalid Choice\n");
    }

    printf("Sorted Array: ");
    display(arr, n);
} while (ch != 4);

return 0;

}

void bubble_sort(int arr[], int n) {
int i, j, temp;
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}

void selection_sort(int arr[], int n) {
int i, j, temp;
for (i = 0; i < n - 1; i++) {
int min_idx = i;
for (j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}

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

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

MergeSort:

#include <stdio.h>

// Merge function to merge two sorted subarrays
void merge(int a[], int p, int q, int r) {
int n1 = q - p + 1;
int n2 = r - q;

int L[n1], R[n2]; // Temporary arrays to hold the left and right subarrays

// Copy data to temporary arrays L[] and R[]
for (int i = 0; i < n1; i++)
    L[i] = a[p + i];
for (int j = 0; j < n2; j++)
    R[j] = a[q + 1 + j];

// Merge the temporary arrays back into a[]
int i = 0, j = 0, k = p;
while (i < n1 && j < n2) {
    if (L[i] <= R[j]) {
        a[k] = L[i];
        i++;
    } else {
        a[k] = R[j];
        j++;
    }
    k++;
}

// Copy the remaining elements of L[], if any
while (i < n1) {
    a[k] = L[i];
    i++;
    k++;
}

// Copy the remaining elements of R[], if any
while (j < n2) {
    a[k] = R[j];
    j++;
    k++;
}

}

// Merge sort function
void mergeSort(int a[], int p, int r) {
if (p < r) {
int q = (p + r) / 2;
mergeSort(a, p, q); // Sort the left half
mergeSort(a, q + 1, r); // Sort the right half
merge(a, p, q, r); // Merge the sorted halves
}
}

// Function to print the array
void printArray(int a[], int n) {
for (int i = 0; i < n; i++)
printf("%d ", a[i]);
printf("\n");
}

// Main function
int main() {
int n;
printf("Enter number of elements to sort: ");
scanf("%d", &n);
int a[n];
printf("Enter the elements: ");
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);

printf("Before sorting, array elements are:\n");
printArray(a, n);

mergeSort(a, 0, n - 1); // Call merge sort

printf("After sorting, array elements are:\n");
printArray(a, n);

return 0;

}

knapsack:

#include<stdio.h>

// Function to find the maximum of two integers
int max(int a, int b) {
if(a > b)
return a;
else
return b;
}

// Function to solve the knapsack problem
int knapsack(int W, int w[], int v[], int n) {
int i, k;
int B[n+1][W+1];

// Initialize the base case values
for (i = 0; i <= n; i++) {
    for (k = 0; k <= W; k++) {
        if (i == 0 || k == 0) {
            B[i][k] = 0;
        } else if (w[i-1] <= k) {
            B[i][k] = max(v[i-1] + B[i-1][k-w[i-1]], B[i-1][k]);
        } else {
            B[i][k] = B[i-1][k];
        }
    }
}

// Return the maximum profit
return B[n][W];

}

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

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

// Arrays to store values and weights of items
int v[n], w[n];

// Input the values and weights of items
printf("Enter value and weight of items: \n");
for (i = 0; i < n; i++) {
    scanf("%d %d", &v[i], &w[i]);
}

// Input the maximum weight that the knapsack can hold
printf("Enter maximum weight that the knapsack can hold: \n");
scanf("%d", &W);

// Calculate and output the maximum profit
int profit = knapsack(W, w, v, n);
printf("Maximum Profit made by the thief: %d\n", profit);

return 0;

}

Quicksort:
#include <stdio.h>

int partition(int a[], int p, int r) {
int x = a[r];
int i = p - 1;
int j, temp;
for (j = p; j <= r - 1; j++) {
if (a[j] <= x) {
i = i + 1;
// Swap a[i] and a[j]
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
// Swap a[i+1] and a[r]
temp = a[i + 1];
a[i + 1] = a[r];
a[r] = temp;
return i + 1;
}

void quick_sort(int a[], int p, int r) {
if (p < r) {
int q = partition(a, p, r);
quick_sort(a, p, q - 1);
quick_sort(a, q + 1, r);
}
}

void print_array(int a[], int n) {
for (int i = 0; i < n; i++) {
printf("\t%d", a[i]);
}
printf("\n");
}

int main() {
int i, n;
printf("Enter number of elements to sort: ");
scanf("%d", &n);
int a[n];
printf("Enter elements to sort: ");
for (i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
printf("Before sorting, array elements are: \n");
print_array(a, n);
quick_sort(a, 0, n - 1);
printf("After sorting, array elements are: \n");
print_array(a, n);
return 0;
}

Prims:
#include <stdio.h>
#include <limits.h>

#define MAX_SIZE 10

// Function to extract the vertex with the minimum key from Q
int Extract_min(int Q[], int key[], int n) {
int min_key = INT_MAX;
int min_vertex = -1;

for (int i = 0; i < n; i++) {
    if (Q[i] && key[i] < min_key) {
        min_key = key[i];
        min_vertex = i;
    }
}

Q[min_vertex] = 0; // Mark the vertex as visited (remove from Q)
return min_vertex;

}

// Function to implement Prim's algorithm and calculate the MST cost
int MST_Prim(int G[MAX_SIZE][MAX_SIZE], int r, int n) {
int key[MAX_SIZE]; // Array to store key values
int parent[MAX_SIZE]; // Array to store parent vertices
int Q[MAX_SIZE]; // Array to keep track of vertices in Q

// Initialize key values to infinity and parent values to nil
for (int i = 0; i < n; i++) {
    key[i] = INT_MAX;
    parent[i] = -1;
    Q[i] = 1; // All vertices are initially in Q
}

key[r] = 0; // Start with the root vertex r

int total_cost = 0; // Initialize total cost of MST

while (1) {
    int u = Extract_min(Q, key, n); // Extract vertex with minimum key
    
    if (u == -1) // If no vertex left in Q
        break;
    
    for (int v = 0; v < n; v++) {
        if (G[u][v] > 0 && Q[v] && G[u][v] < key[v]) {
            parent[v] = u;
            key[v] = G[u][v]; // Update key with the weight of the edge
        }
    }
}

// Calculate and print the MST
printf("Edge   Weight\n");
for (int i = 1; i < n; i++) {
    if (parent[i] != -1) {
        printf("%d - %d    %d\n", parent[i], i, G[parent[i]][i]);
        total_cost += G[parent[i]][i]; // Accumulate edge weight to total cost
    }
}

return total_cost; // Return the total cost of the MST

}

int main() {
int n, r;
int G[MAX_SIZE][MAX_SIZE];

printf("Enter the number of vertices (<= %d): ", MAX_SIZE);
scanf("%d", &n);

printf("Enter the adjacency matrix for the graph (%dx%d):\n", n, n);
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        scanf("%d", &G[i][j]);
    }
}

printf("Enter the root vertex (0 to %d): ", n - 1);
scanf("%d", &r);

int min_cost = MST_Prim(G, r, n);

printf("Minimum Cost of MST: %d\n", min_cost);

return 0;

}