1

I have to implement an algorithm that returns the median of an array. So I chose to implement Quickselect which seems to be efficient for this and I saw that for the tripartition I can use the same partition algorithm used in Quicksort.

The partition algorithm reported in my lecture notes (in C code) is the following:

for (i = lo, j = hi;
     (i <= j);)
{
    while (a[i] < pivot)
    {
        i++;
    }

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

    if (i <= j)
    {
        if (i < j)
        {
            /* exchange values */
            tmp = a[i];  
            a[i] = a[j];
            a[j] = tmp;
        }

        i++;
        j--;
    }

}

Now, if my array is: a = [40, 20, 100, 60, 80] and I choose as pivot the number 80, the result is: a = [40, 20, 80, 60, 100], but as you can see the values in the right partition are not all > 80 (we have 60). If I choose any other number the algorithm works properly.

Is this algorithm wrong?

Thank you for your help in advance!

4

2 回答 2

1 
[40, 20, 100, 60, 80]
          i ... #while (a[i] < pivot)

[40, 20, 100, 60, 80]
          i        j ... #while (a[j] > pivot)

[40, 20, 80, 60, 100]
          i        j ... #/* exchange values */

[40, 20, 80, 60, 100]
             ij ... #i++;j--;

[40, 20, 80, 60, 100]
              j   i  ... #while (a[i] < pivot)

[40, 20, 80, 60, 100] ... exit for-loop .. finish
于 2014-09-09T10:18:23.380 回答
1

For quickselect u need to use a recursive algorithm that will find the correct position of the pivot element, thus dividing the whole array in 2halves [elements to the right of the pivot position have value less than pivot, and the ones to the left of the pivot position have value more than the pivot]

your algorithm doesn't consider what should be done after the first loop has ended. it only finds the position of the firstly selected pivot element (that too erroneously). What will happen if the pivot position found is not the middle position (selected pivot is not the median)?

It should then move to the left part (if the newly found position of the pivot element is more than the middle position) else it should move to the right part, and perform the above step once again.

do comment if you don't understand anything

于 2014-09-09T11:50:31.910 回答