Forum:  Algorithmen / Datenstrukturen
Thema: Quicksort/Baumstruktur
Themen-Übersicht
Ehemaliges_Mitglied
Neu
Dabei seit: 00.00.0000
Mitteilungen: 0
Aus:
Themenstart: 2020-09-11 07:18

Hallo ich habe folgendes Problem.

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.


DerEinfaeltige
Senior
Dabei seit: 11.02.2015
Mitteilungen: 2514
Aus:
Beitrag No.1, eingetragen 2020-09-11 08:34

Ohne den konkret verwendeten Algorithmus für die Partitionierung kann man das mMn. nicht nachvollziehen.


rlk
Senior
Dabei seit: 16.03.2007
Mitteilungen: 10908
Aus: Wien
Beitrag No.2, eingetragen 2020-09-11 08:52

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?

Servus,
Roland
 

[Die Antwort wurde vor Beitrag No.1 begonnen.]


Kitaktus
Senior
Dabei seit: 11.09.2008
Mitteilungen: 6610
Aus: Niedersachsen
Beitrag No.3, eingetragen 2020-09-11 13:57

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:
23| 8 17 22  7 29 26  2  4 19|
19 23|17 22  7 29 26  2  4  8|
19  8 23|22  7 29 26  2  4 17|
19  8 17 23| 7 29 26  2  4 22|
19  8 17 22 23|29 26  2  4  7|
19  8 17 22  7 23|26  2  4 29|
19  8 17 22  7  4 23| 2 26 29|
19  8 17 22  7  4 23| 2 26|29
19  8 17 22  7  4 23| 2|26 29
19  8 17 22  7  4  2 23 26 29
 
Die Striche | markieren den noch unsortierten Bereich.
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.


Kitaktus
Senior
Dabei seit: 11.09.2008
Mitteilungen: 6610
Aus: Niedersachsen
Beitrag No.4, eingetragen 2020-09-12 23:07

Wenn man die Antwort gelesen hat, darf man auch gerne einen Kommentar dazu abgeben, womöglich sogar einen Dank aussprechen.




Dieses Forumbeitrag kommt von Matroids Matheplanet
https://https://matheplanet.de

Die URL für dieses Forum-Thema ist:
https://https://matheplanet.de/default3.html?topic=249363=5103
Druckdatum: 2020-11-29 08:49