← All source

C — quicksort.c

gcc -O2 -std=c11 -o quicksort quicksort.c

./quicksort

wsl.exe -d Ubuntu -- bash -c "cd '/mnt/c/Users/granite/Documents/DSU/Algorithms 482/3/HW3/c' && gcc -O2 -std=c11 -o quicksort quicksort.c && ./quicksort"

/*
 * Randomized Quicksort timing harness — CSC 482 HW3 (Language Comparison)
 *
 * Algorithm: CLRS RANDOMIZED-QUICKSORT / RANDOMIZED-PARTITION (Ch. 5).
 * At every partition step the pivot index is chosen uniformly at random
 * from the current subarray range, swapped into the last position, and
 * then a standard Lomuto partition is run around it. In-place, no
 * library sort function is used.
 *
 * No external code used — original implementation based on CLRS
 * RANDOMIZED-QUICKSORT pseudocode.
 *
 * Build:  gcc -O2 -std=c11 -o quicksort quicksort.c
 * Run:    ./quicksort
 */

#define _POSIX_C_SOURCE 199309L
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/* Swap two ints. */
static void swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

/*
 * Lomuto partition around arr[hi] as the pivot. Returns the final
 * index of the pivot after partitioning.
 */
static int partition(int arr[], int lo, int hi) {
    int pivot = arr[hi];
    int i = lo - 1;
    for (int j = lo; j < hi; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[hi]);
    return i + 1;
}

/*
 * RANDOMIZED-PARTITION: choose a pivot index uniformly at random from
 * [lo, hi], swap it into the last position, then partition normally.
 */
static int randomized_partition(int arr[], int lo, int hi) {
    int range = hi - lo + 1;
    int r = lo + (rand() % range);
    swap(&arr[r], &arr[hi]);
    return partition(arr, lo, hi);
}

/* RANDOMIZED-QUICKSORT: recursive in-place randomized quicksort. */
static void randomized_quicksort(int arr[], int lo, int hi) {
    if (lo < hi) {
        int p = randomized_partition(arr, lo, hi);
        randomized_quicksort(arr, lo, p - 1);
        randomized_quicksort(arr, p + 1, hi);
    }
}

/* Fill arr[0..n-1] with random ints in [0, 1000000). Not timed. */
static void generate_random_array(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        arr[i] = rand() % 1000000;
    }
}

int main(void) {
    srand((unsigned int)time(NULL));

    FILE *csv = fopen("../results/c.csv", "w");
    if (csv == NULL) {
        fprintf(stderr, "Error: could not open ../results/c.csv for writing\n");
        return 1;
    }
    fprintf(csv, "n,time_seconds\n");
    fflush(csv);

    printf("n,time_seconds\n");

    long n = 1000;
    int iterations = 0;
    const int MAX_ITERATIONS = 25;
    const double MAX_SECONDS = 4.0;
    const long MAX_N = 200000000L;

    while (1) {
        int *arr = (int *)malloc((size_t)n * sizeof(int));
        if (arr == NULL) {
            fprintf(stderr, "Error: malloc failed for n=%ld\n", n);
            break;
        }

        generate_random_array(arr, (int)n);

        struct timespec start, end;
        clock_gettime(CLOCK_MONOTONIC, &start);
        randomized_quicksort(arr, 0, (int)n - 1);
        clock_gettime(CLOCK_MONOTONIC, &end);

        double elapsed = (end.tv_sec - start.tv_sec) +
                          (end.tv_nsec - start.tv_nsec) / 1e9;

        free(arr);

        iterations++;
        printf("%ld,%.6f\n", n, elapsed);
        fprintf(csv, "%ld,%.6f\n", n, elapsed);
        fflush(csv);

        if (elapsed > MAX_SECONDS) {
            printf("Stopping: iteration exceeded %.1fs\n", MAX_SECONDS);
            break;
        }
        if (iterations >= MAX_ITERATIONS) {
            printf("Stopping: reached %d iterations\n", MAX_ITERATIONS);
            break;
        }
        if (n * 2 > MAX_N) {
            printf("Stopping: next n would exceed %ld\n", MAX_N);
            break;
        }

        n *= 2;
    }

    fclose(csv);
    return 0;
}

Read C report