Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » Quicksort/Baumstruktur
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Quicksort/Baumstruktur
Ehemaliges_Mitglied
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-09-11


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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2434
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-09-11


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


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
rlk
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.03.2007
Mitteilungen: 10869
Aus: Wien
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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

beschrieben werden. Welche Methode habt ihr in der Lehrveranstaltung besprochen?

Servus,
Roland
 

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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6571
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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:
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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6571
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2020-09-12


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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Ehemaliges_Mitglied hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]