1
$\begingroup$

I met a wired question from the algorithm test of my school. For the first time I thought it is a normal quick-sort problem and feel confident to solve it but as I read the algorithm carefully, it is a little different from the quick sort algorithm...

The original algorithm and question are:

QUICKSORT(A, p, r)
1 if p < r
2   then q = PARTITION(A, p, r)
3 QUICKSORT(A, p, q)
4 QUICKSORT(A, q + 1, r)

PARTITION(A, p, r)
1 x = A[p]
2 i = p − 1
3 j = r + 1
4 while TRUE
5   do repeat j = j − 1
6     until A[j] ≤ x
7   do repeat i = i + 1
8     until A[i] ≥ x
9   if i < j
10    then exchange values A[i] and A[j]
11    else return j
  • (Q1) Let us assume PARTITION(A, 1, 6) is applied to array A(= [4, 3, 7, 8, 6, 2]). Note that we assume the first element of the array is A[1], i.e., A[1] = 4 in this case. Describe the return value of PARTITION and the state of array A.
  • (Q2) Find the smallest total number of calls of PARTITION in order to complete QUICKSORT for any array of size 6.

I think this algorithm has many 'problems'. Firstly, in function QUICKSORT line 3, shouldn't it be QUICKSORT(A,p,q-1)? Then, in function PARTITION line 2 and line 8, if we take i's initial value as p-1, then according to A[i]>=x, at start the A[p] will always be changed?! And in line 11 it did not change A[p] and A[j] finally......

However, as I tried to use this wierd algorithm to do Q1, the result after the first iteration is 237864, second is 234687, third is 234678. It worked!

So if you have ever seen this version of quick sort or you know the mechanism of it, could you give me some comments?

$\endgroup$
0
$\begingroup$

Let us start with the subroutine PARTITION. The loop maintains the following invariant:

$A[k] \geq x$ for all $k \geq j$, and $A[k] \leq x$ for all $k \leq i$.

If the loop ever terminates, then the two ranges "$k \geq j$" and "$k \leq i$" cover the entire array, and in particular, $A[k] \leq x$ for all $k \leq j$, and $A[k] \geq x$ for all $k \geq i \geq j$. In particular, if $k \leq j$ and $\ell > j$ then $A[k] \leq A[\ell]$. This is what PARTITION promises:

If PARTITION$(A,p,r)$ returns $q$, then $x \leq y$ for all $x \in A[p],\ldots,A[q]$ and $y \in A[q+1],\ldots,A[r]$.

Furthermore, the particular choice $x=A[p]$ guarantees that PARTITION terminates — I'll let you work out this detail yourself.

This promise given by PARTITION guarantees the correctness of QUICKSORT: PARTITION partitions the array into two halves such that in the sorted array, all elements in the first half precede all those in the second half. In order to complete the sort, it remains to sort each half separately.

What might be throwing you off is a different variant of quicksort, in which PARTITION gives a stronger promise: all elements in $A[p],\ldots,A[q-1]$ are at most the pivot $A[q]$, and all elements in $A[q+1],\ldots,A[r]$ are at least the pivot $A[q]$. The version you describe doesn't have this promise, but otherwise is very similar to the version that you are familiar with.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.