Verwechslung von Quicksort mit logarithmischem Abstand

Question

Wenn nur das kleinere partitionierte Array aufgerufen wird, wie wird das größere sortiert? Ich sehe nur Code, um die Position von b zu ändern, wenn rekursiv (QS genannt in if und else Anweisung).

public static void QS(int[] b, int h, int k) { 
    int h1= h; int k1= k; 
    // invariant b[h..k] is sorted if b[h1..k1] is sorted 
    while (b[h1..k1] has more than 1 element) { 
     int j= partition(b, h1, k1); 
     // b[h1..j-1] <= b[j] <= b[j+1..k1] 
     if (b[h1..j-1] smaller than b[j+1..k1]) 
      QS(b, h, j-1); h1= j+1; 
     else 
      QS(b, j+1, k1); k1= j-1; 
    } 
} 

Answer 1

Das ist etwas schwer zu lesen Pseudo-Code. Dies könnte ein bisschen leichter zu verstehen sein:

QuickSort(b[], low, hi) 
    while the range low..hi contains more than 1 element 
    1: Pick a random pivot 'j' from the array 
    2: Re-order the array so that all elements less than the pivot are in 
     b[low..j-1], and all elements greater than the pivot are in b[j+1..hi] 
    3: Call quicksort on the side with less elements, and update the range to 
     exclude the sorted side 

Etwa die Hälfte der Werte geringer sein wird als die Dreh, und die Hälfte der Werte größer als die Dreh sein. Dies bedeutet, dass nach Schritt 3 die Größe des Bereichs niedrig .. hi grob halbiert wurde. Also braucht es log | N | Iterationen vor dem Bereich enthält nur ein Element.

Es ist schwer, dieses Bit zu erklären, aber sehen Sie, wie Schritt 3 QuickSort nur auf einer Hälfte des Arrays aufruft? Das liegt daran, dass der Rest der While-Schleife die andere Hälfte sortiert. Die Funktion leicht wieder geschrieben werden könnte wie folgt zusammen:

QuickSort(b[], low, hi) 
    if the range low..hi contains more than 1 element 
    1: Pick a random pivot 'j' from the array 
    2: Re-order the array so that all elements less than the pivot are in 
     b[low..j-1], and all elements greater than the pivot are in b[j+1..hi] 
    3: Call quicksort on both sides 

Die while-Schleife durch eine ersetzt wurde if-Anweisung und einen zweiten rekursiven Aufruf. Ich hoffe von hier aus, dass Sie die Komplexität in etwa N log | N | sehen können.

bearbeiten

Wie funktioniert die while-Schleife Art die übrigen Elemente? Nach Schritt 3 wurde der Bereich aktualisiert, um die kleinere Hälfte auszuschließen, da wir sie einfach mit einem Aufruf von QuickSort sortiert haben. Dies bedeutet, dass der Bereich nur die größere Hälfte enthält - die unsortierten Elemente. Daher wiederholen wir die Schritte 1 - 3 für diese unsortierten Elemente und aktualisieren den Bereich erneut.

Die Anzahl der unsortierten Elemente wird mit jeder Iteration kleiner und kleiner und schließlich bleibt nur ein unsortiertes Element übrig. Aber natürlich ist ein Element sortiert, so dass wir an dieser Stelle wissen, wir haben jedes Element im Array sortiert.

Answer 2

Hinweis nach dem rekursiven Aufruf an QS, h1 aktualisiert wird, wenn b [h1 ..] kleiner war als b [j + 1 ..] und k1 aktualisiert, wenn wenn b [h1 ..] wurde größer oder gleich b [j + 1 ..].

Es gibt einen Fehler im Code, der erste Aufruf nach dem if sollte QS sein (b, h1, j-1);

Logarithmische Speicherplatznutzung bezieht sich auf den Stackbereich, der von Quicksort aufgrund von Rekursion verwendet wird. In dem Beispielcode wird nur die kleinere Partition mit einem rekursiven Aufruf sortiert, dann springt der Code zurück, um die größere Partition in zwei Teile aufzuteilen, und verwendet wiederum nur einen rekursiven Aufruf für den kleineren Teil der nun aufgeteilten größeren Partition .

Link zu Artikel:

http://en.wikipedia.org/wiki/Quicksort#Optimizations

http://blogs.msdn.microsoft.com/devdev/2006/01/18/efficient-selection-and-partial-sorting-based-on-quicksort

Ich bin über den Verweis auf Endrekursion nicht sicher, da der Code eine tatsächliche Schleife statt Endrekursion verwenden. Die Tail-Rekursion würde wie ein rekursiver Aufruf in der letzten Zeile aussehen, die in einer Funktion ausgeführt wird, wobei ein Compiler sie in eine Schleife optimieren kann.