CODEWITHSUNDEEP
javaheapsort
James MV
James MV

Reputation: 8727

Heap sort is outfoxing me

I'm trying to implement a array based Heap Sort, its sorting the first few but not fully and I can't figure out why. Here is what I'm working with:

public class HeapSort{

    static int[] numbers = new int[] { 0, 13, 8, 5, 10, 9, 15, 1, 2, 3, 6, 4, 12, 14, 7, 11 };
    static int[] array = new int[16];

    public static void main(String[] args) {

        for (int i = 0; i < 15; i++) {
            array[i] = numbers[i];
            if (i > 1)
                sort(i);
        }

        for (int i = 1; i < 15; i++) {
            System.out.println(array[i]);
        }

    }

    public static void sort(int i) {

        int parentLocation = i / 2;
        int childLocation = i;

        int parentValue = array[parentLocation];

        int childValue = array[childLocation];

            if (childValue < parentValue) {

                array[parentLocation] = childValue;
                array[childLocation] = parentValue;

                sort(parentLocation);

            }

    }

}

I'm sure that its a fault in my use of recursion to recall the sort on the parent but I can't see why?

TIA

Upvotes: 0

Views: 284

Answers (2)

user1596193
user1596193

Reputation: 100

This is heap_sort which uses heapify and max heap concepts. I coded as per the algorithm in "Intro to Algos" book. Have a look.

#include "stdafx.h"

#define LEFT(i)         (2 * (i))
#define RIGHT(i)        (((2 * (i)) + 1))
#define PARENT(i)       ((i) / 2))

void print_heap(int input[], int n)
{
    int i;
    printf("Printing heap: \n");
    for (i = 0; i < n; i++)
        printf("%d ", input[i]);
    printf("\n");
}

void swap_nodes(int *a, int *b)
{
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}


void max_heapify(int input[], int i, int n)
{
    int largest;
    int l = LEFT(i + 1) - 1; // Get 0 based array index
    int r = RIGHT(i + 1) - 1; // Get 0 based array index

    if (l < n && input[l] > input[i]) {
        largest = l;
    } else {
        largest = i;
    }

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

    if (largest != i) {
        swap_nodes(&input[i], &input[largest]);
        max_heapify(input, largest, n);
    }
}

void heapify(int input[], int n)
{
    for (int i = n/2; i >= 0; i--)
        max_heapify(input, i, n); 
}

void heap_sort(int input[], int n)
{
    heapify(input, n);

    for (int i = n - 1; i >= 1; i--) {
        swap_nodes(&input[0], &input[i]);
        n = n - 1;
        max_heapify(input, 0, n);
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    //int input[] = {6, 5, 3, 1, 8, 7, 4, 2};
    //int input[] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
    int input[] = {5, 3, 17, 10, 84, 19, 6, 22, 9, 1};
    //int input[] = {16, 14, 10, 8, 7, 9, 3, 2, 4, 1};


    int n = sizeof(input) / sizeof(input[0]);

    print_heap(input, n);
    heap_sort(input, n);
    print_heap(input, n);

    return 0;

}

Upvotes: 3

DarthVader
DarthVader

Reputation: 55112

I have this min heap implementation in c#, pretty easy to read. Your impl is missing a lot. such as heapify. Take a look at it. hope it helps.

Upvotes: -1

Related Questions