CODEWITHSUNDEEP
algorithmpseudocodequicksort
andrz
andrz

Reputation: 97

quicksort quickie: the flow of control in quicksort

In what seems to me a common implementation of quicksort, the program is composed of a partitioning subroutine and two recursive calls to quicksort those (two) partitions.

So the flow of control, in the quickest and pseudo-est of pseudocode, goes something like this:

quicksort[list, some parameters]
.
.
.
q=partition[some other parameters]
quicksort[1,q]
quicksort[q+1,length[list]]
.
.
.
End

The q is the "pivot" after a partitioning. That second quicksort call--the one that'll quicksort the second part of the list, also uses q. This is what I don't understand. If the "flow of control" is going through the first quicksort first, q is going to be updated. How is the same q going to work in the second quicksort, when it comes time to do the second parts of all those partitions?

I think my misunderstanding comes from the limitations of pseudocode. There are details that have been likely left out by expressing this implementation of the quicksort algorithm in pseudocode.

Edit 1 This seems related to my problem: 

For[i = 1, i < 5, i = i + 1, Print[i]]

The first time through, we would get i=1, true, i=2, 1. Even though i was updated to 2, i is still 1 in body (i.e., Print[i]=1). This "flow of control" is what I don't understand. Where is the i=1 being stored when it increments to 2 and before it gets to body?

Edit 2

As an example of what I'm trying to get at, I'm pasting this here. It's from here.

Partition(A,p,r)
x=A[r]
i=p+1
j=r+1
while TRUE
    repeat j=j-1
       until A[j]<=x
    repeat i=i+1
       until A[i]>=x
    if i<j
       then exchange A[i] with A[j]
       else return j

Quicksort(A,1,length[A])

Quicksort(A,p,r)
if p<r
    then q=Partition(A,p,r)
        Quicksort(A,p,q)
        Quicksort(A,q+1,r)

Another example can be found here.

Where or when in these algorithms is q being put onto a stack?

Upvotes: 1

Views: 874

Answers (3)

Jim Balter
Jim Balter

Reputation: 16424

The partition code picks some value from the array (such as the value at the midpoint of the array ... your example code picks the last element) -- this is the pivot. It then puts all the values <= pivot on the left and all values >= pivot on the right, and then stores the pivot in the one remaining slot between them. At that point, the pivot is necessarily in the correct slot, q. Then the algorithm sorts the partition [p, q) and the partition [q+1, r), which are disjoint but cover all of A except q, resulting in the entire array being sorted.

Upvotes: 0

hugomg
hugomg

Reputation: 69964

Turns out Quicksort demands extra memory to function precisely in order to do the bookeeping you mentioned. Perhaps the following (pseudocode) iterative version of the algorithm might clear things up:

quicksort(array, begin, end) =
    intervals_to_sort = {(begin, end)}; //a set
    while there are intervals to sort:
        (begin, end) = remove an interval from intervals_to_sort
        if length of (begin, end) >= 2:
            q = partition(array, begin, end)
            add (begin, q) to intervals_to_sort
            add (q+1, end) to intervals_to_sort

You may notice that now the intervals to sort are being explicitly kept in a data structure (usually just an array, inserting and removing at the end, in a stack-like fashion) so there is no risk of "forgetting" about old intervals.

What might confuse you is that the most common description of Quicksort is recursive so the q variable appears multiple times. The answer to this is that every time a function is called it creates a new batch of local variables so it doesn't touch the old ones. In the end, the explicit stack from that previous imperative example ends up being implemented as an implicit stack with function variables.

(An interesting side note: some early programming languages didn't implement neat local variables like that and Quicksort was actually first described using the iterative version with the explicit stack. It was only latter that it was seen how Quicksort could be elegantly described as a recursive algorithm in Algol.)

As for the part after your edit, the i=1 is forgotten since assignment will destructively update the variable.

Upvotes: 0

amit
amit

Reputation: 178521

q is not updated. The pivot remains in his place. In each iteration of quicksort, the only element who is guaranteed to be in its correct place, is the pivot.

Also, note that the q which is "changed" during the recursive call is NOT actually changed, since it is a different variable, stored in a different area, this is true because q is a local variable of the function, and is generated for each call.

EDIT: [response to the question edit]
In quicksort, the algorithm actually generate number of qs, which are stored on the stack. Every variable is 'alive' only on its own function, and is accessible [in this example] only from it. When the function ends, the local variable is being released automatically, so actually you don't have only one pivot, you actually have number of pivots, one for each recursive step.

Upvotes: 1

Related Questions