GATE CSE
First time here? Checkout the FAQ!
x
0 votes
230 views

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 (131 points) 1 3 8 | 230 views

Please log in or register to answer this question.

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users Oct 2017
  1. Arjun

    23242 Points

  2. Bikram

    17048 Points

  3. Habibkhan

    7096 Points

  4. srestha

    6012 Points

  5. Debashish Deka

    5430 Points

  6. jothee

    4928 Points

  7. Sachin Mittal 1

    4762 Points

  8. joshi_nitish

    4278 Points

  9. sushmita

    3954 Points

  10. Rishi yadav

    3744 Points


Recent Badges

Popular Question Rahul Jain25
Popular Question Ml_Nlp
Notable Question set2018
Notable Question rahul sharma 5
Notable Question Sanjay Sharma
Notable Question Lakshman Patel RJIT
Popular Question makhdoom ghaya
Popular Question Çșȇ ʛấẗẻ
Reader kenzou
Popular Question mystylecse
27,262 questions
35,076 answers
83,760 comments
33,185 users