Quick-Sort-Algorithmus-Progression mit gleichen Elementen

Question

Ich arbeite an einer Algorithmus-Zuweisung, die mich erfordert, um den Fortschritt des schnellen Sortieralgorithmus mit einer Anordnung von gleichen Elementen anzuzeigen (1 (a), 1 (b), 1 (c) usw.), wobei der Drehpunkt das letzte Element im Array ist. Der rekursive Teil des Algorithmus ist das, was mich verwirrt. Bisher habe ich die Progression:

1(a) 1(b) 1(c) 1(d) [1(e)] 
1(a) | 1(b) 1(c) 1(d) 1(e) 
1(a) 1(b) | 1(c) 1(d) 1(e) 
1(a) 1(b) 1(c) | 1(d) 1(e) 
1(a) 1(b) 1(c) 1(d) | 1(e) 

Danach wird der Dreh würde 1 (d) würde ich denken, und die Progression wäre das gleiche wie oben, außer mit einem weniger Austausch. Ich bin verwirrt, wie die linken und rechten rekursiven Aufrufe funktionieren. Würden die Elemente auf der "richtigen" Seite des Arrays jemals mit sich selbst ausgetauscht werden? An welchem ​​Punkt würde dieser Algorithmus aufhören? Hier

ist der Pseudo-Code:

QS(A, p, r): 
if p < r 
    q = PARTITION(A, p, r) 
    QS(A, p, q - 1) 
    QS(A, q + 1, r) 

PARTITION(A, p, r): 
x = A[r] 
i = p - 1 
for j = p to r - 1 
    if A[j] <= x 
     i = i + 1 
     exchange A[i] with A[j] 
exchange A[i + 1] with A[r] 
return i + 1 

p ist das erste Element-Array und r ist das letzte Element.

Danke für Ihre Hilfe.

Answer 1

Der zweite Aufruf, QS(A, q + 1, r), wird in Ihrem Fall sein, immer ein no-op, weil q immer gleich sein werden r, so der Aufruf QS(A, r+1, r) wird, die durch if p < r Wache wird ein no-op (p < r wird immer falsch).

Also, wenn Ihr Array indiziert ist 1, 2, ..., 5; der erste Wert von q ist 5, so ist sein erster rekursiver Aufruf QS(A,1,4) und der zweite - QS(A,6,5) (der No-Op).

Das Gleiche gilt für QS(A,1,4) geschehen - seine q 4 sein wird, und die beiden Anrufe - QS(A,1,3) und QS(A,5,4).

QA(A,1,5) 
    PARTITION(A,1,5) -> 5 
    QS(A,1,4) 
     PARTITION(A,1,4) -> 4 
     QS(A,1,3) 
      PARTITION(A,1,3) -> 3 
      QS(A,1,2) 
       PARTITION(A,1,2) -> 2 
        QS(A,1,1) 
        QS(A,3,2) 
      QS(A,4,3) 
     QS(A,5,4) 
    QS(A,6,5) 

interessante Art und Weise partition zu kodieren, nie sah es so gemacht. Ich würde < anstelle von <= dort verwenden, um nicht die gleichen Elemente jemals auszutauschen. (Hier sind natürlich alle Swaps auch No-Ops, zwischen den beiden gleichen Indizes; nicht im allgemeinen Fall).