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.

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)