8-2 Sorting in place in linear time

Suppose that we have an array of \(n\) data records to sort and that the key of each record has the value \(0\) or \(1\). An algorithm for sorting such a set of records might possess some subset of the following three desirable characteristics:

  1. The algorithm runs in \(O(n)\) time.
  2. The algorithm is stable.
  3. The algorithm sorts in place, using no more than a constant amount of storage space in addition to the original array.

a. Give an algorithm that satisfies criteria 1 and 2 above.

b. Give an algorithm that satisfies criteria 1 and 3 above.

c. Give an algorithm that satisfies criteria 2 and 3 above.

d. Can you use any of your sorting algorithms from parts (a)–© as the sorting method used in line 2 of \(\text{RADIX-SORT}\), so that \(\text{RADIX-SORT}\) sorts \(n\) records with \(b\)-bit keys in \(O(bn)\) time? Explain how or why not.

e. Suppose that the \(n\) records have keys in the range from \(1\) to \(k\). Show how to modify counting sort so that it sorts the records in place in \(O(n + k)\) time. You may use \(O(k)\) storage outside the input array. Is your algorithm stable? (\(\textit{Hint:}\) How would you do it for \(k = 3\)?)

a. Counting-Sort.

b. Quicksort-Partition.

c. Insertion-Sort.

d. (a) Yes. (b) No. © No.

e.

Thanks @Gutdub for providing the solution in this issue.

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
MODIFIED-COUNTING-SORT(A, k)
    let C[0..k] be a new array
    for i = 1 to k
        C[i] = 0
    for j = 1 to A.length
        C[A[j]] = C[A[j]] + 1
    for i = 2 to k
        C[i] = C[i] + C[i - 1]
    insert sentinel element NIL at the start of A
    B = C[0..k - 1]
    insert number 1 at the start of B
    // B now contains the "endpoints" for C
    for i = 2 to A.length
        while C[A[i]] != B[A[i]]
            key = A[i]
            exchange A[C[A[i]]] with A[i]
            while A[C[key]] == key // make sure that elements with the same keys will not be swapped
                C[key] = C[key] - 1
    remove the sentinel element
    return A

In place (storage space is \(\Theta(k)\)) but not stable.

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用