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

xXsoureXx · 18. März 2010

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.

Code:

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

[COLOR="SeaGreen"]// #1 heap aufbauen[/COLOR]
 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) )
 {
[COLOR="SeaGreen"]// #2 Erstes Element mit letzem vertauschen[/COLOR]
 swap(*_list, *(_list+size));

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

[COLOR="SeaGreen"]// #3 "reheap"[/COLOR]
 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

Anzeige

Nützliche Suchen

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

Videos zum Themenbereich