Pages

Heap Sort in c

Thursday 18 July 2013
#include<stdio.h>
#include<conio.h>
#define MAXARRAY 6

void heapsort(int ar[], int len);
void heapbubble(int pos, int ar[], int len);

int main(void)
{
    int array[MAXARRAY];
    int i = 0;

    /* load some random values into the array */
    for(i = 0; i < MAXARRAY; i++)
    array[i] = rand() % 100;

   
    printf("Before heapsort: ");
    for(i = 0; i < MAXARRAY; i++)
    {
        printf(" %d ", array[i]);
    }
    printf("\n");

    heapsort(array, MAXARRAY);

   
    printf("After heapsort: ");
    for(i = 0; i < MAXARRAY; i++)
    {
        printf(" %d ", array[i]);
    }
    printf("\n");

    return 0;
}
void heapbubble(int pos, int array[], int len)
{
    int z = 0;
    int max = 0;
    int tmp = 0;
    int left = 0;
    int right = 0;

    z = pos;
    for(;;)
    {
        left = 2 * z + 1;
        right = left + 1;

        if(left >= len)
        return;
       
        else if(right >= len)
        max = left;

        else if(array[left] > array[right])
        max = left;

        else
        max = right;

        if(array[z] > array[max])
        return;

        tmp = array[z];
        array[z] = array[max];
        array[max] = tmp;
        z = max;
    }
}
void heapsort(int array[], int len)
{
    int i = 0;
    int tmp = 0;

    for(i = len / 2; i >= 0; --i)
    heapbubble(i, array, len);

    for(i = len - 1; i > 0; i--)
    {
        tmp = array[0];
        array[0] = array[i];
        array[i] = tmp;
        heapbubble(0, array, i);
    }
}

No comments:

Post a Comment