Verständnis der Laufzeit für Merge-Sortierung und schnelle Sortierung

Für beide merge sort und quick sort, ich versuche, mit Szenarien zu kommen, wo sie schlimmsten Fall werden. Wenn ich richtig liege, füge den Worst Case O (nlogn) der Sortierung ein, wenn alles sortiert ist. Der schlimmste Fall der Schnellsortierung liegt vor, wenn der Drehpunkt an der am wenigsten optimalen Stelle ist und das Array sortiert ist, so dass es zu O (n^2) wird. Ich habe mich gefragt, ob das zuerst richtig war, also korrigiere mich bitte wenn nicht. Meine eigentliche Frage ist, ob der Drehpunkt für die schnelle Sortierung in der Mitte eines Arrays ist, wie müsste das Array aussehen, damit es O (n^2) ist?Verständnis der Laufzeit für Merge-Sortierung und schnelle Sortierung

Quelle

2017-03-09 Dinoman979

Worst Case für schnelle Sortierung ist, wenn der Drehpunkt kleiner oder größer als alle anderen Werte ist, die sortiert werden müssen. In diesem Fall wird nur 1 Element von den verbleibenden Werten auf jeder Rekursionsstufe entfernt, und die Zeitkomplexität endet O (n^2).

Für eine einfache Zusammenführungssortierung, von oben nach unten oder von unten nach oben, ist die Anzahl der Züge immer gleich. Die Anzahl der Vergleiche hängt vom Datenmuster ab. Beim Zusammenführen von zwei Läufen der Größe n beträgt die Worst-Case-Anzahl der Vergleiche 2n-1 (wenn jedes Element außer 1 der beiden Läufe verglichen wird, wenn nur noch 1 Element vorhanden ist, gibt es nichts zu vergleichen, also wird es einfach kopiert) Der beste Fall ist, wenn alle Elemente eines Laufs kleiner als das erste Element des anderen Laufs sind. In diesem Fall ist die Anzahl der Vergleiche n, z. B. wenn die Daten bereits sortiert oder umgekehrt sortiert sind.

Quelle

2017-03-09 02:05:57 rcgldr

Wenn also die Dreh war 5 in einer Reihe von [1,2,3,4,5,6 , 7,8,9], da es in der Mitte ist, wäre die Laufzeit O (n log n), weil 5 weder größer noch kleiner als alle anderen Werte im Array ist? Wenn der Pivot immer noch 5 ist und das Array etwas wie [7,8,9,10,5,11,12,13,14] ist, würde dies der Fall sein, da der Pivot kleiner ist als alle anderen Werte ein Beispiel für die Komplexität von O (n^2)? – Dinoman979

@ Dinoman979 - ja, aber für O (n^2) Zeit Komplexität, der Code müsste wiederholt die Situation, wo der mittlere Drehpunkt ist kleiner als oder größer als die restlichen Werte. Wenn der Code den mittleren Wert wählt, wäre das Muster komplex und würde davon abhängen, ob der Pivot in die über rekursive Aufrufe übergebenen Sub-Arrays eingeschlossen ist oder nicht. – rcgldr

Sie können Quicksort emulieren und sicherstellen, dass jedes Mal, wenn der Drehpunkt ausgewählt wird, fortlaufend 0, 1, 2, ... gewählt wird, um die Worst-Case-Leistung zu garantieren.

Dies setzt einen üblichen Pivotisierungsalgorithmus voraus, der den Pivot-Wert vor dem Partitionieren des Arrays an den Anfang des Arrays verschiebt. In diesem Fall, da wir den Pivot als das kleinste verbleibende Element auswählen, wird keine Partitionierung erforderlich sein.

Hier ist der Emulationscode:

class Cell: 
    def set(self, v): 
     self.v = v 

def worst_case_quicksort(xs, i): 
    xs = xs[:] 
    for i in xrange(len(xs)): 
     p = (len(xs) - i) // 2 
     xs[i+p].set(i) 
     xs[i], xs[i+p] = xs[i+p], xs[i] 

xs = [Cell() for _ in xrange(20)] 
worst_case_quicksort(xs, 0) 
print [x.v for x in xs]

Die Ausgabe sieht wie folgt aus:

[1, 11, 3, 19, 5, 13, 7, 17, 9, 15, 0, 2, 4, 6, 8, 10, 12, 14, 16, 18]

Quelle

2017-03-09 02:37:36

Verständnis der Laufzeit für Merge-Sortierung und schnelle Sortierung

Antwort

Verwandte Themen