0

We were given a heap sort in a pseudocode:

******* HEAP SORT ******* 

sift(A, l, r)
-------------
f <- l
s <- 2 * l
temp <- A[f]
found <- false
while not found and s <= r
    if s < r and A[s-1] < A[s] then
        s <- s+1
    if temp >= A[s-1] then
        found <- true
    else
        A[f-1] <- A[s-1]
        f <- s
        s <- 2 * f
A[f-1] <- temp


heapsort(A,N)
-------------
l <- N / 2 + 1
r <- N
while l > 1
    l <- l - 1
    sift(A, l, r)
while r > 1
    temp <- A[0]
    A[0] <- A[r-1]
    A[r-1] <- temp
    r <- r - 1

:~~~~~ Average case performance: O(23N Ln N)
:~~~~~ Worst case performance:   O(26N Ln N)

A => array
N => size of array
l => left edge
r => right edge
f => father pointer
s => son pointer

I put it in a java code:

//Heap Sort: sift() and heapsort()
    private static void sift(int[] a, int leftEdge, int rightEdge)
    {
        int fatherPointer = leftEdge;
        int sonPointer = 2 * leftEdge;
        int temp = a[fatherPointer];
        boolean found = false;
        
        while(!found && sonPointer <= rightEdge)
        {
            if(sonPointer < rightEdge && a[sonPointer-1] < a[sonPointer])
                sonPointer = sonPointer + 1;
            if(temp >= a[sonPointer-1])
                found = true;
            else
                a[fatherPointer-1] = a[sonPointer-1];
            fatherPointer = sonPointer;
            sonPointer = 2 * fatherPointer;
        }//while(!found && sonPointer <= rightEdge)
        
        a[fatherPointer-1] = temp;
    }//private static void sift(int[] a, int leftEdge, int rightEdge)

    public static void heapsort(int[] a, int n)
    {
        int leftEdge = n / 2 + 1;
        int rightEdge = n;
        int temp;
        
        while(leftEdge > 1)
        {
            leftEdge = leftEdge - 1;
            sift(a, leftEdge, rightEdge);
        }//while(leftEdge > 1)
        
        while(rightEdge > 1)
        {
            temp = a[0];
            a[0] = a[rightEdge - 1];
            a[rightEdge - 1] = temp;
            rightEdge = rightEdge - 1;
        }//while(rightEdge > 1)
    }//public static void heapsort(int[] a, int n)

but seems like there is a flaw somewhere, since it is not sorting right :o

Please, please, could anyone make some suggestions?

Thanx,

Waldis :cry:

3
Contributors
7
Replies
8
Views
11 Years
Discussion Span
Last Post by iamthwee
0

>but seems like there is a flaw somewhere
There is, and it's frustrating how the same incorrect algorithm is given so often by incompetent teachers. Here, read this. It's in C, but the code is similar enough and the principles all apply for Java.

0

Thank you, Narue. That website is really helpful for more than just a heap sort.

0

>Erm, your webpage doesn't display properly when viewed at a lower resolution...
It handles the de facto standard resolution of 800x600 when you hide the navigation bar. If your resolution is smaller than that, and you can't go higher, you're SOL until I decide to redesign.

>also the browny interface blows...
It's generally good practice to offer an alternative solution when you completely dismiss someone else's design choices.

>That website is really helpful for more than just a heap sort.
That's what I was going for. :) Now if only I had enough free time to actually write everything that I have floating around in my head...

0

>It handles the de facto standard resolution of 800x600 when you hide the navigation bar.

Erm, but then I can't see that pretty little, is it a celtic symbol, which follows me everywhere I go in the background. ;)

>It's generally good practice to offer an alternative solution when you completely dismiss someone else's design choices.

Anything other than brown perhaps. That's just a guess. :cheesy:

>Now if only I had enough free time to actually write everything that I have floating around in my head...

Arrghh, now ur scaring me. :cheesy:

[IMG]http://img476.imageshack.us/img476/5171/cut20ln.png[/IMG]
Piworld ™
[Tis simple as Pie]

0

>Erm, but then I can't see that pretty little, is it a celtic symbol, which
>follows me everywhere I go in the background.
Bummer. When I get complaints that the background is more interesting than the content, I'll look into changing it. ;)

>Anything other than brown perhaps.
My recommendation is that you check your gamma settings. The background color is closer to pink than brown. :)

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.