I am trying to implement the QuickSort algorithm in C, however it's giving me a pretty hard time, I don't know what I'm doing wrong but sometimes the output isn't what I expected it to be:
#include <stdio.h>
#include <stdlib.h>
void printArray(int array[], int size) {
for (int i = 0; i < size; i )
printf("%d ", array[i]);
printf("\n");
}
void swap(int *a, int *b) {
int aux;
aux = *a;
*a = *b;
*b = aux;
}
int partition(int array[], int l, int r, int size) {
int pivot_index = (l r) / 2;
int pivot = array[pivot_index];
while (l < r) {
while (l < size && pivot >= array[l])
l ;
while (r >= 0 && pivot < array[r])
r--;
if (l < r)
swap(&array[l], &array[r]);
}
swap(&array[pivot_index], &array[r]);
return r;
}
void quickSort(int array[], int start, int end, int size) {
int pivot;
if (end > start) {
pivot = partition(array, start, end, size);
quickSort(array, start, pivot - 1, size);
quickSort(array, pivot 1, end, size);
}
}
int main() {
int array_test[] = { 948, 4, 0, 89, 7, 34, 1, 3 };
printArray(array_test, (sizeof(array_test) / sizeof(array_test[0])));
quickSort(array_test, 0,
(sizeof(array_test) / sizeof(array_test[0])),
(sizeof(array_test) / sizeof(array_test[0])));
printArray(array_test, (sizeof(array_test) / sizeof(array_test[0])));
return 0;
}
Input array/Output array:
948 4 0 89 7 34 1 3->3 1 4 0 7 34 89 948
9 8 7 6 5 4 3 2 1 0->0 1 2 4 3 5 6 7 8 9
9 8 7 59 6 5 4 6 3 0 2 1 0->0 0 1 2 3 5 4 6 6 9 7 8 59
954 485 0 345 1 36->954 36 0 1 345 485
As you can see, some arrays are giving me some pretty weird results, and I don't really know why, so I'd appreciate if someone could help me figure it out.
CodePudding user response：
Your main error is here
quickSort(array_test, 0, (sizeof(array_test) / sizeof(array_test[0])) , (sizeof(array_test) / sizeof(array_test[0])));
you are passing the same value for size and end. you need
quickSort(array_test, 0, (sizeof(array_test) / sizeof(array_test[0])) - 1 , (sizeof(array_test) / sizeof(array_test[0])));
Also when doing lots of index juggling like that you can do
int partition(int array[], int l, int r, int size) {
assert(r > -1 && r < size);
assert(l > -1 && l < size);
this will stop instantly in your debugger if you use an invalid index. This would have found your error
CodePudding user response：
There are multiple problems in your code:
in
main(), you pass an initial value forrthat is too large: you should pass(sizeof(array_test) / sizeof(array_test[0])) - 1.computing the middle index with
int pivot_index = (l r) / 2;is incorrect: it may overflow on very large arrays. Useint pivot_index = l (r - l) / 2;in the
partition()function, the loop testsl < sizeandr >= 0are incorrect: you should instead comparelandrto the boundaries of the slice instead of those of the full array.the last statement
swap(&array[pivot_index], &array[r]);is incorrect as the pivot may have moved.as a matter of fact,
rmight not be the final index of the pivot value, so the recursive calls should not omit this index. The classic trick to eliminate the pivot index involves swapping the pivot to the beginning or end of the slice and swapping it back to the final value ofr.
Here is a modified version:
#include <stdio.h>
void printArray(const int array[], int size) {
for (int i = 0; i < size; i )
printf("%d ", array[i]);
printf("\n");
}
void swap(int *a, int *b) {
int aux;
aux = *a;
*a = *b;
*b = aux;
}
int partition(int array[], int l, int r, int size) {
int first = l;
int last = r;
int pivot_index = l (r - l) / 2;
int pivot = array[pivot_index];
swap(&array[first], &array[pivot_index]);
while (l < r) {
while (l < last && pivot >= array[l])
l ;
while (r > first && pivot < array[r])
r--;
if (l < r)
swap(&array[l], &array[r]);
}
swap(&array[first], &array[r]);
return r;
}
void quickSort(int array[], int start, int end, int size) {
if (start < end) {
int pivot = partition(array, start, end, size);
quickSort(array, start, pivot - 1, size);
quickSort(array, pivot 1, end, size);
}
}
int main() {
int array_test[] = { 948, 4, 0, 89, 7, 34, 1, 3 };
int array_length = sizeof(array_test) / sizeof(array_test[0]);
printArray(array_test, array_length);
quickSort(array_test, 0, array_length - 1, array_length);
printArray(array_test, array_length);
return 0;
}
Note that the last argument size is not used in the partition() function and not needed in the quickSort function. It would actually be less confusing to just pass the number of elements to both functions and adjust the array pointer upon recursion.
Here is a simplified version:
#include <stdio.h>
void printArray(const int array[], int length) {
for (int i = 0; i < length; i )
printf("%d ", array[i]);
printf("\n");
}
void swap(int *a, int *b) {
int aux = *a;
*a = *b;
*b = aux;
}
int partition(int array[], int length) {
int l = 1;
int r = length - 1;
int pivot_index = length / 2;
int pivot = array[pivot_index];
swap(&array[0], &array[pivot_index]);
for (;;) {
while (l < length - 1 && pivot >= array[l])
l ;
while (r > 0 && pivot < array[r])
r--;
if (l < r)
swap(&array[l], &array[r]);
else
break;
}
swap(&array[0], &array[r]);
return r;
}
void quickSort(int array[], int length) {
if (length > 1) {
int pivot = partition(array, length);
quickSort(array, pivot);
quickSort(&array[pivot 1], length - pivot - 1);
}
}
int main() {
int array_test[] = { 948, 4, 0, 89, 7, 34, 1, 3 };
int array_length = sizeof(array_test) / sizeof(array_test[0]);
printArray(array_test, array_length);
quickSort(array_test, array_length);
printArray(array_test, array_length);
return 0;
}
One last improvement: recursing on the smaller half limits the stack depth and avoids a stack overflow on pathological cases:
void quickSort(int array[], int length) {
while (length > 1) {
int pivot = partition(array, length);
if (pivot < length - pivot) {
quickSort(array, pivot);
array = pivot 1;
length -= pivot 1;
} else {
quickSort(&array[pivot 1], length - pivot - 1);
length = pivot;
}
}
}