Re: [algogeeks] sorting range of numbers in O(n)
radix sort... On Mon, Aug 2, 2010 at 10:22 AM, Apoorve Mohan apoorvemo...@gmail.comwrote: Counting Sort. On Mon, Aug 2, 2010 at 6:15 AM, Praveen praveen.yarlaga...@gmail.comwrote: There are N numbers in an array and each number is in the range [0, n*n -1]. Is there a way to sort the elements in O(n)? Thanks, Praveen -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- With Regards Ankur Aggarwal -- 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] sorting range of numbers in O(n)
Counting Sort. On Mon, Aug 2, 2010 at 6:15 AM, Praveen praveen.yarlaga...@gmail.comwrote: There are N numbers in an array and each number is in the range [0, n*n -1]. Is there a way to sort the elements in O(n)? Thanks, Praveen -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- 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] sorting range of numbers in O(n)
i dont think counting sort can be applied since its time cpmplexity is O(n+k) where numbers are in the range 1...k and here k=O(n^2). so the overall complexity will again go to O(n^2) :( On Mon, Aug 2, 2010 at 10:22 AM, Apoorve Mohan apoorvemo...@gmail.comwrote: Counting Sort. On Mon, Aug 2, 2010 at 6:15 AM, Praveen praveen.yarlaga...@gmail.comwrote: There are N numbers in an array and each number is in the range [0, n*n -1]. Is there a way to sort the elements in O(n)? Thanks, Praveen -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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] sorting range of numbers in O(n)
There are N numbers in an array and each number is in the range [0, n*n -1]. Is there a way to sort the elements in O(n)? Thanks, Praveen -- 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.
