ADA Program 9

Program 9 — Selection Sort with Time Complexity

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

void selectionSort(int a[], int n) {
    int i, j, minIndex, temp;
    for (i = 0; i < n - 1; i++) {
        minIndex = i;
        for (j = i + 1; j < n; j++) {
            if (a[j] < a[minIndex])
                minIndex = j;
        }
        temp = a[i];
        a[i] = a[minIndex];
        a[minIndex] = temp;
    }
}

int main() {
    int n, i;
    clock_t start, end;
    double time_taken;
    FILE *fp = fopen("data.txt", "w");
    srand(0);
    printf("Running Selection Sort and recording time...\n\n");
    
    for (n = 5000; n <= 30000; n += 5000) {
        int runs = 3;
        double total = 0.0;
        for (int r = 0; r < runs; r++) {
            int *arr = (int *)malloc(n * sizeof(int));
            for (i = 0; i < n; i++)
                arr[i] = rand() % 100000;
            start = clock();
            selectionSort(arr, n);
            end = clock();
            total = total+(double)(end - start) / CLOCKS_PER_SEC;
            free(arr);
        }
        time_taken = total / runs;
        printf("N = %d, Time = %lf seconds\n", n, time_taken);
        fprintf(fp, "%d %lf\n", n, time_taken);
    }
    fclose(fp);
    
    FILE *fp2 = fopen("data.txt", "r");
    int nArr[100];
    double t[100];
    int count = 0;
    while (fscanf(fp2, "%d %lf", &nArr[count], &t[count]) == 2)
        count++;
    fclose(fp2);
    
    double s = 0;
    for (int k = 0; k < count; k++) {
        double r = nArr[k];
        s= s+t[k] / (r * r);
    }
    double avg_n2 = s / count;
    printf("O(n²) normalized: %.6f μs/el² (stable → confirmed O(n²))\n", avg_n2 * 1e6);
    printf("\nTIME COMPLEXITY ANALYSIS \n");
    printf("TIME COMPLEXITY: O(n^2)\n");
    double scale = 1000000;
    printf("O(n^2): %.4f\n", avg_n2*scale);
    
    FILE *gp = popen("gnuplot -persistent", "w");
    if (gp) {
        fprintf(gp, "set title 'Selection Sort: Time vs Input Size'\n");
        fprintf(gp, "set xlabel 'N'\n");
        fprintf(gp, "set ylabel 'Time (seconds)'\n");
        fprintf(gp, "set grid\n");
        fprintf(gp, "plot 'data.txt' using 1:2 with linespoints lw 2 pt 7 title 'Actual Time'\n");
        pclose(gp);
    } else {
        printf("Gnuplot not found\n");
    }
    return 0;
}

Installing Gnuplot (For Graphs)
10. Install Gnuplot
Type:
sudo apt install gnuplot
Press Enter.
If asked for password, type:
impact
and press Enter.