# Is this a correct implementation of quicksort in C?

I'm learning C at the moment and chose implementing quicksort as an exercise.

My code is sorting correctly, but afterwards I looked at some tutorials online about quicksort. And they implement it differently.

I don't know, if I misunderstood quicksort, or if I simply implemented it differently.

How I understood quicksort:

1. Choose pivot
2. bin elements according to their size (bigger/smaller than pivot)
3. repeat till array is sorted

I use middle element as pivot to avoid standard worst cases.

My code:

#include <stdio.h>
#include <math.h>

void quicksort(unsigned int* array, unsigned int length)
{
if (length <= 1)
{
return;
}

unsigned int length_tmp = length/2;

//pivot is middle element
unsigned int pivot = array[length_tmp];

unsigned int array_tmp[length];
unsigned int length_small = 0;
unsigned int length_big = 0;

//binning array - bigger / smaller
//left of pivot
for (unsigned int i = 0; i < length_tmp; i++)
{
if (array[i] < pivot)
{
array_tmp[length_small] = array[i];
length_small++;
}
else
{
array_tmp[length-1-length_big] = array[i];
length_big++;
}
}

//right of pivot
for (unsigned int i = length_tmp+1; i < length; i++)
{
if (array[i] < pivot)
{
array_tmp[length_small] = array[i];
length_small++;
}
else
{
array_tmp[length-1-length_big] = array[i];
length_big++;
}
}

//inserting pivot unsigned into temporary array
array_tmp[length_small] = pivot;

//copying values unsigned into array
for (unsigned int i = 0; i < length; i++)
{
array[i] = array_tmp[i];
}

//recursive function calls
quicksort(array+0, length_small);
quicksort(array+length_small+1, length_big);

return;
}

int main()
{
unsigned int array[] = {1,2,3,7,8,9,6,5,4,0};
unsigned int length = sizeof array / sizeof array[0];  //alternative: sizeof array / sizeof *array

//printing array
printf("unsorted array: ");
for (unsigned int i = 0; i < length; i++)
{
printf("%d", array[i]);
}
printf("\n");

//calling sorting function
quicksort(array, length);

//printing array
printf("sorted array: ");
for (unsigned int i = 0; i < length; i++)
{
printf("%d", array[i]);
}
printf("\n");

return 0;
}


I had posted this before on stackoverflow, but was informed of my mistake and that I should post it here. I didn't get answer to my question in that short time, but a few pointers regarding my code which I tried to implement in my solution.

• Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers.
– Mast
Commented Apr 21, 2020 at 9:32

• The most valuable feature of quicksort is that it sorts in-place, without a temporary array. The average space complexity quicksort is logarithmic, whereas the one of your solution is linear. The time complexity is also affected by the copying from temporary back to original.

NB: If you can afford a linear temporary, don't use quicksort. Mergesort will win hands down: it doesn't have a worst case, and besides it is stable.

• Choosing middle element for the pivot, while harmless, doesn't avoid the worst case. The performance of the quicksort is affected not by where the pivot is chosen, but by where it lands after partitioning. Worst case arises when they consistently land near the edges of the array.

• I don't see the need to treat left of pivot and right of pivot separately:

Swap the pivot with the first element (array[0] now holds the pivot)
Partition the entire [1..length) range in one pass
Swap the array[0] (which holds the pivot) with array[length_small].

• A length of the array should be size_t. There is no guarantee that unsigned int is wide enough to represent a size of a very large array.

• The code before the recursive call implements an important algorithm, namely partition and deserves to be a function of its own. Consider

void quicksort(int *array, size_t length)
{
if (length <= 1) {
return;
}
size_t partition_point = partition(array, length);
quicksort(array, partition_point);
quicksort(array + partition_point + 1, length - partition_point - 1);
}

• Further down, you may want to implement two improvements:

• Recursion cutoff: when the array becomes small enough, insertion sort performs better

• Tail call elimination (not really necessary, the C compilers are good in it)

• OK, I will rework it to be in-place and use the swapping of the pivot element. I had heard of size_t before, but hadn't found a good source to explain it to me yet. Have a heard time to find sources to explain so I can understand it easily. Outsourcing the partition sounds like a good idea. Is what you call partition_point what I call length_small? If so, did you forget a "length +" in the first call? I only have looked at BubbleSort and Quicksort so far, will look at Insertion and Merge next. Do you a good source to read about tail call elimination? Not sure what you are talking about.
– Miha
Commented Apr 20, 2020 at 20:09
• obviously you did not forget an "length +", no idea what I was thinking yesterday. My bad.
– Miha
Commented Apr 21, 2020 at 8:05
• @Miha A recursive function is tail recursive if a recursive call is the last thing executed by the function. Tail recursive is easier to optimize for compilers than non-tail recursive due to their structure (effectively they do the tail call elimination for you). Tail calls and quicksort.
– Mast
Commented Apr 21, 2020 at 9:36