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.