QuickSort C Median pivot element

Question

I'm trying to implement a QuickSort algorithm with a median pivot element... My code works, if no numbers occur twice, but this can't be the solution anyway. The code works perfect, if i choose the first element of the partition as pivot, no matter if values occur twice or more...

Here is my code:

void quickSort(int a[ ], int from, int to)
{ // sort partition from ... to of array a
    int i, pivot, new_val;
    if (from < to) // at least 2 elements in partition
    {
        //pivot = from; --> old version, first element is pivot
        pivot = median(a, from, to);
        for (i = from; i <= to; i++)
        {
            new_val = a[i];
            if (new_val < a[pivot])
            { // shift values to the right
                a[i] = a[pivot+1];
                a[pivot+1] = a[pivot];
                a[pivot] = new_val;
                pivot++;
            } // else a[i] stays put
        }
        quickSort(a, from, pivot-1); // left partition
        quickSort(a, pivot+1, to); // right partition
    } // else (from >= to) only 0 or 1 elements
} // end quicksort

int median(int a[], int from, int to)
{
    int med = (from + to) / 2;
    if((a[from] < a[med] && a[med] <= a[to]) || (a[to] < a[med] && a[med] < a[from]))
        return med;
    else if((a[med] < a[from] && a[from] < a[to]) || (a[to] < a[from] && a[from] < a[med]))
        return from;
    else if((a[med] < a[to] && a[to] < a[from]) || (a[from] < a[to] && a[to] < a[med]))
        return to;
}

what am i doing wrong??

Thanks in advance!

That for (i = from + 1; part makes perfect sense when pivot == from, not so much when using the median. — Henk Holterman

merlyn merlyn · Accepted Answer · 2014-05-29T12:06:37

When some of the elements are equal to one another, your median function fails.
None of the condition in your function evaluates to true if the input is say 3, 3, and 3.

In such a case, the function doesn't find any return statement and the behavior is undefined.
Try using <= instead of < in the conditions.

Also, you are using pivot + 1 without making sure pivot is not the last element.
If the median is the last element of the array, the program will crash.

Are you sure it works for normal input, because i tried and the function doesn't sort the array properly.
You can find a good explanation on a partitioning routine here.

QuickSort C Median pivot element

1 Answers