Code For Binary Heapsort

Question

I am practicing writing codes from pseudocodes. I found this while going over my Introductions to Algorithms text. I am sure I coded precisely to the pseudocode, however; it is not outputing what I want. The code is a Binary Heapsort. Instead of sorting my input, the code returns my input unchanged as an output. My thoughts towards the problem exist in the build method, where I casted Math.floor() to an int. This is my first time using floor(), so I believe my lack of understanding is the problem. I believe that I am returning the lowest approximated value of heapsize/2 so I could branch my Binary Heap. But is this the case in my coding?

public class tester
{
public static void heapsort(int[] a)
{

    build(a);

    for (int i = a.length - 1; i >= 1; i--)
    {
        swap(a, 0, i);
        int heapsize = a.length - 1;
        heapify(a,0);
    }
}

public static void build(int[] a)
{
    int heapsize = a.length;
    int fl = (int) Math.floor((heapsize)/2);
    for (int i = fl; i >= 0; i--)
    {
        heapify(a, i);
    }
}

public static void heapify(int[] a, int root)
{
    int left = 2 * root + 1;
    int right = 2 * root + 2;
    int heapsize = a.length;
    int largest;

    if ( (left < heapsize) && (a[left] > a[root]))
    {
        largest = left;
    }
    else
    {
        largest = root;
    }
    if ( (right < heapsize) && (a[right] > a[largest]))
    {
        largest = right;
    }
    if (largest != root)
    {
        swap(a, a[root], a[largest]);
        heapify(a, largest);
    }

}

public static void swap(int[] a, int x, int y)
{
    int tmp;
    tmp = a[x];
    a[x] = a[y];
    a[y] = tmp;
}

public static void main(String[] args)
{
    int[] a = new int[args.length];
    for (int i = 0; i < args.length; i++)
    {
        a[i] = Integer.parseInt(args[i]);
    }
    heapsort(a);
    for (int i : a)
    {
            System.out.println(i);
        }
    }
}

Njol · Accepted Answer

Your swap method doesn't work in Java, as you can only pass primitives by value, not by reference. You can modify the method like this:

public static void swap(int[] a, int i, int j)
{
    int tmp;
    tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

This would then be called like

    swap(a, 0, i);

instead of

    swap(a[0], a[i]);

And will correctly swap two numbers in the array.

Code For Binary Heapsort

Answers (2)

Related Questions