heapsort

was ist denn der schlechteste fall für heapsort?

wenn die elemente genau in der falschen reihenfolge soertiert sind ? (oder ähnlich) ??

oder doch etwas anderes?

StarCraftFeuerteufel

umgekehrte reihenfolge müsste schon hinkommen, aber man muss ja sowieso immer erst den heap aufbauen, und dann nach und nach delete_min-operation ausführen, bis der heap leer ist. also bleibst du asymptotisch immer in O(n*log n).
heapsort ist auch stabil bzgl. dieser laufzeit, nicht wie z.B. quicksort, das u.U. auch in O(n^2) laufen kann, jenachdem wie das pivot-element gewählt wird.

nicht wie z.B. quicksort, das u.U. auch in O(n^2) laufen kann, jenachdem wie das pivot-element gewählt wird

...und wie die gegebene Reihenfolge der zu sortierenden Daten ist!

(Es sei denn man wählt das Pivot Element zufällig. Dann hat man zwar immer noch im schlimmsten fall Quadratische Laufzeit. Diese hängt dann aber nicht mehr von der gegebenen Reihenfolge der zu sortierenden Daten ab, sondern vom Zufall(des Pivot Elements)!

so ich hab jetz ein problemchen...

wir sollen heapsort folgendes absteigend sortieren:

3 12 4 5 11 15 2 17 13 1 6 7

der erste schritt ist klar:

3 12 4 17 11 15 2 5 13 1 6 7

so ich habe dann im nächsten schritt:

3 17 4 12 11 ...

ein freund meint aber es MUSS

3 12 15 17 11 4 ... sein

der einzige unterschied ist dass ich den LINKEN knoten zuerst vorgenommen habe und er den rechten?

ist das jetzt FALSCH oder eher formsache?

um missverständnisse zu vermeiden : eine folge

x y z a b c d

->

x
y z
a b c d ...

StarCraftFeuerteufel

so wie ich das sehe sind beide varianten nicht richtig, aber um das genau sagen zu können müsste ich mal euren algorithmus für heapsort sehen. gibt da halt ein paar feinheiten die zu beachten sind, zum beispiel ob ihr einen min-heap oder max-heap habt jenachdem erhaltet eine aufsteigend oder absteigend sortierte folge der zahlen.
wie gesagt der erste schritt ist aufjedenfall den heap aufzubauen, die beispielfolgen sind keine min/max-heaps.

array a;
n = length(a);
build_max_heap(a);//erster schritt
for(k = 0; k < n - 1; k++)
{
  a.swap(0, n - 1 - k);
  //heap eigenschaft wieder herstellen im bereich [0, n - 2 - k]
  heapify(a, 0, n - 2 - k);
}

danach steht in a die aufsteigend sortierte folge von zahlen.
mit build_min_heap erhält man die absteigende folge von zahlen.
konkrete umsetzung von build_max_heap und heapify, einfach mal googln.

Ich hab da ne frage woher weiß ich im code ob ich auf/absteigend sortieren muss ??

volkard

iii schrieb:

Ich hab da ne frage woher weiß ich im code ob ich auf/absteigend sortieren muss ??

Je nach Sprache. In C++ gilt zum Beispiel:
IMMER aufsteigend.
Will man absteigend haben, benutzt man trotzdem einen Aufsteigens-Sortierer und stellt sich auf den Kopf oder die Welt oder, was am üblichsten ist, die Ordnung. Dazu ist der dritte Parameter da http://www.sgi.com/tech/stl/stable_sort.html

Dankeee dir :))))