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, i.e., A = 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?