3. Juli 200916 j Hallo, ich habe mal eine absolute Anfängerfrage: Angenommen ich habe ein Array mit den Werten 5 4 3 2 1 0 Wie wende ich darauf den Quicksortalgorithmus an, so das danach die Werte aufsteigend sortiert sind?
4. Juli 200916 j Wie wende ich darauf den Quicksortalgorithmus an, so das danach die Werte aufsteigend sortiert sind?So wie auf jedes andere Array auch. Sortieralgorithmen haben die Eigenschaft, mit jeder Art von Eingabedaten zu funktionieren. Weißt du denn, wie Quicksort grundsätzlich funkioniert? Hier findest du eine Animation und ein Beispiel für einen kompletten Sortierdurchlauf.
4. Juli 200916 j Ja ich denke schon das ich Ihn begriffen habe.... Also z.Bsp. 5 4 3 2 1 0 mit Pivotelement = 3 wird dann zu 0 4 3 2 1 5 0 1 3 2 4 5 Aber wenn ich dann die beiden Teile 0 1 und 2 4 5 nochmal mit dem Algorithmus bearbeite, was dann? Oder ist das in diesem Fall nicht nötig und es wird einfach noch die 2 auf die linke Seite von 3 genommen, so das sich dann die Folge 0 1 2 3 4 5 ergibt?
4. Juli 200916 j Aber wenn ich dann die beiden Teile 0 1 und 2 4 5 nochmal mit dem Algorithmus bearbeite, was dann?Langsam, das sind nicht die Teillisten des ersten Durchgangs. Wenn das Pivotelement 3 ist, kann nicht 2 in der rechten Teilliste landen. Und wo ist überhaupt die 3 geblieben? Das Pivotelement kannst du beim Teilen nur dann weglassen, wenn du es zwischen die Teillisten setzt. Das hast du aber nicht gemacht.
4. Juli 200916 j mhm, so recht verstehe ich das nicht. Könntest du evtl. den Quicksort des Arrays 5 4 3 2 1 0 kurz runterschreiben? Dann würde ich es wahrscheinlich besser nachvollziehen können.
5. Juli 200916 j Du teilst beim ersten Durchgang in die Partitionen: 0 1 2 | 3 4 5 (0 und 5, 1 und 4, 2 und 3 werden getauscht. Bei 2 und 3 überkreuzen sich die Zähler --> Partitionierung erfolgt also dort) Jetzt ist es zwar schon sortiert (was an der Wahl des Pivots und der umgekehrten Ausgangssortierung liegt), aber es würde nun bspw mit der linken Partition und einem neuen Pivot (vermutlich 1, wenn Du als Pivot immer das mittlere Element nimmst) rekursiv fortgefahren und erneut in Partitionen aufgeteilt werden. Ist dieses vollständig abgearbeitet, folgt die rechte Partition mit dem Pivot 4 usw.
5. Juli 200916 j Ok, und was ist wenn ich z.Bsp. als Pivotelement die 0 wähle? Dann gehe ich so vor: 5 4 3 2 1 0 1 4 3 2 5 0 1 2 3 4 5 0 Danach werden alle Zahlen > 0 auf die rechte Seite von 0 gelegt. Wäre das auch möglich?
5. Juli 200916 j Dann gehe ich so vor: 5 4 3 2 1 0 1 4 3 2 5 0 1 2 3 4 5 0Ich weiß nicht, was du da machst, aber Quicksort ist es nicht. Wenn du die 0 als Pivotelement wählst, findet der linke Zähler die 5, und der rechte gar nichts, es wird also zunächst einmal nichts vertauscht. Dann wird das Pivotelement selbst an die richtige Stelle gepackt (sonst würde das nicht terminieren), d.h. die 5 und die 0 werden vertauscht. Damit ist die 0 an der richtigen Stelle, die linke Teilliste ist leer, und die rechte Teilliste ist 4 3 2 1 5.
5. Juli 200916 j mhm ok und wie ist es damit: [ 5 4 3 2 1 0 ] Pivotelement ist 3. Dann 5 und 0, 4 und 1 vertauschen und die 2 noch mit auf die linke Seite: [ 0 1 2 ] 3 [ 4 5 ] [ 0 1 2 3 4 5 ]
5. Juli 200916 j [ 5 4 3 2 1 0 ] Pivotelement ist 3. Dann 5 und 0, 4 und 1 vertauschen und die 2 noch mit auf die linke Seite:"2 noch mit auf die linke Seite" kommt aber bei Quicksort nicht vor. Du kannst nicht einfach irgendwelche Schritte für Spezialfälle dazuerfinden, denn dann ist das kein Algorithmus mehr. Entweder du bringst das Pivotelement an die richtige Stelle (d.h. 2 und 3 vertauschen), dann hast du [0 1 2] 3 [4 5], oder nicht, dann hast du [0 1 3 2] [4 5].
5. Juli 200916 j Warum extrahierst Du eigentlich das Pivot, Klotzkopp? Es funktioniert doch so: Alles was größergleich dem Pivot ist wird nach rechts getauscht. Alles was kleinergleich dem Pivot ist wird nach links getauscht. Man kann sich zwei Zeiger vorstellen - der eine läuft von links los und der andere von rechts. Sobald einer der beiden das Pivot trifft, tauscht er es also in jedem Fall rüber. Die Partitionsgrenzen liegen aber dort, wo sich die Zeiger überkreuzen. In diesem Beispiel ist das Pivot in der rechten Partition. Eine Extrahierung erfolgt nur in dem Sonderfall, wenn beide Zeiger gleichzeitig auf dem Pivot landen würden, dieses mit sich selbst tauschen und dann eins weiter gesetzt werden. Dann steht das Pivot außerhalb der beiden sich bildenden Partitionen. Oder gibt es da Quicksort-Variationen die das anders handhaben?
5. Juli 200916 j Die bei Wikipedia beschriebene Variante tauscht nur dann, wenn die Elemente echt größer bzw. echt kleiner sind als das Pivotelement. Das spart Vertauschungen, es kann aber passieren, dass die Grenze ganz am Rand liegt. Dann würde der Algorithmus nicht terminieren. Das kann man verhindern, indem man das Pivotelement rausnimmt, und damit garantiert, dass die Teilmengen kleiner als die Usprungsmenge sind.
5. Juli 200916 j Also dann wäre meine Lösung richtig? Mit 2 rüber nehmen habe ich eigentlich gemeint das 2 und 3 vertauscht werden. Und danach, nach den Tauschvorgängen, werden die 2 Teile wieder verbunden: aus [ 0 1 2 ] 3 [ 4 5 ] wird [ 0 1 2 3 4 5 ]. Bearbeitet 5. Juli 200916 j von almig
5. Juli 200916 j Also dann wäre meine Lösung richtig? Naja, zumindest ist sie unvollständig. Quicksort erkennt nicht auf magische Weise, dass die verbliebenen Teillisten bereits sortiert sind, der Algorithmus läuft weiter bis zum bitteren Ende. Auch wenn nichts mehr vertauscht wird, es wird weiter geteilt, bis die Teillisten eine triviale Größe erreicht haben. Und danach, nach den Tauschvorgängen, werden die 2 Teile wieder verbunden: aus [ 0 1 2 ] 3 [ 4 5 ] wird [ 0 1 2 3 4 5 ].Du brauchst nichts zu verbinden, weil nie etwas getrennt wurde. Quicksort arbeitet "in-place".
5. Juli 200916 j Ok dann drücke ich es mal so aus: wenn ich so vorgehen würde in einer Klausur [ 5 4 3 2 1 0 ] Pivot = 3 [ 0 1 2 ] 3 [ 4 5 ] [ 0 1 2 3 4 5 ] natürlich noch mit der Angabe das 2 und 3 vertauscht werden und genauerer Beschreibung was mit was getauscht wird, würde das wohl die volle Punktzahl geben ?
5. Juli 200916 j würde das wohl die volle Punktzahl geben ? Vermutlich nicht, weil du die Teillisten, die sich aus dem ersten Schritt ergeben, nicht sortiert hast.
5. Juli 200916 j omg, ich werde an dem quicksort echt noch zugrunde gehen :upps Kannst du mir einen Gefallen tun, und bitte mal den kompletten Algorithmus für das Array [ 5 4 3 2 1 0 ] runterschreiben. Ich muss einfach mal die komplette richtige Lösung zum nachvollziehen sehen.
5. Juli 200916 j Du musst doch einfach nur denselben Algorithmus auf die gefundenen Teillisten [ 0 1 2 ] und [ 4 5 ] anwenden.
5. Juli 200916 j Ja aber [ 0 1 2] und [ 4 5 ] ist doch schon in der richtigen Reihenfolge. Ich glaube ich habe einen logischen Denkfehler drin....
6. Juli 200916 j Ja aber [ 0 1 2] und [ 4 5 ] ist doch schon in der richtigen Reihenfolge.Na und? In der Beschreibung von Quicksort steht nicht: "Prüfe, ob die Liste bereits sortiert ist, und falls ja, brich ab." Der Algorithmus prüft das nicht, er macht weiter. Ich sagte es doch schonmal: Auch wenn nichts mehr vertauscht wird, es wird weiter geteilt, bis die Teillisten eine triviale Größe erreicht haben.
6. Juli 200916 j Das heißt dann: [ 5 4 3 2 1 0 ] Pivot = 3, 5 und 0, 4 und 1 und 3 und 2 vertauschen. [ 0 1 2 ] 3 [4 5] Dann Pivot = 1 und 4 [ 0 ] 1 [ 2 ] 3 [ 4 ] [ 5 ] so? Dann wieder [ 0 1 2 3 4 5 ]
Archiv
Dieses Thema wurde archiviert und kann nicht mehr beantwortet werden.