We've talked a lot about Big O notation and theoretical complexity in previous lessons, but as an engineer, I've found that theory only sticks when you actually see the numbers on your own machine. There is a massive difference between knowing that Quick Sort is $O(n \log n)$ and actually watching a Bubble Sort struggle for three seconds while Quick Sort finishes in a blink.

Setting the Stage with Random Data

To get a real benchmark, we can't use a tiny array of five elements. We need enough data to make the CPU actually work. I'm going to write a quick helper function to fill an array with random integers. I'll use rand() from stdlib.h. It's not cryptographically secure, but for a benchmark, it's perfect.

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

void fill_array(int *arr, int size) {
    for (int i = 0; i < size; i++) {
        arr[i] = rand() % 10000; // Random numbers between 0 and 9999
    }
}

Capturing the Clock

In C, the standard way to measure elapsed time for a specific block of code is using clock() from time.h. It returns the number of clock ticks elapsed since the program started. To get the actual time in seconds, we divide the difference between the start and end ticks by CLOCKS_PER_SEC. I prefer using double for the result because the difference in fast algorithms is often a fraction of a second.

double measure_time(void (*sort_func)(int*, int), int *arr, int size) {
    clock_t start = clock();
    sort_func(arr, size);
    clock_t end = clock();
    return (double)(end - start) / CLOCKS_PER_SEC;
}

The "Already Sorted" Trap

Here is where I almost messed up. In my first draft of this code, I passed the same array to Bubble Sort and then immediately passed that same array to Quick Sort. I ran the program and Quick Sort clocked in at 0.000 seconds. I thought I'd discovered a miracle algorithm until I realized the obvious: Bubble Sort had already sorted the array. Quick Sort wasn't sorting random data; it was sorting a perfectly ordered list.

To fix this, I need to make sure each algorithm gets a fresh, identical copy of the random data. I'll use memcpy from string.h to clone the original "master" array before passing it to the timing function.

#include <string.h>

// Inside main...
int *master_array = malloc(size * sizeof(int));
int *work_array = malloc(size * sizeof(int));
fill_array(master_array, size);

// Test Bubble Sort
memcpy(work_array, master_array, size * sizeof(int));
double bubble_time = measure_time(bubble_sort, work_array, size);

// Test Quick Sort
memcpy(work_array, master_array, size * sizeof(int));
double quick_time = measure_time(quick_sort, work_array, size);

Putting it All Together

Now we just combine the logic. I'll use an array size of 10,000. For some of you on very fast machines, you might need to bump this to 20,000 or 50,000 to see Bubble Sort really start to sweat. I'm keeping it at 10k for now so the program doesn't hang for too long during your first run.

int main() {
    int size = 10000;
    int *master_array = malloc(size * sizeof(int));
    int *work_array = malloc(size * sizeof(int));
    
    srand(time(NULL));
    fill_array(master_array, size);

    memcpy(work_array, master_array, size * sizeof(int));
    double t1 = measure_time(bubble_sort, work_array, size);
    printf("Bubble Sort took: %f seconds\n", t1);

    memcpy(work_array, master_array, size * sizeof(int));
    double t2 = measure_time(quick_sort, work_array, size);
    printf("Quick Sort took: %f seconds\n", t2);

    free(master_array);
    free(work_array);
    return 0;
}

📋 Practical Task

Exercise: Stress-Testing the Scaling Gap

Now it's your turn to see the "exponential wall." You are going to build a benchmarking tool that doesn't just test one size, but compares how these algorithms scale as the input grows.

Your Requirements:

• Implement a bubble_sort and a quick_sort function (or use implementations you've written in previous lessons).
• Create a loop that runs the benchmark for three different array sizes: 1,000, 5,000, and 15,000 elements.
• For each size, generate a random array and measure the execution time for both algorithms.
• Print the results in a table format, like this:

  Size    | Bubble Sort | Quick Sort
          -------------------------------
          1000    | 0.012s      | 0.001s
          5000    | 0.310s      | 0.005s
          ...

• Ensure you are using memcpy to provide the exact same random data to both algorithms for every size iteration.