Quicksort in-place (deutsch)
HTML-код
- Опубликовано: 17 окт 2024
- Alle Sortieralgorithmen von mir gibt es hier zu sehen:
deprecated.blee...
-------------------------------------
hat dir eines meiner Videos gefallen?
Über etwas Unterstützung würde ich mich sehr freuen!
www.bleeptrack....
Jo, echt danke für das Video. Wenn man die Beschreibung für den Algorithmus im Lehrbuch liest (ohne Visualisierung!) denkt man sich ja einen Knoten ins Hirn :D
2:14 "j läuft nach rechts" sollte heißen "i läuft nach rechts"
ansonsten tolles Video
jo war auch kurz verwirrt
Hi, vielen Dank, deine Videos haben mir sehr geholfen. Über den "rant" musste ich etwas schmunzeln. Wer die Quellen nicht hinterfragt, ist selbst dran schuld, wenn die Prüfung im Anschluss in die Hose geht.
Danke, dass du nach dem allgemeinen Video auch noch dieses gemacht hast. Ist perfekt!
Was passiert mit einer Teilliste aus zwei Elementen? Ist j dann gleich dem pivot-element?
j und i ist dann gleich.
Wenn das linke Element größer ist, bleibt i und j geht weiter nach links, also wurden i und j überkreuzt. was zum Abbruch führt. Da i > p ist werden die elemente vertauscht und sind sortiert.
Wenn das rechte Element größer ist, bleibt j und i geht auf das pivot Element, also werden i und j überkreuzt, was zum Abbruch führt. Da i = p ist, wird nichts getauscht und die Elemente sind sortiert.
Ich weiß, dass das sicher nicht mehr relevant ist für dich, aber vielleicht liest das jemand, der das selbe Problem hat :p
@@Beatboxerskills Ja ich, vielen Dank xD
Welche Definition von in-place verwendest du denn? Für mich ist in-place so definiert, dass der zusätzlich verwendete Speicher nur konstant sein und nicht von der Länge der Eingabeliste abhängen darf. Das ist doch bei dir insofern nicht der Fall als dass du dir irgendwie merken musst, welche Teillisten noch unsortiert sind, und wieviele Teillisten das nun genau sind, hängt doch wiederum von der Länge der eingegeben Liste ab oder sehe ich das falsch?
628071 Hi, du brauchst bei dieser Variante kein zweites Array (oder welche Struktur man halt gerade benutzt), sondern arbeitet nur auf dem Ursprungsarry: daher in-place.
Hey, danke für die schnelle Antwort. Bin nicht sicher, ob ich die Frage richtig rübergebracht habe: Die Markierungen, die du im Video mit Kästchen um die Zahlen machst, musst du in der Praxis ja irgendwie speichern. Diese Information müsstest du doch eben gerade in einem solchen zweiten Array/Liste etc. speichern oder wie ließe sich das denn sonst realisieren? Oder beziehst du dich nur darauf, dass die zu sortierenden Daten im selben Array bleiben?
+628071 Ah, verstehe! Solche (ich nenne sie Mal Hilfsvariablen), kann man normalerweise vernachlässigen weil sie konstant ( in Abhängigkeit zur Arraylänge) sind. Und da man sich ja gerade lange Arrays für den Speicheraufwand ansieht, fallen die einfach nicht ins Gewicht. Bräuchte man dagegen ein zweites Array, dann merkt man das schon ganz deutlich :)
Ok, super. Danke für die Erklärung!
Wo ist inplace so definiert, 628071??!! Gute Frage die du stellst. Daran erkennt man den Denker :) die richtige Antwort hier wäre gewesen: Der quicksort arbeitet rekursiv und die Pointer werden natürlich alle im stack abgelegt. Im rekursiven Abstiegs kommt da eine große Menge an Pointer zusammen!!! Wie du schon vermutet hast, ist das viel Speicherbedarf, aber auf dem callstack. Wieso es also inplace heißt, liegt lediglich daran, dass all diese Pointer stets auf genau den gleichen, ursprünglichen array zeigen. (wurde ok erklärt) Neben den Pointern wird nur eine einzige Speicherzelle extra benötigt und zwar bei der Vertauschung. Dein Speicherbedarf ist aber nicht konstant! Sämtliche rekursiven Quicksort Aufrufe erfolgen stets mit genau dem gleichen speicheradresse ;)
großes dankeschön!! habe die ganze zeit nach einem beispiel gefunden, in dem das pivotelement rechts in der folge gewählt wird, da man hier ja dann das i mit dem pivotelement tauscht statt dem j (wenn man pivotelement links hat). Sehr gutes video:D
Gutes Video danke, aber eigentlich muss man nicht nochmal extra überprüfen ob der wert bei i größer ist als das pivot element da i sowieso bei der ersten zahl die nicht kleiner ist als das pivot stehen bleibt oder ?
Frage: Macht es irgendein Unterschied bei der Implementierung wenn man als Pivot den Anfang der Liste wählt ?
Hi, Die Überprüfung ist notwenig, weil es auch sein kann, dass i gar keine größere Zahl (das Pivotelement war schon die größte Zahl) findet und rechts "außerhalb" der Teilleiste landet. Dann muss natürlich nichts mehr getauscht werden.
In der Implementierung: Wenn ich das gerade richtig im Kopf habe, dann ändert sich folgendes: nachdem sich j und i "überkreuzen", überprüft man nicht ob die Zahl bei i größer als p ist, sondern ob die Zahl bei j kleiner als das Pivot ist und vertauscht die dann noch gegebenenfalls.
Ok danke
Läuft i denn trotzdem nach rechts und j nach links, wenn man als Pivot den Anfang der Liste nimmt?
+TheMnvista jup
Woher weiß ich, wo das j bei nach dem ersten durchlauf anfangen muss? Kann mir das bitte jmd erklären und warum das so ist?
schau dir das Video ruhig häufiger an. Sie hat es super erklärt.
Das j fängt nach dem 1. Durchlauf (wie auch beim 1. Durchlauf) 1 vor dem gewählten PE (=Pivotelement) an. Vorrausgesetzt, du machst es wie sie und wählst den letzten Eintrag deiner "Liste" (Arrays) immer als PE.
@@devbosko Vielen Dank!
Ich habe es mir noch mehrmals angeschaut und ein paar Beispiele bearbeitet, dann wurde das Prinzip, auch wenn ich andere PE wähle, klar.
Die Informatikklausur habe ich bestanden : )
Hey, also erstmal dein Video ist wunderbar und ich verstehe diese Verfahren bei dir immer am besten! Aber als ich begonnen habe, den Algorithmus in Java zu implementieren, ist mir aufgefallen, dass der Schritt "überprüfe, ob j
Ok hat sich schon geklärt, danke!
Die Angaben waren unklar, bin mit Penis im Toaster stecken geblieben.
Höhö
@@Max-vg5bg schöner spruch
Ausgerechnet der Worst-Case Fall :D, gutes Video, weiter so :D
Deine Videos sind sehr hilfreich ... danke! :)
Bin einfach durchgefallen in der Abschlussarbeit, weil ich das so gemacht hab !!!!!11!!!!1!1!!!11!elf -.-'
Super, vielen Dank für das hilfreiche Video (y)
Was ne aufgelegte Python-Lernkurs-Werbung 😂
Vielen Dank für das Video:D
das Intro :D :D :D
Geilomat
Sehr gut erklärt, danke dir :)