[C/C++] Heapsort - so richtig implentiert?

tach zusammen!

Ich habe mich in letzter Zeit etwas mehr mit Sortieralgorithmen beschäftigt und bin schließlich
auf Heapsort gestoßen. Nach dem ich ihn vom Prinzip her verstanden hatte, habe
ich versucht ihn zu implementieren. Dabei hab ich mich nach diesen Schema orientiert:


Heap aufbauen
Erste Karte ("Wurzel") mit letzer Karte austauschen
Heap wieder aufbauen (letze Karte ignorieren)


Ich habe mir natürlich den ein oder anderen Source vorher angesehen, wollte aber versuchen, dass möglichst alleine zu schaffen.
Funktionieren tut er soweit, allerdings würd mich interessieren, ob ich in etwa die effizients auch in etwa getroffen habe... Da ich selbst keine Erfahrung im Testen von Algorithmen hab ist vll einer hier so freundlich, und sagt mir, inwie weit ich das richtig gemacht habe.


void HeapSort ( int* _list, int size )
{
int parent, child; // oder von mir aus auch Knoten und Blatt .. or what ever..

// #1 heap aufbauen
for(int i=size/2; i>0; --i)
{
parent = i-1;
int temp = _list[parent];

while((child = parent*2+1) < size)
{
if (child+1 < size && _list[child] < _list[child+1] && _list[parent]<_list[child+1] )
{
_list[parent] = _list[++child];
_list[child] = temp;
}
else if (_list[parent]<_list[child] )
{
_list[parent] = _list[child];
_list[child] = temp;
}
else
break;

parent = child;
}
}


while( (--size) )
{
// #2 Erstes Element mit letzem vertauschen
swap(*_list, *(_list+size));

parent = 0;
int temp = _list[parent];

// #3 "reheap"
while(_list+parent < _list+size/2)
{
child = parent*2 + 1;
if (child+1 < size && _list[child] < _list[child+1] && _list[parent]<_list[child+1] )
{
_list[parent] = _list[++child];
_list[child] = temp;
}
else if (_list[parent]<_list[child] )
{
_list[parent] = _list[child];
_list[child] = temp;
}
else
break;

parent = child;
}
}
}

danke schon mal

Alle Posts zum Thema [C/C++] Heapsort - so richtig implentiert?, stammen von Mitgliedern des Forums.