Antworte auf:  Quicksort/Baumstruktur von Ehemaliges_Mitglied
Forum:  Algorithmen / Datenstrukturen, moderiert von: matroid

[Zur Forum-Gliederung] [Wie man Fragen beantwortet] [Themenstart einblenden]

  Alle registrierten Mitglieder können Mitteilungen schreiben.
Benutzername:
Passwort:
Nachricht-Icon:                   
                  
              
Nachricht:


 
 


Input assistance tools (JavaScript): [Link extern intern] [MathML?] [$$?]
[fed-area] [LaTeX-inline] [LaTeX-display] [Tikz] [hide-area][show-area] [Source code [num.]][?]
 Show Preview      Write using fedgeo formula editor or Latex.

Smilies for your message:
😃 😄 😁 🙂 🙃 😉 🤗 🤫 🤔 🙄 😴 🤒 😎 😮 😲 😂
🙁 😖 😒 😐 😡 👌 👍 👎 🤢 🤧 🥵 🥶 😵 🤯 😛 😷
Optionen: Deaktiviere HTML in dieser Nachricht
Deaktiviere MATHML in dieser Nachricht. Wenn Dein Text $-Zeichen enthält, die nicht LaTeX-Formeln begrenzen.
Deaktiviere Smilies in dieser Nachricht
Zeige die Signatur (Kann in 'Mein Profil' editiert werden.)
    [Abbrechen]
 
Beachte bitte die [Forumregeln]


Themenübersicht
Kitaktus
Senior
Dabei seit: 11.09.2008
Mitteilungen: 6598
Herkunft: Niedersachsen
 Beitrag No.4, eingetragen 2020-09-12 23:07    [Diesen Beitrag zitieren]

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


Kitaktus
Senior
Dabei seit: 11.09.2008
Mitteilungen: 6598
Herkunft: Niedersachsen
 Beitrag No.3, eingetragen 2020-09-11 13:57    [Diesen Beitrag zitieren]

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.


rlk
Senior
Dabei seit: 16.03.2007
Mitteilungen: 10904
Herkunft: Wien
 Beitrag No.2, eingetragen 2020-09-11 08:52    [Diesen Beitrag zitieren]

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.]


DerEinfaeltige
Senior
Dabei seit: 11.02.2015
Mitteilungen: 2493
Herkunft:
 Beitrag No.1, eingetragen 2020-09-11 08:34    [Diesen Beitrag zitieren]

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


Ehemaliges_Mitglied
 Themenstart: 2020-09-11 07:18    [Diesen Beitrag zitieren]

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.


 
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]