Victor Kwon Victor Kwon - 1 month ago 6
C Question

Quick-sort implementation in C

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

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
Comments