Best- und Worst-Case-Eingaben für Heap-Sortierung und schnelle Sortierung?

heap- Da der beste und der schlechteste Fall gleich sind spielt es keine Rolle in der Eingabereihenfolge? Die Anzahl der Vergleiche und Zuweisungen wird immer gleich sein. Ich stelle mir vor, dass es bei einer Heap-Sortierung dieselbe sein kann, da die eigentliche Arbeit beim Einfügen erledigt wird, aber bei der Sortierung wird nur das Entfernen der verwendet Max / Min-Heap? Ist das der Grund?

Die Anzahl der tatsächlich durchgeführten Vergleiche kann davon abhängen die Reihenfolge, in der die Werte angegeben werden. Die Tatsache, dass der beste und der schlechteste Fall jeweils Θ (n log n) sind – vorausgesetzt, alle Elemente sind unterschiedlich – bedeutet nur, dass asymptotisch keinen Unterschied gibt zwischen den beiden, obwohl sie sich um einen konstanten Faktor unterscheiden können. Ich habe keine einfachen Beispiele dafür auf der Oberseite meines Kopfes, aber ich glaube, dass Sie Eingaben konstruieren können, bei denen sich die Anzahl der Vergleiche um einen konstanten Faktor zwischen dem unterscheidet zwei Ansätze. Da die Big-O-Notation Konstanten ignoriert, spiegelt sich dies nicht in der Best-Case- und Worst-Case-Analyse wider.

schnelle Sortierung – Diese Ich weiß es nicht genau. Ich bin mir nicht sicher, was die besten und schlechtesten Situationen dafür sind. Wenn es sich beispielsweise um eine bereits sortierte Liste mit 10 Zeichenfolgen handelt, müssten wir dann nicht immer die gleiche Anzahl von Pivots auswählen, um den rekursiven Algorithmus zu vervollständigen? Jede Hilfe zu dieser Erklärung würde wirklich helfen.

Die Anzahl der ausgewählten Pivots ist unabhängig von der Ausführung des Algorithmus tatsächlich gleich. Die Arbeit pro Pivot kann jedoch variieren, je nachdem, welche Art von Aufteilung Sie erhalten. Im besten Fall ist der bei jedem Schritt ausgewählte Drehpunkt das Medianelement des Arrays. Wenn dies geschieht, werden (ungefähr) n Vergleiche in der obersten Schicht der Rekursion durchgeführt, dann (ungefähr) n in der nächsten Schicht, weil es zwei Subarrays der Größe n / 2 gibt, und dann (ungefähr) n in der nächsten Schicht, weil es vier Subarrays der Größe n / 4 usw. gibt. Da es Θ (log n) Schichten gibt und jede Schicht Θ (n) Arbeit, die insgesamt geleistete Arbeit ist Θ (n log n). Erwägen Sie andererseits, das absolute Minimum jedes Arrays als Drehpunkt zu wählen. Dann werden (ungefähr) n Vergleiche in der obersten Schicht durchgeführt, dann (ungefähr) n – 1 in der nächsten Schicht, dann (ungefähr) n – 2 in der nächsten usw. Die Summe 1 + 2 + 3 + … + n ist Θ (n ² ), daher der schlimmste Fall.

Hoffe, das hilft!

Kommentare

• Sir, wie ist der beste Fall von Heapsort nlogn? Wenn wir davon ausgehen, dass alle Elemente identisch sind, würden die Kosten nur alle Elemente des Arrays durchlaufen und sich nicht bis zur Wurzel verschieben. Also sollte es meiner Meinung nach Omega (n) sein.
• Das ist ein guter Punkt. Ich habe unterschiedliche Elemente angenommen, daher werde ich diese Antwort aktualisieren.

Da niemand „s HeapSort wurde noch wirklich angesprochen:

Angenommen, Sie verwenden einen maximalen Heap, der als Array dargestellt wird, und fügen Ihre maximalen Elemente rückwärts in Ihr Ausgabearray / in die Rückseite Ihres Arrays ein, wenn Sie dies direkt tun Die Worst-Case-Eingabe für heapSort ist eine Eingabe, die Sie zwingt, jedes Mal, wenn Sie ein Element entfernen, zu „sprudeln“ oder erneut zu aktivieren. Dies geschieht jedes Mal, wenn Sie versuchen, eine Menge ohne Duplikate zu sortieren. Es ist weiterhin Θ (n log n), wie templatetypedef sagte.

