Is this a correct implementation of quicksort in C?

Question

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.

• Mast: 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 .

Answer 1

• 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)

• Miha: 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: obviously you did not forget an "length +", no idea what I was thinking yesterday. My bad.
• Mast: @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.