Quick-sort implementation in C

Question

Goal: I'm trying to implement quick-sort in C.
Problem: This quick-sort implementation for C goes on an infinite loop. I think the partition function is okay, because using test cases, the pivot (which is set to index 0) always moves to the correct location. I don't understand why the quicksort function would not eventually reach the base case.

What might be the problem with this implementation?

# include <stdio.h>

// Swapping algorithm
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Partitioning algorithm
int partition(int *L, int left, int right){
    int pivot = L[0];

    while (right > left) {
            while (L[left] < pivot) {
                    left = left + 1;
            }
            while (L[right] > pivot) {
                    right = right - 1;
            }
            swap(&L[left], &L[right]);
    }
    swap(&pivot, &L[left]);
    return left;
}

// Quicksort recursion
void quicksort(int *L, int start, int end) {
    if (start >= end) {
            return;
    }
    else {
            int splitPoint = partition(L, start, end);
            quicksort(L, start, splitPoint-1);
            quicksort(L, splitPoint+1, end);
    }
}

int main() {
    int myList[] = {12, 43, -16, 0, 2, 5, 1, 13, 2, 2, -1};
    printf("UNSORTED LIST\n");
    int *pointer = myList;
    for (int i = 0; i < 10; i++) {
            printf("%d ", *(pointer+i));
    }
    quicksort(myList, 0, 9);
    printf("\nSORTED LIST\n");
    for (int i = 0; i < 10; i++) {
            printf("%d ", *(pointer+i));
    }
    printf("\n");
}

Answer 1

The initial pivot choice should be L[left] not L[0], shouldn't it? However, that's not the only problem in the partition function.

This code works:

#include <stdio.h>

// Swapping algorithm
static inline
void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

static void dump_list(const char *tag, int *ptr, int left, int right)
{
    printf("%15s [%d..%d]: ", tag, left, right);
    for (int i = left; i <= right; i++)
        printf(" %3d", ptr[i]);
    putchar('\n');
}

// Partitioning algorithm
static
int partition(int *L, int left, int right)
{
    int pivot = left;
    int p_val = L[pivot];

    while (left < right)
    {
        while (L[left] <= p_val)
            left++;
        while (L[right] > p_val)
            right--;
        if (left < right)
            swap(&L[left], &L[right]);
    }
    swap(&L[pivot], &L[right]);
    return right;
}

// Quicksort recursion
static
void quicksort(int *L, int start, int end)
{
    if (start >= end)
        return;
    //dump_list("PRE-PARTITION", L, start, end);
    int splitPoint = partition(L, start, end);
    //dump_list("POST-PARTITION", L, start, end);
    //printf("Split point: %d\n", splitPoint);
    quicksort(L, start, splitPoint - 1);
    quicksort(L, splitPoint + 1, end);
}

int main(void)
{
    int myList[] = {12, 43, -16, 0, 2, 5, 1, 13, 2, 2, -1};
    dump_list("UNSORTED LIST", myList, 0, 9);
    quicksort(myList, 0, 9);
    dump_list("SORTED LIST", myList, 0, 9);
}

It produces the output:

  UNSORTED LIST [0..9]:   12  43 -16   0   2   5   1  13   2   2
    SORTED LIST [0..9]:  -16   0   1   2   2   2   5  12  13  43

With the debugging prints enabled, the output is:

  UNSORTED LIST [0..9]:   12  43 -16   0   2   5   1  13   2   2
  PRE-PARTITION [0..9]:   12  43 -16   0   2   5   1  13   2   2
 POST-PARTITION [0..9]:    2   2 -16   0   2   5   1  12  13  43
Split point: 7
  PRE-PARTITION [0..6]:    2   2 -16   0   2   5   1
 POST-PARTITION [0..6]:    1   2 -16   0   2   2   5
Split point: 5
  PRE-PARTITION [0..4]:    1   2 -16   0   2
 POST-PARTITION [0..4]:  -16   0   1   2   2
Split point: 2
  PRE-PARTITION [0..1]:  -16   0
 POST-PARTITION [0..1]:  -16   0
Split point: 0
  PRE-PARTITION [3..4]:    2   2
 POST-PARTITION [3..4]:    2   2
Split point: 4
  PRE-PARTITION [8..9]:   13  43
 POST-PARTITION [8..9]:   13  43
Split point: 8
    SORTED LIST [0..9]:  -16   0   1   2   2   2   5  12  13  43