+1 mithun kumar !!
using bit array or bitmap index gives the best solution ( O(n) )
the only limitation is we should know the maximum limit of the number,
which is provided in this problem :D
Thanks Regards
Saurabh Yadav
--
You received this message because you are subscribed to the Google
using bit array we can sort elements in O(1)
-mithun
On Sat, May 5, 2012 at 12:17 AM, Algobiz deepak.arulkan...@gmail.comwrote:
How to sort n numbers in the range of 1 to n^2 in O(n).. Any ideas?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks
After giving some thought,I think even radix sort may not be sufficient.
Complexity of radix sort is O(k*n) where k is the number of buckets
required to sort the given range.
The number of buckets is proportional to the number of bits required to
represent the *maximum number in the given
Hi all,
I am new to this group.
My last post was deleted i do not know the reason behind it.
I will explain my logic here:-
as the range is 1 to n^2 we have a input array like input[n^2].
We can take a auxillary array of size n^2 like aux[n^2].
Scan the input array.
For each input input[i]
Consider the case
n=6
array elements :-
{36 36 36 36 36 36}
How many iterations your code makes?
Consider another case
n=100
array={1e12,1e12 ..repeated 10^6 times}
How many iterations your code make?
Are the iterations still proportional to n that is the number of elements
in the array?
How to sort n numbers in the range of 1 to n^2 in O(n).. Any ideas?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/PGgMdaIbGIsJ.
To post to this group, send
The range 1 to n^2 is already sorted
On Sat, May 5, 2012 at 12:17 AM, Algobiz deepak.arulkan...@gmail.com wrote:
How to sort n numbers in the range of 1 to n^2 in O(n).. Any ideas?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view
@cegprakash They are n numbers lying in the range 1 to n^2.Not necessarily
sorted.
eg 3 4 1 2 5 8 (6 numbers satisfying the conditions given in the problem)
Saurabh Singh
B.Tech (Computer Science)
MNNIT
blog:geekinessthecoolway.blogspot.com
On Sat, May 5, 2012 at 5:17 AM, Prakash D
Hi,
How can we sort one unsorted int array with O(n).
Unsorted : {4,2,6,1,5,5,1,2,45,444,44,45,4,1}
Sorted : {1,1,1,2,2,4,4,5,5,6,44,45,45,444}
Is there any sorting method which gives us O(n) time complexity???
Please tell the algo if anybody knows it.
--
AMAN AGARWAL
Success is not final,
Counting sort, radix sort, .
On Wed, Aug 3, 2011 at 10:58 AM, AMAN AGARWAL mnnit.a...@gmail.com wrote:
Hi,
How can we sort one unsorted int array with O(n).
Unsorted : {4,2,6,1,5,5,1,2,45,444,44,45,4,1}
Sorted : {1,1,1,2,2,4,4,5,5,6,44,45,45,444}
Is there any sorting method which
counting sort
http://en.wikipedia.org/wiki/Counting_sort
Thanks
NItin
On Wed, Aug 3, 2011 at 10:58 AM, AMAN AGARWAL mnnit.a...@gmail.com wrote:
Hi,
How can we sort one unsorted int array with O(n).
Unsorted : {4,2,6,1,5,5,1,2,45,444,44,45,4,1}
Sorted : {1,1,1,2,2,4,4,5,5,6,44,45,45,444}
Given a valid range sort keys, the linked list can be sorted in O9n) time
using counting sort which takes O(n+k) comparisons to sort the list of K
elements .
On Sat, Jul 23, 2011 at 9:58 AM, Ankur Khurana ankur.kkhur...@gmail.comwrote:
10^9--10^9 - 8- 7- NULL . It wont help in this case...
How to sort Linked lists in O(n) time ??
Give the algorithm or the explanation or clue to tackle the problem
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from
use counting sort..
On Sat, Jul 23, 2011 at 1:22 AM, rShetty rajeevr...@gmail.com wrote:
How to sort Linked lists in O(n) time ??
Give the algorithm or the explanation or clue to tackle the problem
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks
For linklist? How
On Sat, Jul 23, 2011 at 1:23 AM, Kamakshii Aggarwal
kamakshi...@gmail.comwrote:
use counting sort..
On Sat, Jul 23, 2011 at 1:22 AM, rShetty rajeevr...@gmail.com wrote:
How to sort Linked lists in O(n) time ??
Give the algorithm or the explanation or clue to tackle the
actually its a work around...first traverse the list and store it in an
array..
sort the array in o(n)
then replace the content of the linked list using the values in the array
On Sat, Jul 23, 2011 at 1:24 AM, Pankaj jatka.oppimi...@gmail.com wrote:
For linklist? How
On Sat, Jul 23, 2011 at
Cannot be done in O(N) if elements of list can take any value because then
counting sort wont help
On Sat, Jul 23, 2011 at 1:24 AM, Pankaj jatka.oppimi...@gmail.com wrote:
For linklist? How
On Sat, Jul 23, 2011 at 1:23 AM, Kamakshii Aggarwal kamakshi...@gmail.com
wrote:
use counting
n logn merge sort.count sort only when range is known.
On Sat, Jul 23, 2011 at 1:35 AM, sunny agrawal sunny816.i...@gmail.comwrote:
Cannot be done in O(N) if elements of list can take any value because then
counting sort wont help
On Sat, Jul 23, 2011 at 1:24 AM, Pankaj
counting sort ll help to some extent... find the min and max element O(n)
now u just need an array of size max-min to store the values then
just traverse the list and while updating u do value+min... still it is not
suitable if the magnitude is high.
On Sat, Jul 23, 2011 at 9:45 AM,
10^9--10^9 - 8- 7- NULL . It wont help in this case...
On Sat, Jul 23, 2011 at 9:55 AM, keyan karthi keyankarthi1...@gmail.comwrote:
counting sort ll help to some extent... find the min and max element O(n)
now u just need an array of size max-min to store the values then
just
20 matches
Mail list logo