Diese Eigenschaft impliziert, dass der beste Fall von heapSort ist, wenn alle Elemente gleich sind (Θ (n), da Sie nicht nach jedem Entfernen erneut anfordern müssen, was log (n) Zeit seit dem Die maximale Höhe des Heaps beträgt log (n). Es ist jedoch eine Art mieser / unpraktischer Fall, weshalb der wirklich beste Fall für Heapsort Θ (n log n) ist.

Kommentare

• Ihr Punkt zu dem miesen unpraktischen Fall wurde gerade in meiner Algorithmusklasse gestellt. (Vorsicht vor Trickfragen.) Natürlich bin ich ‚ immer noch mit Ihrem Punkt einverstanden. ( und habe meine Antwort als Ergebnis falsch verstanden. XD)

• Schnellsortierung

  Schlimmster Fall: $ \ mathcal {O} (n ^ 2) $ Nehmen wir an, das Pivot-Element ist immer das am weitesten rechts stehende Element: Geben Sie ein bereits ein sortierte Liste mit $ n $ -Elementen. Jede Partitionierung führt also zu einer Liste mit $ n-1 $ -Elementen und eine Liste mit $ 0 $ -Elementen. Auch wenn Sie das Pivot-Element zufällig auswählen Sie können immer noch Pech haben und immer den Maximalwert in der Liste auswählen.

  $ T (n) $ ist die Anzahl der QuickSort-Vergleiche erfordert das Sortieren einer Liste mit $ n $ -Elementen. Schlimmster Fall: \ begin {align} T (n) = & T (n-1) + n & \ text {($ T (n-1) $ rekursiv, $ n $ zur Partition)} \\ = & \ frac {n (n + 1) } {2} \ in \ mathcal {O} (n) \ end {align}

  Bester Fall: $ \ mathcal {O} (n \ log n) $ . Wenn das Pivot-Element so ausgewählt ist, dass es die Liste gleichmäßig partitioniert:

  \ begin {align} T (n) = & 2 \ T \ left (\ frac {n} {2} \ right) + n & (\ text {2 mal $ \ frac {n} { 2} $ rekursiv, $ n $ zu partitionieren)} \\ \ in & \ mathcal {O} (n \ log n) & (\ text {Hauptsatz}) \ end {align}

• Heap-Sortierung

  Der Worst-Case- und der Best-Case-Komplex für die Heap-Sortierung sind beide $ \ mathcal {O} (n \ log n) $ . Daher benötigt die Heap-Sortierung $ \ mathcal {O} (n \ log n) $ -Vergleiche für jedes Eingabearray. Komplexität der Heap-Sortierung:

  \ begin {align} & \ mathcal {O} (n) & (\ text {build $ (1, n) $ heap}) \\ + & \ sum_ {i = 1} ^ {n} \ mathcal {O} (\ log i – \ log 1) & (\ text {build $ (1, j) $ heap}) \\ = & \ mathcal {O} (n) + \ sum_ {i = 1} ^ {n} \ mathcal {O} (\ log i) & (\ text {logarithm quotient rule}) \\ = & \ mathcal {O} (n \ log n) & \ left (\ sum_ {i = 1} ^ {n} \ log i < \ sum_ {i = 1} ^ {n} \ log n = n \ log n \ rechts) \ end {align }

Kommentare

• Sie haben ‚ Ich habe nicht alle Fragen des OP ‚ beantwortet, also werde ich eine beantworten, die Sie verpasst haben. Die Heap-Sortierung ‚ verwendet nicht immer die gleiche Anzahl von Vergleichen für eine bestimmte Anzahl von Elementen. Der schlechteste Fall ist $ a \, n \ log n $ und der beste Fall ist $ b \, n \ log n $, wobei $ a > b $.
• Beachten Sie auch, dass die Drei-Wege-Variante einen linearen besten Fall für die Eingabe einzelner Elemente aufweist.