Clever Geek Handbook

John Bentlees beautiful quicksort - how does it work?

I thought I understood well how quicksort works until I looked at the vid at http://code.google.com/edu/algorithms/index.html where John Bentley submitted his "nice quicksort code" which looks like this :

void quicksort(int l, int u){
    int i, m;
    if(l >= u) return;
    m = l;
    for(i = l+1; i<= u; i++)
        if(x[i] < x[l])
            swap(++m, i); //this is where I'm lost. Why the heck does it preincrement?

    swap(l, m);

    quicksort(l, m-1);
    quicksort(m+1, u);

}

Another part of the algorithm that confuses me is the final swap after the FOR loop. Why is this necessary? Let's assume the array is already fine. If so, no swaps will occur since x [i]> x [l]. At the end we will change l to m. It tightens the order.

Did I miss something?

Thank.

+3


source to share


5 answers


At the beginning is m

set to a value l

, and the element is x[l]

selected as a pivot element.

The algorithm then iterates over the list, and whenever it finds an element smaller x[l]

, it moves it immediately after the current one m

. This means that when m > l

elements are in all positions from l+1

to m

less than element x[l]

.

For example:

3 5 4 2 1  l = 0, m = 0, i = 1
  ^
3 5 4 2 1  l = 0, m = 0, i = 2
    ^
3 2 4 5 1  l = 0, m = 1, i = 3
      ^
3 2 1 5 4  l = 0, m = 2, i = 4
        ^


and at the end, we replace the last of the smaller numbers with the first element (split) to get:

1 2 3 5 4

If there are no smaller items than the first, swap does nothing (since it m

is equal l

).

+5


source


The at element x[l]

is the selected bar. The invariant of the for loop is that all elements x[l+1]

through is x[m]

less than the pivot point, and all elements from x[m]

to are x[i]

greater than or equal to the axis.

When it finds an element less than the pivot point, it moves it to the entrance m+1

and then dials m

. (The entry in m+1

was larger than the pivot point, and thus its movement is fine.)



The last swap should move the from x[l]

to axis x[m]

because it must end between the bottom array and the top array. If there are no swaps (an example of a sorted array), then the m==l

final swap doesn't move anything either.

The code will be clearer pedagogically to install m = l + 1

and use m++

instead ++m

.

+1


source


The partitioning algorithm is good and easy to remember. He has been in ACM messages or retold Benltay multiple times. He also appears in Bentley's book Programming Pearls. The idea is to keep track of an element that negates a post-positional state. The elements behind the axis are smaller and higher in the index are larger. But, if the selection of a random item is not random, we may end up with the largest (or smallest) item, which will leave us with a lot of O (n) swaps. The implementation and explanation in java is [blog]: http://harisankar-krishnaswamy.blogspot.in/2013/05/quick-sort-partition-algorithm.html "here"

Hari

+1


source


If the array is sorted, m never changes from its initial value l, so the exchange does nothing.

0


source


Fixed indices l

and u

indicate the first and last elements of the array to be sorted. The value is x[l]

always selected as the pivot axis.

At the top of the cycle, the sub-matrix (excluding the pivot axis x[l]

) is divided as follows:

  • bottom area: items with indices l < index <= m

    were tested and found as< x[l]

  • middle area: items with indices m < index < i

    have been tested and found as>= x[l]

  • top area: elements with indexes i <= index <= u

    have not been tested yet

One possible source of confusion is that while the loop works, the area with values ​​greater than the pivot point is in the middle, not the top. It does not reach the top of the array until the unchecked region is exhausted — it is effectively "shifted" by repeated swaps to make room for the expanding bottom region.

In particular, the loop variable is m

pre-incremented when the bottom region needs to be expanded: the first element of the middle region (if any) needs to be wrapped to the end to expand the bottom region. Note that if the middle area is empty, m == i

after pre-increment (for this case, the operation swap()

must be no-op).

x[l]

Finally , the pivot point is replaced with the end of the bottom region to set it in place for the recursive step. Note that if the array is already in order, the bottom area is empty m == l

and the final operation swap()

does not work again.

0


source






More articles:


All Articles