7-1 Hoare partition correctness

The version of \(\text{PARTITION}\) given in this chapter is not the original partitioning algorithm. Here is the original partition algorithm, which is due to C.A.R. Hoare:

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
HOARE-PARTITION(A, p, r)
    x = A[p]
    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
            exchange A[i] with A[j]
        else return j

a. Demonstrate the operation of \(\text{HOARE-PARTITION}\) on the array \(A = \langle 13, 19, 9, 5, 12, 8, 7, 4, 11, 2, 6, 21 \rangle\), showing the values of the array and auxiliary values after each iteration of the while loop in lines 4-13.

The next three questions ask you to give a careful argument that the procedure \(\text{HOARE-PARTITION}\) is correct. Assuming that the subarray \(A[p..r]\) contains at least two elements, prove the following:

b. The indices \(i\) and \(j\) are such that we never access an element of \(A\) outside the subarray \(A[p..r]\).

c. When \(\text{HOARE-PARTITION}\) terminates, it returns a value \(j\) such that \(p \le j < r\).

d. Every element of \(A[p..j]\) is less than or equal to every element of \(A[j + 1..r]\) when \(\text{HOARE-PARTITION}\) terminates.

The \(\text{PARTITION}\) procedure in section 7.1 separates the pivot value (originally in \(A[r]\)) from the two partitions it forms. The \(\text{HOARE-PARTITION}\) procedure, on the other hand, always places the pivot value (originally in \(A[p]\)) into one of the two parititions \(A[p..j]\) and \(A[j + 1..r]\). Since \(p \le j < r\), this split is always nontrivial.

e. Rewrite the \(\text{QUICKSORT}\) procedure to use \(\text{HOARE-PARTITION}\).

a. After the end of the loop, the variables have the following values: \(x = 13\), \(j = 9\) and \(i = 10\).

b. Because when \(\text{HOARE-PARTITION}\) is running, \(p \le i < j \le r\) will always hold, \(i\), \(j\) won't access any element of \(A\) outside the subarray \(A[p..r]\).

c. When \(i \ge j\), \(\text{HOARE-PARTITION}\) terminates, so \(p \le j < r\).

d. When \(\text{HOARE-PARTITION}\) terminates, \(A[p..j] \le x \le A[j + 1..r]\).

e.

C++
1
2
3
4
5
HOARE-QUICKSORT(A, p, r)
    if p < r
        q = HOARE-PARTITION(A, p, r)
        HOARE-QUICKSORT(A, p, q)
        HOARE-QUICKSORT(A, q + 1, r)
本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用