zum Inhalt springen

Heapsort

Links:

http://de.wikipedia.org/wiki/Sortierverfahren

http://de.wikipedia.org/wiki/Heapsort

 

C++ Quellcode

#include<iostream>
using namespace std;

// **************************************
// heapsort
void heapify(int *A, int i, int n)
{
    while(2*i <= n)
    {
        int j=2*i;
        if(j<n)
        {
            if(A[j]<A[j+1])
                j++;
        }
        if(A[i]<A[j])
        {
            swap(A[i],A[j]);
            i=j;
        }
        else
            i=n;
    }
}

void heapsort(int *A, int n)
{
    for(int i=n/2; i>=1; i--)
        heapify(A,i,n);

    for(int i=n; i>1; i--)
    {
        swap(A[i],A[1]);
        heapify(A,1,i-1);
    }
}

int main()
{
    int A[]={-1,1,6,7,3,4,5,2,8};    // mal bei 1 anfangen
    int n=sizeof(A)/sizeof(int);
    heapsort(A,n-1);
    for(int i=1; i<n; i++)
        cout << A[i] << " ";
    cout << endl;
}