ADA Program 10

 

 10. Quick Sort

/*Quick Sort*/

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

int partition(int a[], int low, int high) {
    int pivot = a[high];
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (a[j] <= pivot) {
            i++;
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }

    int temp = a[i + 1];
    a[i + 1] = a[high];
    a[high] = temp;

    return i + 1;
}

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

int main() {
    int n, i, num_points = 0;
    clock_t start, end;
    double time_taken;

    double n_values[7], times[7];

    srand(time(NULL));

    FILE *fp = fopen("data.txt", "w");
    if (fp == NULL) {
        printf("Error opening file\n");
        return 1;
    }

    printf("Running Quick Sort and recording time...\n");

    for (n = 5000; n <= 30000; n += 5000) {
        int *arr = (int *)malloc(n * sizeof(int));

        for (i = 0; i < n; i++)
            arr[i] = rand() % 100000;

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

        time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;

        printf("N = %d, Time = %lf seconds\n", n, time_taken);
        fprintf(fp, "%d %lf\n", n, time_taken);

        n_values[num_points] = n;
        times[num_points] = time_taken;
        num_points++;

        free(arr);
    }

    fclose(fp);

    double sum_n = 0, sum_t = 0, sum_nt = 0, sum_n2 = 0;

    for (i = 0; i < num_points; i++) {
        sum_n += n_values[i];
        sum_t += times[i];
        sum_nt += n_values[i] * times[i];
        sum_n2 += n_values[i] * n_values[i];
    }

    double m = (num_points * sum_nt - sum_n * sum_t) / (num_points * sum_n2 - sum_n * sum_n);
    double c = (sum_t - m * sum_n) / num_points;

    printf("\n--- Linear Fit: y = %.1f*x + %.4f ---\n", m*1000, c);

    printf("\n--- Time Complexity Analysis ---\n");

    double total_n_ratio = 0, total_time_ratio = 0;
    int ratio_count = 0;

    for (i = 1; i < num_points; i++) {
        double n_ratio = n_values[i] / n_values[i-1];
        double time_ratio = times[i] / times[i-1];

        printf("N: %d->%d, Time Ratio: %.3fx\n", (int)n_values[i-1], (int)n_values[i], time_ratio);

        total_n_ratio += n_ratio;
        total_time_ratio += time_ratio;
        ratio_count++;
    }

    printf("\nAverage ratios: N=%.1fx, Time=%.3fx\n",
           total_n_ratio/ratio_count, total_time_ratio/ratio_count);

    FILE *gp = popen("gnuplot -persist", "w");
    if (gp) {
        fprintf(gp, "plot 'data.txt' using 1:2 with linespoints\n");
        pclose(gp);
    }

    return 0;
}