Correctness of quick sort in C

What do you think of this piece of code ? This is an implementation of quick sort in C, but I'm not sure about the quality and correctness.

#include 

void swap(int tab[], int a, int b)
{
  int temp = tab[a];
  tab[a] = tab[b];
  tab[b] = temp;
}

void quickSort(int tab[], int begin, int end)
{
  int left = begin-1;
  int right = end+1;
  const int pivot = tab[begin];

  if(begin >= end)
    return;

  while(1)
    {
      do right--; while(tab[right] > pivot);
      do left++;  while(tab[left] < pivot);

      if(left < right)
        swap(tab, left, right);
      else break;
    }

  quickSort(tab, begin, right);
  quickSort(tab, right+1, end);
}

int main(void)
{
    int tab[5] = {5, 3, 4, 1, 2};
    int i;

    quickSort(tab, 0, 4);

    for(i = 0; i < 5; i++)
    {
        printf("%d ", tab[i]);
    }
    putchar('\n');

    return 0;
}

Is it the standard way of implementing a quick sort in C ?

The code is not a bad implementation of Quicksort but it has a flaw, inherent to the Quicksort algorithm, that you can easily fix. I tested the code with this main:

const int testsize = 100000;

int main(void)
{
    int tab[testsize];
    int i;

    for(i = 1; i < testsize; i++)
        tab[i] = i;

    tab[0] = testsize+1;
    quickSort(tab, 0, testsize-1);
    return 0;
}

As you can see, this is deliberately the worst case scenario for Quicksort in which it takes \$O(n^2)\$ time to sort. This code took 11.85 seconds on my machine. Quicksort works best on randomly arranged data, so paradoxically, you can often actually improve sorting time by randomly shuffling the data before you start. I wrote this rather simple-minded shuffle routine:

void shuffle(int tab[], int begin, int end)
{
    for (; begin < end/2; ++begin)
        swap(tab, begin, rand()%end);
}

When I inserted a call to shuffle() just before the call to quickSort() in main, the time to sort the same data dropped to 0.026 seconds. By comparison, the standard qsort() sorts in 0.006 seconds on this same machine.

Also, more generally, I'd be inclined to pass two pointers to swap rather than an array and two indices. The code may be very slightly faster, but it's certainly more general.

The code could also be made more general by using the same parameters as the qsort() routine in `` but then, that's already written. :)

StackExchange Code Review Q#48481, answer score: 3