[algogeeks] Re: sorting range of numbers in O(n)
Radix uses the count sort..that is why its running time O(n). -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: sorting range of numbers in O(n)
I think count sort is not acceptable (see Ankur's post for explanation), while radix sort fits the requirement. Take the array as an array of 2-digit base n numbers. First sort by the least significant digit (x%n), then the most significant digit (x//n), both using the stable counting sort. The overall time complexity is O(n). On 2010-8-2 17:34, Avik Mitra wrote: You can use count sort or radix sort. Both are of O(n) as running time complexity. You can refer to the book by Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: sorting range of numbers in O(n)
You can use count sort or radix sort. Both are of O(n) as running time complexity. You can refer to the book by Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
