Mit hilfe einer rekursiven Baumstruktur soll ich folgende Zahlenfolge mit Quicksort darstellen:
23, 8, 17, 22, 7, 29, 26, 2, 4, 19
Lösung ist dann:
Meine eigende Lösung wäre für die zweite Zeile links eigentlich ehr:
8-17-22-7-2-4-19 oder noch nachvollziehen könnte ich wenn man die 19 als erstes schreibt:
19-8-17-22-7-2-4
und für die dritte Zeile links:
8-17-7-2-4
Meine Frage nun sind die Anordnungen manchmal einfach willkürlich das man mal ein paar Zahlen vertauscht weil man schon sieht das es so schneller geht ?
Weil ich hätte ehr gedacht das man immer nach gewählten Zahlen von links nach rechts bzw. rechts nach links kleiner oder größer werdend aufschreibt.
Ich bin schon mehre verschiedene ähnliche Lösungen durchgegangen und mir scheinen die Lösungen meist irgendwie willkürlich zu sein nach immer wieder anderen Regeln.
rlk
Senior Dabei seit: 16.03.2007 Mitteilungen: 10951
Herkunft: Wien
Beitrag No.2, eingetragen 2020-09-11
Hallo marti99,
herzlich willkommen auf dem Matheplaneten!
Für die Aufteilung (Partitionierung) der Elemente in zwie Teilfelder gibt es verschiedene Algorithmen, von denen einige auf en.wikipedia.org/wiki/Quicksort
beschrieben werden. Welche Methode habt ihr in der Lehrveranstaltung besprochen?
Kitaktus
Senior Dabei seit: 11.09.2008 Mitteilungen: 6651
Herkunft: Niedersachsen
Beitrag No.3, eingetragen 2020-09-11
Die geänderte Reihenfolge hat etwas damit zu tun, wie die Elemente bei der Zerlegung umsortiert werden. Das ist relevant, wenn man für die Sortierungen keinen zusätzlichen Speicherplatz verwenden möchte, also alle Sortierungen innerhalb des Datenfeldes durchführt.
Hier wurde vermutlich das erste Element als Pivot verwendet und von hinten angefangen zu vergleichen. Ist das Element am Ende kleiner als das Pivotelement, so wird es auf die Position des Pivots geschrieben, das wird eine Position nach rechts verschoben und das Element, was vorher dort stand, wandert ans rechte Ende.
Ist das zu vergleichende Element größer als das Pivotelement, dann bleiben alle Elemente an ihrer Position, man wandert aber in der Liste eine Stelle nach links und macht dort weiter.
Wenn man das so macht, hätte das Feld Schritt für Schritt folgenden Inhalt:
Zum Schluss wird vermutlich noch das Pivotelement ganz ans Ende der Liste geschoben, damit man es im nächsten Schritt nicht wieder als Pivot auswählt. Wie da das exakte Vorgehen ist, kann man bei dem kurzen Beispiel nicht erkennen.
Später scheint dann das fettgedruckte Element als Pivot verwendet zu werden. Wie das im Detail umgesetzt wurde, kann man an dem kleinen Beispiel nicht erkennen.
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
Themenstart: 2020-09-11
Für Ehemaliges_Mitglied bei den Matheplanet-Awards stimmen
Notiz
Profil
Quote
Link
