Victor Kwon - 1 year ago 73
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");
}
``````

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
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download