CODEWITHSUNDEEP
calgorithmquicksort
RoodRallec
RoodRallec

Reputation: 57

QuickSort C Median pivot element

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!

Upvotes: 4

Views: 12834

Answers (1)

merlyn
merlyn

Reputation: 2361

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.

Upvotes: 3

Related Questions