You can use Hash but then you have to design a hash function such that hash clashes should be less which I think will depend on your input set. Hash clashes will increase time complexity of searching.
In counting sort space requirement is very high, so instead of taking too much of space you can use STL map. In Map you can search O(logN) time. so worst case time complexity will be O(NlogN) and space complexity will be O(N). http://groups.google.com/group/ds--algoitbhu/browse_thread/thread/8fd6bcfd6e24d6c4 On Mon, Sep 7, 2009 at 8:18 AM, Bharath <[email protected]> wrote: > > How about using a hash. Hash element to its position in the array. > This way we can preserve the order. > > On Sep 7, 4:33 pm, gaurav gupta <[email protected]> wrote: > > Counting Sort is a good solution. This problem is same like : > > > > you have an array 1,3,1,3,2,6,5,7,8,5,6,4,5,2 You have to arrange them > such > > that all number having same value should occur together and order of > > occurrence in series should conserve. So result will be : > > > > 1,1 ,3,3,2,2,6,6,5,5,5,7,8 ,4 > > > > > > > > On Sun, Sep 6, 2009 at 11:39 AM, Dufus <[email protected]> > wrote: > > > > > How about counting sort in O(N+K) time and O(K) space. > > > > > _dufus > > > > > On Sep 6, 1:06 pm, ankur aggarwal <[email protected]> wrote: > > > > You have N balls having one of K colors. Arrange them into groups of > same > > > > colors. e.g. > > > > > > RRRRRRGRG > > > > can be arranged as > > > > RRRRRRRGG (Answer) > > > > GGRRRRRRR > > > > -- > > GAURAV GUPTA > > B.Tech IV Yr. , Department of Computer Science & Engineering > > IT BHU , Varanasi > > Contacts > > Phone No: +91-99569-49491 > > > > e-mail : > > [email protected] > > [email protected] > > > > -- GAURAV GUPTA B.Tech IV Yr. , Department of Computer Science & Engineering IT BHU , Varanasi Contacts Phone No: +91-99569-49491 e-mail : [email protected] [email protected] --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
