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

- The algorithm runs in $\O(n)$ time
- The algorithm is stable.
- The algorithm sorts in place, using no more than a constant amount of storage space in addition to the original array.
Do the following:

- Give an algorithm that satisfies criteria 1 and 2 above
- Give an algorithm that satisfies criteria 1 and 3 above
- Give an algorithm that satisfies criteria 2 and 3 above
- Can you use any of your algorithms from parts (a)-(c) as the sorting method used in line 2 of
`RADIX-SORT`

, so that`RADIX-SORT`

sorts $n$ records with $b$-bit keys in $\O(bn)$ time? Explain how or why not.- Suppose that the $n$ records have keys in the range $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? (
Hint: How would you do it for $k = 3$?)

- This can be done with counting sort. We need two variables to track the numbers/indices of ones and zeroes and $\Theta(n)$ space to make a copy.
- This can be done with approach similar to Hoare partition in problem 7.1
- I can't think of a stable in-place algorithm so bubble-sort will do

Only the first one (the counting sort variant) can be used. The second is not stable, which is a requirement for radix sort, and the third takes $\Theta(n^2)$ time, which will turn the compound sorting algorithm $\Theta(bn^2)$.

We build an array of counts as in `COUNTING-SORT`

, but we perform the sorting
differently. We start with `i = 0`

and then.

```
while i ≤ A.length
if A[i] is correctly placed
i = i + 1
else
put A[i] in place, exchanging with the element there
```

On each step we're either (1) incrementing `i`

or (2) putting an element in
its place. The algorithm terminates because eventually we run out of misplaced
elements and have to increment `i`

.

There are some details about checking whether `A[i]`

is correctly placed that
are in the C code.

#include <stdbool.h> typedef struct { int key; int value; } item; static item tmp; #define EXCHANGE(a, b) tmp = a; a = b; b = tmp; void stable_linear_sort(item *A, int size) { int zero = 0, one = 0; item copy[size]; for (int i = 0; i < size; i++) { if (A[i].key == 0) { one++; } } for (int i = 0; i < size; i++) { if (A[i].key == 0) { copy[zero] = A[i]; zero++; } else { copy[one] = A[i]; one++; } } for (int i = 0; i < size; i++) { A[i] = copy[i]; } } void linear_in_place_sort(item *A, int size) { int left = -1, right = size; while (true) { do { left++; } while (A[left].key == 0); do { right--; } while (A[right].key == 1); if (left > right) { return; } EXCHANGE(A[left], A[right]); } } void stable_in_place_sort(item *A, int size) { for (int i = size; i > 0; i--) { for (int j = 0; j < i; j++) { if (A[j].key > A[j + 1].key) { EXCHANGE(A[j], A[j+1]); } } } } void in_place_counting_sort(item *A, int size, int range) { int counts[range + 1]; int positions[range + 1]; for (int i = 0; i <= range; i++) { counts[i] = 0; } for (int i = 0; i < size; i++) { counts[A[i].key]++; } for (int i = 2; i <= range; i++) { counts[i] += counts[i-1]; } for (int i = 0; i <= range; i++) { positions[i] = counts[i]; } int i = 0; while (i < size) { int key = A[i].key; bool placed = (positions[key - 1] <= i && i < positions[key]); if (placed) { i++; } else { EXCHANGE(A[i], A[counts[key] - 1]); counts[key]--; } } }