QuickSort doesn't work for large inputs

Can anyone sp开发者_StackOverflow社区ot a problem with my quick sort implementation below? It seems to fail on arrays with more than 10 or so elements.

void swap(int *p1, int *p2)
{
    int temp = *p1;
    *p1 = *p2;
    *p2 = temp;
}

void generateRandom(int arr[], int size)
{
    srand(time(NULL));
    int i;

    for (i = 0; i < size; i++)
    {
        arr[i] = rand() % 100;
    }
}

int partition(int arr[], int start, int end)
{
    int i = start, j = end;
    int pivot = arr[start];

    for (;;)
    {
        for (; arr[i] < pivot; i++);
        for (; arr[j] > pivot; j--);

        if (i < j)
        {
            swap(&arr[i], &arr[j]);
        }
        else
        {
            return j;
        }
    }
}

void quickSort(int arr[], int start, int end)
{
    int part;

    if (start < end)
    {
        part = partition(arr, start, end);
        quickSort(arr, start, part);
        quickSort(arr, part + 1, end);
    }
}

int main()
{
    generateRandom(arr, 100);
    for (i = 0; i < 100; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n\n");

    quickSort(arr, 0, 99);
    for (i = 0; i < 100; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n\n");

    return 0;
}

---

First, you code doesn't compile. When I made the corrections to make it compile (adding stdio.h, and definitions for arr and i in main) it infinite looped, which it will do if the partition starts and ends with the pivot. You need to increment and decrement before the comparisons rather than after. You can do that by starting with i = start-1 and j = end+1 and changing your inner loops to increment or decrement first, or you can leave them as is and just do an i++ and j-- after the swap -- I did that and the sort works.

Note that your pivot choice is poor for already sorted arrays; you really should be picking the median of 3 or even 9 values.

P.S. Other desirable optimizations: 1) Switch to an insertion sort for small partitions -- the optimal cutoff point is machine-dependent. Another approach is to not sort partitions below a certain size, and then do an insertion sort on the whole array after quicksort is done. It's also possible to use heapsort instead of insertion sort if done carefully; google introsort. 2) quicksort does two recursive calls; eliminate the second one by setting start = part + 1 and looping. 3) Avoid the possibility of stack overflow by quicksorting the larger partition first. 4) Eliminate the first recursive call by using an explicit stack. 5) Inline swap() and partition(). 6) Don't bother with any of that and just call the qsort library routine. :-)

---

I had the same problem, but I changed my while loop to do..while and it worked.

This is my new code now.

int partition(int a[], int lo, int hi)  {
int v = a[lo], i = lo, j = hi;

do  {

    do  {
        i++;
    } while(a[i] < v) ;

    do  {
        j--;
    }while(a[j] > v) ;

    if(i < j)   interchange(&a[i], &a[j]);  

}while(i < j);

interchange(&a[lo], &a[j]);     
return j;
}