8-2

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)–(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.
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? (Hint: How would you do it for k = 3?)

a. Counting satisfies the both 1 and 2 since it is stable and runs in $\theta(n)$ time.

b. quick sort runs in O(n) if we have only two elements 0,1(repeated multiple times) because it would one pass to sort the elements if we pick 0 or 1 as the pivot.

c. Insertion sort sorts in place if you see lines 5 - 7 it will swap an element only of greater than key. But if it equal to the key it will stay in the same position.

d. yes we can any of the algorithms form a -c as the sorting if the key of each record is in the range 0 to 1. Since each of the intermediate sort runs in $\theta(n)$ time and we need to sort b bits which takes $\theta(bn)$. e. COUNTING-SORT-IN-PLACE(A,k)
let C[0..k] be a new array
for i = 1 to n
C[i] = 0
for i = i to A.length
C[A[i]] = C[A[i]]+1
for i = 1 to k
C[i] = C[i] + 1
i = A.length
while C[i] > 0 and i > 0
  if C[i] > C[i-1]
   A[C[i]] = i
   C[i] = C[i] -1
  else
   i = i-1
i = 0
while C[i] > 0
  A[C[i]] = i
  C[i] = C[i] -1
yes the above sort is stable.