The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes

Suppose that we have an array of nn 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:

  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.

Do the following:

  1. Give an algorithm that satisfies criteria 1 and 2 above
  2. Give an algorithm that satisfies criteria 1 and 3 above
  3. Give an algorithm that satisfies criteria 2 and 3 above
  4. Can you use any of your algorithms from parts (a)-(c) as the sorting method used in line 2 of RADIX-SORT, so thatRADIX-SORT sorts n records with b-bit keys in  O(bn) time? Explain how or why not.
  5. Suppose that the nn 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? )



Can somebody please provide solution with an example? 

asked in Algorithms by (147 points) | 283 views

Please log in or register to answer this question.

34,291 questions
41,038 answers
39,940 users