Quicksort

[Amtrak2004]

Hallo,

kann mir jemand den Quicksort erklären? Wikipedia hilft mir nicht weiter

Danke

[Klotzkopp]

Was genau verstehst du denn an dem Wikipedia-Artikel nicht?

[Amtrak2004]

Ich verstehe nicht, wie der Quicksort-Algorithmus funktioniert.

[Klotzkopp]

Ich meine, was genau an der Erklärung im Wikipedia-Artikel verstehst du nicht?

Ich kann das hier natürlich auch nochmal erklären, aber wenn du den Wikipedia-Artikel nicht verstehst, verstehst du vermutlich meine Erklärung auch nicht.

Also beschreib bitte etwas genauer, wo die Verständnisprobleme liegen.

[MarkusLe]

Ne Bessere Erklärung als im Wiki wirst Du fürchte ich auch hier nicht bekommen, ich versuchs mal ganz grob in eigenen Woerten zusammenzufassen:

Methodenaufruf Sortiere(array, linkerIndex, rechterIndex)

-> Such dir einen Index aus der Mitte zwischen linkem und rechtem Index (Pivotelement)

-> Laufe in einer Schleife von rechts in Richtung Pivotelement und von links in Richtung Pivotelement tausche wenn rechts kleiner als Pivotelement und Links größer als Pivotelement ist die Inhalte

-> Rufe Sortiere rekursiv auf, einmal für alles links des Pivotelements und einmal für alles rechts des Pivotelements.

evtl.helfen Dir auch die Links vom Wikipedia weiter.

Gruß

Markus

[deano]

quicksort is ganz easy:

du addierst die erste und die letzte zahl und teilst das durch 2.

das ist deine "magische grenze"

nun läufst du alle zahlen durch

wir nehmen folgende zahlenreihe:

1   5   6   2   3   7   4

erstes und letztes element ergibt 5 geteilt durch 2 sind 2,5 nun ergeben sich 2 teillisten: (erklärung: der quicksort arbeitet so, dass er immer wieder die vorhandene liste in 2 teillisten teilt) a) alles was kleiner als 2,5 ist und alles was größer is erste teilliste wäre dann:

1   2

zum verständnis: wir laufen durch die liste 1, passt 5, passt nicht -> suche nach einem tauschkandidaten: 2 5 und 2 werden getauscht. 6, passt nicht -> suche tauschkandidat -> keiner gefunden. beendet alles andere ist nun in der zweiten liste:

6   5   3   7   4

genau das ist der quicksort.

wenn du jetzt schaust, hast du jetzt, exakt die gleiche lage wie am anfang meines posts -> eine liste. ok, jetzt hast du 2 einzelne, aber die kannst du genau gleich behandeln.

bei der ersten liste würde jetzt

1 und 2 ergibt 3 durch 2 sind 1,5.

die 1 bleibt so stehen und die 2 auch. d.h. die ersten beiden felder sind fertig sortiert, da du einzelne listenfelder nicht mehr aufteilen kannst.

der quicksort macht solange teillisten bis es nichtmehr weiter geht. denn dann hat er seine aufgabe erfüllt: die liste ist in der aufsteigenden reihenfolge sortiert.

hoffe, geholfen zu haben.