CODEWITHSUNDEEP
arraysalgorithmquicksort
tfreiner
tfreiner

Reputation: 309

Quick Sort Algorithm Progression With Equal Elements

I am working on an algorithms assignment which requires me to show the progression of the quick sort algorithm with an array of equal elements (1(a), 1(b), 1(c), etc.) with the pivot being the last element in the array. The recursive part of the algorithm is what is confusing me. So far I have the 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)

After this the pivot would become 1(d) I think and the progression would be the same as above except with one less exchange. I am confused as to how the left and right recursive calls work. Would the elements in the "right" side of the array ever be exchanged with themselves? At what point would this algorithm stop?

Here is the pseudocode:

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 is the first element array and r is the last element.

Thanks for your help.

Upvotes: 3

Views: 1611

Answers (1)

Will Ness
Will Ness

Reputation: 71075

The second call, QS(A, q + 1, r), in your case will always be a no-op, because q will always be equal to r, so the call becomes QS(A, r+1, r), which by if p < r guard becomes a no-op (p < r will always be false).

So if your array is indexed 1, 2, ..., 5; the first value of q is 5, so its first recursive call is QS(A,1,4) and the second -- QS(A,6,5) (the no-op).

Same thing will happen for QS(A,1,4) -- its q will be 4, and the two calls -- QS(A,1,3) and 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)

Interesting way to code partition, never saw it done this way. I'd use < instead of <= there, not to swap the equal elements, ever. (Here, of course, all the swaps are no-ops too, between the two equal indices; not in general case though).

Upvotes: 1

Related Questions