quicksort

quicksort.c

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

#define LENGTH(arr) (int) (sizeof(arr) / sizeof(arr[0]))

// helper function for swapping two values in an array based on their indicies
void swap(int *arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

/* 
    quicksort implementation that uses two indices as pivots to swap based on their relative equality to the randomized pivot
    the implementation is recursive, and splits the lists generally in half until sorted
    given maximum transitivity and the pivots are the median, the algorithm runs in O(n log n) time
*/
void quicksort(int* arr, int start, int end) {
    int n = end - start;

    // list is sorted, break from recursion
    if (n <= 0) return;

    // choose random element within array to pivot from (on average it will be the median)
    int pivot_index = rand() % (end + 1 - start) + start;
    int pivot       = arr[pivot_index];

    // start pivot at both ends of array
    int pivot_l = start, pivot_r = end;

    // loop until the pivots overlap in the middle
    while (pivot_l <= pivot_r) {
        // move both pivots towards center
        if (arr[pivot_l] < pivot) pivot_l++;
        else if (arr[pivot_r] > pivot) pivot_r--;
        else {
            // if both pivots have stopped, swap elements in the wrong place and continue pivot
            swap(arr, pivot_l++, pivot_r--);
        }
    }

    // recurse from both ends
    quicksort(arr, start, pivot_r);
    quicksort(arr, pivot_l, end);
}

int main() {
    srand(time(NULL));
    int list[10000] = {};
    for (int i = 0; i < 10000; i++) {
        list[i] = rand() % (10000 + 1);
    }
    
    printf("UNSORTED: ");
    for (int i = 0; i < LENGTH(list); i++) {printf("%d ", list[i]);} puts("");

    clock_t begin = clock();

    quicksort(list, 0, LENGTH(list) - 1);

    clock_t end = clock();
    double time_spent = (double)(end - begin) / CLOCKS_PER_SEC;

    printf("\nSORTED: ");
    for (int i = 0; i < LENGTH(list); i++) {printf("%d ", list[i]);} puts("");

    printf("\n\n\nEXECUTION TOOK %lf ms\n", time_spent * 1000);
}