HEAP SORT HELP

Thread view:

spidey12345 - 05 Mar 2007 01:18 GMT

Here is what i wrote for heap sort

    //heapSort method
    public static void heapsort(float[] array)
    {
        int n = array.length-1;
        BuildMaxHeap(array);
        while(n>=2){
            swap(array, 1, n);
            n--;
        }

        maxHeapfy(array, 1);
    }

    private static void maxHeapfy(float[] array, int i)
    {
        int n = array.length-1;

        int largest = i;
        int l = 2*i;
        int r = 1+2*i;

        if ( l <= n && array[l] >=array[largest]) {
        largest = l;
        }
        if ( r <= n && array[r] >=array[largest] ) {
        largest = r;
        }

        if ( largest != i ) {
        swap(array, largest, i);
        maxHeapfy(array, largest);
        }

    }

    private static void BuildMaxHeap(float[] array)
    {
        int n = array.length-1;
        for(int i = n/2; i>=1; i--)
        maxHeapfy(array, i);
    }

    private static void swap(float array[], int i, int j)
    {
    float t=array[i];
    array[i]=array[j];
    array[j]=t;
    }

when i run a float array with = { 0.12, 0.67, 0.57, 0.64, 0.93}

it gives me wrong output of 0.64, 0.57, 0.67, 0.12, 0.93} Anybody know
where my aglorithm is wrong at

by the way, the array is 0-20
so i ingored the first 0 index, and go from 1-20...
and i copy the 0-19 original array to the 1-20 copied array, and sort
the copied array... so i don't think there is anything wrong with the
starting indexes, PLZ HELP, if you can tell me where the error is at...

Reply to this Message

Joshua Cranmer - 05 Mar 2007 03:09 GMT

1. Don't shout; it gets quicker answers;
2. This is not an IM; proper grammar, spelling, punctuation, and
capitalization are useful tools here.
3. Here's your problem(s):

> Here is what i wrote for heap sort
>
[quoted text clipped - 9 lines]
> maxHeapfy(array, 1);
> }

What this code does is builds a heap, moves the largest element to the
end, and swaps some stuff within the heap and reheapifies the invalid
heap. What you're missing is that a heap has to be re-heapified after
each removal. It should look more like this:
public static void heapsort(float[] array)
{
int n = array.length-1;
BuildMaxHeap(array);
while (n >=2) {
swap(array, 1, n--);
maxHeapify(array, 1, n);
}
}

maxHeapify (there's an `i' you know) should look like this:
private static void maxHeapify(float[] array, int i, int n)
{
int largest = i, l = 2*i, r = 2*i+1;
if (l <= n && array[l] >= array[largest])
largest = l;
if (r <= n && array[r] >= array[largest])
largest = r;
if (largest != i) {
swap(array, largest, i);
maxHeapify(array, largest, i);
}
}

>     private static void BuildMaxHeap(float[] array)
>     {
>         int n = array.length-1;
>         for(int i = n/2; i>=1; i--)
>         maxHeapfy(array, i);
>     }

This code appears to be correct, except that maxHeapfy(array, i) should
be maxHeapify(array, i, n);

>     private static void swap(float array[], int i, int j)
>     {
>     float t=array[i];
>     array[i]=array[j];
>     array[j]=t;
>     }

No problems here. :-D

> when i run a float array with = { 0.12, 0.67, 0.57, 0.64, 0.93}

you should get {0.12, 0.57, 0.64, 0.67, 0.93}. Barring any stupid errors
on my part, this should work.

Reply to this Message

HEAP SORT HELP

Free Magazines