wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> microsoft >> sort array containing only 3 type of elements
        
(Message started by: sanny on Dec 3^rd, 2008, 1:13am)

Title: sort array containing only 3 type of elements
Post by sanny on Dec 3^rd, 2008, 1:13am

sort the array containg only 3 type of elements randomly distributed, without using extra space ( i.e, no bucket sort ) in O(n) time.

Eg.
input A= {0,1,1,2,1,0,0,2,2,0,1,1,2,0}
output A= {0,0,0,0,0,1,1,1,1,1,2,2,2,2}

Title: Re: sort array containing only 3 type of elements
Post by towr on Dec 3^rd, 2008, 2:08am

A (very much) older thread on this problem can be found here (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1100111371). (There should be more recent ones as well, but I haven't been able to find the right keywords to search (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_microsoft;action=search) for them)