recursion - QuickSort implementation in C seems to skip some runs randomly

Question

i was in the process on implementing a QuickSort in C as an exercise. I think I'm in a pretty good spot by I'm puzzle by why my code seems to sometimes not call the first call of QuickSort.

main.c

#include <stdlib.h>

#include <time.h>

#include "quicksort.h"
#include "utils.h"

//----------------------------------------

void main(int argc, char* argv[]) {
    unsigned int SIZE;
    int* numbers;
    
    if (argc > 1) {
        SIZE = argc-1;
        numbers = (int*) malloc(sizeof(unsigned int) * SIZE);
        if (numbers == NULL) { exit(1); }
        
        for (unsigned int i = 0; i < SIZE; i++) {
            numbers[i] = atoi(argv[i+1]);
        }
    } else {
        SIZE = 100;
        numbers = (int*) malloc(sizeof(unsigned int) * SIZE);
        if (numbers == NULL) { exit(1); }
        
        srandom(time(NULL));
        
        for (int i = 0; i < SIZE; i++) {
            numbers[i] = (random() % 60000) - 30000;    // Random numbers between (-30000, 30000)
        }
    }
    printf("Array filled!
");

    quicksort(numbers, 0, SIZE-1);
    printf("%s
", isSorted(numbers, SIZE) ? "Sorted!" : "Not sorted!");

    free(numbers);
    printf("Memory released
");

    exit(0);
}

quicksort.c

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

#include "quicksort.h"
#include "utils.h"

//----------------------------------------

unsigned int partition(int* const array, const unsigned int low, const unsigned int high) {
    const int pivot = array[(unsigned int)((low + high)/2)];
    unsigned int i = low;
    unsigned int j = high;
    
    while (1) {
        while (array[i] < pivot) { i += 1; }
        while (pivot < array[j]) { j += -1; }
        if (i == j) { return i; }
        swap(array+i, array+j);
    }
}

void quicksort(int* const array, const unsigned int low, const unsigned int high) {
    unsigned int pivot = partition(array, low, high);
    printf(".");

    // We only want to recurse if there at least two elements to order.
    //  Otherwise we simply don't recurse on the subarray because one element is in order with itself.
    if (low+1 < pivot) { quicksort(array, low, pivot-1); }
    if (pivot+1 < high) { quicksort(array, pivot+1, high); }
}

utils.c

#include <stdio.h>

#include "utils.h"

//----------------------------------------

void print_array(int* const array, const unsigned int size) {
    printf("%d", array[0]);
    for (unsigned int i = 1; i < size; i++) {
        printf(" %d", array[i]);
    }
    printf("
");
}

void swap(int* a, int* b) {
    const int temp = *a;
    *a = *b;
    *b = temp;
}

unsigned short isSorted(int* const array, const unsigned int size) {
    for (int i = 0; i < size-1; i++) {
        if (array[i] > array [i+1]) {
            return 0;
        }
    }
    
    return 1;
}

The issue is that sometimes the first call to quicksort() is ran and I can see the dots of each call on my terminal. Sometimes it gets stuck and I can't see even one single dot.

I'm really puzzled because it's such a random error I don't even know how to start debugging it.

This is one particular instance that always get stuck.

./main -22167 -8962 -12961 -8232 -1118 -22237 -7872 -8654 15744 -28388 -12088 402 17865 3515 -10380 -1672 -6731 24435 14161 14906 -21791 -9593 -2111 -1323 6065 1955 -23011 17216 29229 -8988 21034 -22938 -11598 14425 -24818 -6364 -1460 -2689 14983 -15716 -24725 9247 -8962 23141 -17238 -12989 27821 -17616 -18554 11982 27290 26008 -27611 -28468 -5315 -15194 -20161 -21974 -27977 -20932 -24610 -591 22483 -29856 20186 27665 -6219 25078 -28672 15116 -20638 -23396 -5637 -23247 6097 -16523 -6236 3918 -4139 5210 22252 29504 -22430 994 7388 -21393 15800 17227 -13367 -5825 2647 28375 -64 -28518 28520 26474 5500 28653 21552 6828

Answer 1

There was quite a few errors in the partition scheme and in the quicksort.

Correct version: quicksort.c

unsigned int partition(int* const array, const unsigned int low, const unsigned int high) {
    const int pivot = array[(unsigned int)((low + high)/2)];
    long i = (long)low - 1;
    long j = (long)high + 1;
    
    while (1) {
        do { i += 1; } while (array[i] < pivot);
        do { j += -1; } while (pivot < array[j]);
        if (i >= j) { return j; }
        swap(array+i, array+j);
    }
}

void quicksort(int* const array, const unsigned int low, const unsigned int high) {
    if (low < high) {
        unsigned int pivot = partition(array, low, high);

        quicksort(array, low, pivot);
        quicksort(array, pivot+1, high);
    }
}