Byposcher
Irgendwie machen das alle anders. An meiner Uni wird das so gemacht:
Ich verstehe das nicht. Wenn die Zeiger übereinander laufen, dann kommt bei mir eine andere Zahlenfolge raus, als auf dem Bild. Außerdem weiß ich nicht, wie das Pivot in der Mitte platziert wurde.
Kann mir jemand bitte Schritt für Schritt erklären, wie hier gearbeitet wurde? Ich wäre so dankbar.
(1 votes)
Loading...Einige mir bekannte Sprachen haben eine Art “leichtgewichtige Threads”, also ein Konstrukt für Nebenläufigkeit das man in großer Zahl (tausende oder Millionen) verwenden kann, ohne dass dafür gleich viele Betriebssystem-Threads verwendet werden. Vorteil ist, dass man gewisse Aufgaben viel einfacher synchron/blockierend erledigen kann, ohne sich mit mühsamen Callbacks oder async/await herumschlagen zu müssen, die den…
Guten Tag, eine Matherechnung bzw. eine Kostenrechnung für eine Klausurvorgabe. Wie würdet ihr rechnen?
In den aller meisten Batmanfilmen (oder in allen?) haben die Batmans stichfeste, schussichere und feuerfeste Schutzanzüge. Aus welchem Material könnte so ein Schutzanzug in echt sein, dass es diese drei Eigenschaften (oder auch mehr?) erfüllt?
Hallo zusammen, Ich hab einen Vlog auf meinem Youtube Kanal hochgeladen, in dem im Hintergrund Musik in einem Kaufhaus läuft, die ich nicht rausschneiden konnte. Das Video ist jetzt gelb markiert. Hat das jetzt Einfluss auf den weiteren Verlauf und das Wachstum des Videos? Und wie oft darf das passieren bevor man Probleme bekommt oder…
Problem: Ich schreibe eine Bachelorarbeit über das Problem, wie ich Computatuinal thinking in einer Grundschule födern bzw. unterrichten kann. Das Ganze in 4*2 Lektionen. Also ziemlich kurz. Die Praktische Arbeit ist ein Unterrichtsentwurf und die Durchführung. Mir stellt sich aber die Frage, ob ich Lerntheorien ebenfalls in die Arbeit nehme oder weglasse. Ich denke schon,…
Quicksort funktioniert ja in etwa so:
Bei dem Beispiel wurde im ersten Schritt das letzte Element als Pivot-Element gewählt. Also ist k1 = 3.
Jetzt kommen alle Elemente kleiner gleich 3 in die neue linke Liste L1 = (-3, 2, -6, 1), und alle Elemente größer gleich 3 in die neue rechte Liste R1= (8, 5, 9, 6).
Bearbeiten wir zuerst die linke Seite:
Wir wenden Quicksort auf (-3, 2, -6, 1) an und wählen k2 = 1 als Pivot. Daraus ergibt sich L2 = (-3, -6), R2 = (2).
Dann wenden wir wieder Quicksort auf L2 und R2 an. Für L3 ergibt sich: k3 = -6, L3 = leere Liste, R3 = -2.
Jetzt wenden wir wieder Quicksort auf L3 und R3 an. Beide Listen haben höchstens ein Element, d.h. wir sind fertig und setzen unsere Teilergebnisse zusammen:
(-6) + (-3) = (-6,-3),
eine Stufe darüber:
(-6,-3) + (1) + (2) = (-6, -3, 1, 2).
Jetzt sind wir wieder auf der höchsten Stufe, haben L1 fertig sortiert und bearbeiten als nächstes die rechte Teilliste R1 auf die selbe Weise. Am Ende wird die sortierte Liste dann zusammengesetzt:
(-6, -3, 1, 2) + (3) + (5, 6, 8, 9) = (-6, -3, 1, 2, 3, 5, 6, 8, 9)
verstehe das richtig , dass das erste Pivot Element zufällig ist ? Bzw das letzte gelesene ?
Es scheint so als nehme man bei diesem Beispiel bei jedem Schritt stets das letzte Element der Liste als Pivot.
Wenn keine Informationen über die Daten vorliegen ist es jedoch ratsam das Pivotelement gleichverteilt zufällig zu wählen, um die Chance auf eine Worst-Case Laufzeit zu minimieren.
Das Schaubild passt nicht os recht zur Beschreibung. Der erste Swap sollte laut Beschreibugn des Algorithmus zwischen 1 und 9 stattfinden, sodaß die 1 sich auf der linkesten Position der linken Teilliste befinden müßte.
Um n log n zu erhalten sollte man das Pivotelemt aus 3 Elementen auswaehlen