I've encountered a wired question from my school's algorithm test. For the first time, I thought it was a normal fast sorting problem and I was confident of solving it, but if I read this algorithm carefully, it is a little different from the fast sort algorithm. ..
The algorithm and the question of origin are as follows:
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) Suppose the PARTITION (A, 1, 6) is applied to Table A (= (4, 3,
7, 8, 6, 2)). Note that we assume that the first element of the array is
A (1), that is, A (1) = 4 in this case. Describe the return value of
PARTITION and the state of Table A.
- (Q2) Find the smallest total
number of PARTITION calls in order to complete QUICKSORT for any
size chart 6.
I think this algorithm has a lot of "problems". First, in the QUICKSORT line 3 function, should not it be QUICKSORT (A, p, q-1)? Then, in the PARTITION functions line 2 and line 8, if we take the initial value of i as p-1, then, according to A (i)> = x, at the beginning, A (p) will always be modified ?! And on line 11, he did not change A (p) and A (j) finally ......
However, as I tried using this weird algorithm to do Q1, the result after the first iteration is 237864, the second is 234687, the third is 234678. It worked!
So, if you've seen this version of Quick Sort or if you know the mechanism, can you give me some comments?