View Full Version : [Frage] Zusammenfassung Sortierverfahren
PliniusSecundus
14-04-2002, 16:09
Hat schon jemand Lösungen für die Fragen unter 2.8 auf Seite 53? Insbesondere für 4. bis 7.
Ich mach jedenfalls einmal ein Thema zur Diskussion auf...
Da noch keiner hier irgendwas gepostet hat, werde ich mal meine € 0.02 besteuern. Keine Garantie darauf, dass auch nur irgendwas davon stimmt!
4. Hier den (Straight) Insertion Sort. Bei dem werden nur die Elemente herumverschoben, die noch nicht sortiert sind. (also fast keine)
5. Hier den Selection Sort. Minimale Datenbewegungen. (<= n)
6.
(Straight) Insertion Sort: n
Selection Sort: n²
Merge Sort: n log n
Partiton Exchange (aka Quicksort): n²
Heapsort: n log n
7. Da versteh ich die Frage nicht. Bitte um Erklärung.
MrBurnst
15-04-2002, 18:25
5: laut Skriptum auf Seite 38 auch Mergesort:
Als alternative Datenstruktur eignen sich verkettete Listen, da alle Teilfolgen nur sequenziell abgearbeitet werden. Dann werden keine Daten bewegt, nur Zeiger verändert => Merge Sort ist deshalb auch gut als externes Suchverfahren geeignet
9: Divide and Conquer: Merge- und Heapsort
Original geschrieben von MrBurnst
9: Divide and Conquer: Merge- und Heapsort
Also Heapsort ... ich weis net, bist sicher!?
Warum nicht auch Quicksort? Das teilt ja auch alles in 2 Teile (mit Hilfe des Pivot Elementes)
Original geschrieben von ded
6.
(Straight) Insertion Sort: n
Selection Sort: n²
Merge Sort: n log n
Partiton Exchange (aka Quicksort): n²
Heapsort: n log n
6.
heap sort: Obwohl Best Case n log n ist, tritt bei gleichen Daten imho eine Laufzeit von n auf.
Warum ?
Beim Aufbau werden n/2 Element versickert, das Versickern ist IMMER konstant (drei Vergleiche, dann Abbruch).
Beim Sortieren gibt es n Aufrufe von Versickere, wieder brechen sie nach jeweils 3 Vergleichen ab.
9. Mergesort und Quicksort. Diese beiden Verfahren haben jeweils eine führen jeweils rekursive Aufrufe der linken und rechten Hälfte aus, wobei die Teilung einmal in der Mitte floor(n/2) bei Merge und einmal durch Partitioniere mit Hilfe des Pivotelements durchgeführt wird. Heap-Sort ist imho keine Teile und Herrsche Prozedur (denn die Menge wird nicht geteilt und getrennt bearbeitet)
@ shabby
6. Stimmt schon das mit dem Merge Sort. Der scheint wirklich nur in n zu liegen. Beweisen kann ich das auch nicht, aber es ist recht anschaulich, wenn man es selbst zb. hier (http://www.cs.unc.edu/~lin/COMP122-F00/TREES/HeapSort/Control.htm) ausprobiert.
7. Hat da irgendwer eine Ahnung, was sie damit meinen? Suchverfahren, die bei mehrmaligem Auftreten von Schlüsseln inkorrekt sortieren kennen wir ja nicht. (Siehe auch 6.) Oder meinen sie, ob/wie man die einzelnen Algorithmen stabil machen kann (Was ja eigentlich Frage 8 ist)?
Ich denk mir Frage 7 ist einfach ein fake. Du musst die Algorithmen gar nicht verändern.
6) Wenn Merge-Sort wirklich in n liegt, wär ja das ein (weiterer) Fehler im Skriptum.
6. Also dass da noch keiner draufgekommen ist!
shabby und ich reden natürlich vom Heapsort !!!! (Siehe auch meinen Link) Der Mergesort liegt schon in n log n.
Nur beim Heapsort sollte sich die Funktion Versickere bei gleichen Werten eben auf 3 Vergleiche beschränken (Zeile 2, 5, 11).
Der Aufbau des ersten Heaps dauert (auch laut Skriptum) O(n).
Die Funktion Versickere wird dann noch n-1 mal aufgerufen.
Zusammengefasst (Alg 8):
c1 + c2 + (n-1) * (c3 + c4) = n/2 * c4 + c2 + (n-1) * (c3 + c4)
Wobei eben c4 nur 3 Vergleiche sind.
Schlüsselvergleiche: 3 * (3n/2 + 1)
Vertauschungen: n-1
Könnte das stimmen???
@skytale: Ich glaub' irgendwie doch nicht, dass 7 nur eine Scherzfrage ist. wahrscheinlich ist sie nur schlecht formuliert.
MrBurnst
15-04-2002, 23:06
da hab ich wohl für etwas verwirrung gesorgt... ich glaub auch nicht dass heapsort nach dem prinzip funkt... hab auch quicksort gemeint...
PliniusSecundus
16-04-2002, 09:59
SelectonS, InsertionS und BubbleS müssten die einzigen Alg sein, die im BestCase keine Moves produzieren?
Ist das nun Mmin=theta(0) oder theta(1)?
MrBurnst
16-04-2002, 13:21
zu frage 2: man kann die liste doch nicht mit quicksort sortieren weil das erste element nicht das kleinste ist... was soll man euerer meinung denn dann machen? "falsch" sortieren?
Wird durch das Stoppelement immer möglich, schau im Skriptum nach, man stellt an den anfang der Folge immer einen gesonderten Wert der kleiner als jeweils die restlichen ist = Stoppelement
SinusDiabolicus
16-04-2002, 22:47
Original geschrieben von PliniusSecundus
SelectonS, InsertionS und BubbleS müssten die einzigen Alg sein, die im BestCase keine Moves produzieren?
Ist das nun Mmin=theta(0) oder theta(1)?
insertion sort tauscht doch auch elemente mit sich selbst, müsste bei vorsortierter folge doch zu konstantem aufwand führen, oder?
(bei selection sort glaub ich auch, bin mir im moment nur nicht sicher...)
demnach wäre der einzige alg. der wirklich keine moves erzeugt bubble sort, der nämlich wirklich nur elemente tauscht die unterschiedlich sind...
/edit:
hmm, selectionsort tauscht elemente auch nicht mit sich selbst, also dürfte der im best case auch keine moves durchführen
zu 2. da krieg ich den heapsort nicht hin, hat den schon jemand und kanns mir hier rein stellen?
edit:
ah verdammt, er hat die abstände nicht richtig übernommen, vielleciht sieht mans ja trotzdem raus, wenn nicht, einfach überlesen ...
/edit
ich denk ich habs doch hingekriegt:
1 2 3 4 5 6 7
7 1012 13 128 5 4711 34
Baum: 7
1012 13
128 5 4711 34
Verschiebung 4711
1012 7
128 5 13 34
Neue Zeile
1012 7 128 5 13 34 4711
Baum 1012
7 128
5 13 34
Verschiebung erspar ich mir mal
NZ
34 7 128 5 13 1012
B 34
7 128
5 13
NZ
13 7 34 5 128
B 13
7 34
5
NZ
5 7 13 34
B 5
7 13
NZ
5 7 13
B 5
7
NZ
5 7
B 5 :cool:
stimmt das sO? (ich hoff das sieht man übersichtlich genug)
Original geschrieben von FaKe
zu 2. da krieg ich den heapsort nicht hin, hat den schon jemand und kanns mir hier rein stellen?
1. erstelle heap:
7,1012,13,128,5,4711,34
7,1012,4711,128,5,13,34
4711,1012,7,128,5,13,34
4711,1012,34,128,5,13,7
2. immer oberstes element mit letztem vertauschen und versickern:
7,1012,34,128,5,13|4711
1012,7,34,128,5,13
1012,128,34,7,5,13
13,128,34,7,5|1012
128,13,34,7,5
5,13,34,7|128
34,13,5,7
7,13,5|34
13,7,5
5,7|13
7,5
5|7
=> 5,7,13,34,128,1012,4711
vBulletin® v3.7.1, Copyright ©2000-2008, Jelsoft Enterprises Ltd.