Sorting and Graph Algorithms in C

Posted on Dec 10, 2024 in Computers

Sorting Algorithms

Quick Sort

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

void quickSort(int arr[], int low, int high);
int partition(int arr[], int low, int high);

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

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return (i + 1);
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    clock_t start = clock();
    quickSort(arr, 0, n - 1);
    clock_t end = clock();

    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\nTime taken: %f seconds\n", ((double)(end - start)) / CLOCKS_PER_SEC);
    return 0;
}

Merge Sort

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

void merge(int arr[], int l, int m, int r);
void mergeSort(int arr[], int l, int r);

void merge(int arr[], int l, int m, int r) {
    // ... (rest of the merge sort code)
}

void mergeSort(int arr[], int l, int r) {
    // ... (rest of the merge sort code)
}

int main() {
    // ... (rest of the merge sort code)
}

Graph Algorithms

Prim’s Algorithm

// ... (Prim's algorithm code)

Kruskal’s Algorithm

// ... (Kruskal's algorithm code)

Knapsack Problem

// ... (Knapsack problem code)

Dijkstra’s Algorithm

// ... (Dijkstra's algorithm code)