//------------------------SELECTION SORT------------------------//


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

void selection_sort(int arr[], int n) {
    int i, j, min_idx, temp;
    for(i = 0; i < n - 1; i++) {
        min_idx = i;
        for(j = i + 1; j < n; j++) {
            if(arr[j] < arr[min_idx])
                min_idx = j;
        }
        if(min_idx != i) {
            temp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = temp;
        }
    }
}
void printArray(int arr[], int size) {
    int i;
    for(i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
int main(void) {
    int i, n;
    clock_t start, end;
    double cpu_time_used;
    printf("Enter the value of n: ");
    scanf("%d", &n);
    int arr[n];

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

    start = clock();
    selection_sort(arr, n);
    end = clock();
    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    printf("Sorted array:\n");
    printArray(arr, n);
    printf("Execution time: %f seconds\n", cpu_time_used);
    return 0;
}


//------------------------QUICK SORT------------------------//


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

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

int partition(int arr[], int low, int high) {
    int pivot = arr[low];
    int i =low;
    int j = high;
    while(i < j) {
        while(arr[i] <= pivot && i <= high - 1)
            i++;
        while(arr[j] > pivot && j >= low + 1)
            j--;
        if(i < j)
            swap(&arr[i], &arr[j]);
    }
    swap(&arr[low], &arr[j]);
    return j;
}

void quickSort(int arr[], int low, int high) {
    if(low < high) {
        int partitionIndex = partition(arr, low, high);
        quickSort(arr, low, partitionIndex - 1);
        quickSort(arr, partitionIndex + 1, high);
    }
}

int main(void) {
    int i, n;
    clock_t start, end;
    double cpu_time_used;
    printf("Enter the value of n: ");
    scanf("%d", &n);
    int arr[n];
    for(i = 0; i < n; i++) {
        arr[i] = rand() % 1000;
        printf("%d", arr[i]);
    }
    start = clock();
    quickSort(arr, 0, n - 1);
    end = clock();
    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    printf("\nSorted array: ");
    for(i = 0; i < n; i++)
        printf("%d", arr[i]);

    printf("\nExecution time: %f seconds\n", cpu_time_used);
    return 0;
}


//------------------------MERGE SORT------------------------//


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

void merge(int arr[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    int L[n1], R[n2];
    for(i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for(j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    i = 0, j = 0, k = l;

    while(i < n1 && j < n2) {
        if(L[i] <= R[j]) {
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
        }
    }

    while(i < n1)
        arr[k++] = L[i++];
    while(j < n2)
        arr[k++] = R[j++];
}

void mergeSort(int arr[], int l, int r) {
    if(l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

int main(void) {
    int i, n;
    clock_t start, end;
    double cpu_time_used;
    printf("Enter the value of n: ");
    scanf("%d", &n);
    int arr[n];
    for(i = 0; i < n; i++) {
        arr[i] = rand() % 1000;
        printf("%d ", arr[i]);
    }
    start = clock();
    mergeSort(arr, 0, n - 1);
    end = clock();
    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    printf("\nSorted array: ");
    for(i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\nExecution time: %f seconds\n", cpu_time_used);
    return 0;
}


//------------------------PRIM'S ALGORITHM------------------------//


#include <stdio.h>

void my_prim(int adj[][10], int N) {
    int i, j, nv, min, min_cost = 0, u = 0, v = 0;
    int visit[10] = {0};
    visit[0] = 1;
    nv = 1;
    while (nv < N) {
        min = 999;
        for (i = 0; i < N; i++) {
            if (visit[i] == 1) {
                for (j = 0; j < N; j++) {
                    if (!visit[j] && adj[i][j] < min) {
                        min = adj[i][j];
                        u = i;
                        v = j;
                        printf("\nConsidering edge (%d, %d) with weight %d", i, j, adj[i][j]);
                    }
                }
            }
        }
        adj[u][v] = 999;
        adj[v][u] = 999;

        if (visit[u] == 1 && visit[v] == 0) {
            visit[v] = 1;
            min_cost += min;
            nv++;
            printf("\nEdge %d --> %d : (%d)\n", u, v, min);
        }
    }
    printf("Minimum cost : %d\n", min_cost);
}

int main() {
    int adj[10][10], N, i, j;
    printf("Enter number of nodes in the graph: ");
    scanf("%d", &N);

    printf("Enter the adjacency matrix\n");
    printf("Enter 0 for no connection and weights for connection\n");

    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
            scanf("%d", &adj[i][j]);
            if (adj[i][j] == 0) {
                adj[i][j] = 999;
            }
        }
    }
    my_prim(adj, N);
    return 0;
}


//------------------------KRUSKAL'S ALGORITHM------------------------//


#include <stdio.h>

int ne = 1, min_cost = 0;

int main(void) {
    int n, i, j, min, a, b, u, v, cost[20][20], parent[20];
    printf("Enter the number of vertices: ");
    scanf("%d", &n);
    printf("\nEnter the cost matrix: ");
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            scanf("%d", &cost[i][j]);
    for (i = 1; i <= n; i++)
        parent[i] = 0;
    printf("\nThe edges of spanning tree are\n");

    while (ne < n) {
        min = 999;
        for (i = 1; i <= n; i++) {
            for (j = 1; j <= n; j++) {
                if (cost[i][j] < min && cost[i][j] != 0) {
                    min = cost[i][j];
                    a = u = i;
                    b = v = j;
                }
            }
        }
        while (parent[u]) u = parent[u];
        while (parent[v]) v = parent[v];
        if (u != v) {
            printf("Edge %d\t(%d --> %d) = %d\n", ne++, a, b, min);
            min_cost += min;
            parent[v] = u;
        }
        cost[a][b] = cost[b][a] = 999;
    }
    printf("\nMinimum cost = %d\n", min_cost);
}


//------------------------DIJKSTRA'S ALGORITHM------------------------//


#include <stdio.h>
#define infinity 999

void dij(int n, int v, int cost[10][10], int dist[10]) {
    int i, u, count, w, flag[10], min;
    for (i = 1; i <= n; i++) {
        flag[i] = 0;
        dist[i] = cost[v][i];
    }
    count = 2;
    while (count <= n) {
        min = infinity;
        for (w = 1; w <= n; w++) {
            if (dist[w] < min && !flag[w]) {
                min = dist[w];
                u = w;
            }
        }
        flag[u] = 1;
        count++;
        for (w = 1; w <= n; w++) {
            if ((dist[u] + cost[u][w] < dist[w]) && !flag[w])
                dist[w] = dist[u] + cost[u][w];
        }
    }
}

int main(void) {
    int n, v, i, j, cost[10][10], dist[10];
    printf("\nEnter the number of nodes: ");
    scanf("%d", &n);

    printf("Enter the cost 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] = infinity;
        }
    }
    printf("\nEnter the source vertex: ");
    scanf("%d", &v);
    dij(n, v, cost, dist);
    printf("\nShortest Path:\n");
    for (i = 1; i <= n; i++) {
        if (i != v)
            printf("%d --> %d, cost = %d\n", v, i, dist[i]);
    }
}