[algogeeks] Re: Sorting Array
Radix sort can solve the problem in O(N) time. Max. value of input is N^2 so in binary representation, we need d = 2(logN)+1 digits to represent each number. ( It is O(logN) - thats the key) Now group logN bits ( say r = logN ) The maximum value in each group is O( 2^r) This is the base in which we will do radix sort. No of digits in this new base = d/r Max value of each digit in this new base = 2^r Time taken for radix sort: O( No. of digits * ( Time for sorting each digit ) ) Time for sorting N numbers on one digit = O(n+2^r) So total time = O( d/r * (n+2^r) ) By the choice of d and r, we get Time = O(N). Infact this will work any range polynomial in N. Note that this is just a theoretical analysis and in general Quick sort beats Radix sort in practice because of the hidden constant factors On Jun 28, 9:55 pm, L wrote: > There is one way in which we can do O(n). > Convert the numbers in base 'n'. [ O(n) ]. > Now, there are 2-digit numbers, each digit ranging from 0 to n-1. > You can call count-sort 2 times (for each digit), so, complexity is O(n > +n) =O(n). > > On Jun 27, 12:22 am, Dan wrote: > > > Your question is good for a classroom style discussion/debate. > > However, in the real world, there is no simple answer. > > > There are lots of sorting algorithms. Each one has it's pros & cons > > and no single sorting algorithm is "best", especially when not much is > > known about the data to be sorted. In your case about all that > > we really know is that there are no negative numbers involved. I > > don't think that helps very much (any?). Then... you need to > > consider the programming language and computer system used for the > > implementation. Yes. They do matter. Sometimes, they matter a > > LOT. Don't assume that an O(x) algorithm is better than an O(y) > > algorithm just because x is less than y. > > > Dan :-) > > > On Jun 26, 12:14 am, ross wrote: > > > > Given a sequence of numbers in the range of 1-N^2, what is the most > > > efficient way to sort the numbers (better than NlgN).. > > > Can counting sort be used here? Is an O(N) solution possible.. -- 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 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 Array
There is one way in which we can do O(n). Convert the numbers in base 'n'. [ O(n) ]. Now, there are 2-digit numbers, each digit ranging from 0 to n-1. You can call count-sort 2 times (for each digit), so, complexity is O(n +n) =O(n). On Jun 27, 12:22 am, Dan wrote: > Your question is good for a classroom style discussion/debate. > However, in the real world, there is no simple answer. > > There are lots of sorting algorithms. Each one has it's pros & cons > and no single sorting algorithm is "best", especially when not much is > known about the data to be sorted. In your case about all that > we really know is that there are no negative numbers involved. I > don't think that helps very much (any?). Then... you need to > consider the programming language and computer system used for the > implementation. Yes. They do matter. Sometimes, they matter a > LOT. Don't assume that an O(x) algorithm is better than an O(y) > algorithm just because x is less than y. > > Dan :-) > > On Jun 26, 12:14 am, ross wrote: > > > > > > > > > Given a sequence of numbers in the range of 1-N^2, what is the most > > efficient way to sort the numbers (better than NlgN).. > > Can counting sort be used here? Is an O(N) solution possible.. -- 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 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 Array
Your question is good for a classroom style discussion/debate. However, in the real world, there is no simple answer. There are lots of sorting algorithms. Each one has it's pros & cons and no single sorting algorithm is "best", especially when not much is known about the data to be sorted. In your case about all that we really know is that there are no negative numbers involved. I don't think that helps very much (any?). Then... you need to consider the programming language and computer system used for the implementation. Yes. They do matter. Sometimes, they matter a LOT.Don't assume that an O(x) algorithm is better than an O(y) algorithm just because x is less than y. Dan :-) On Jun 26, 12:14 am, ross wrote: > Given a sequence of numbers in the range of 1-N^2, what is the most > efficient way to sort the numbers (better than NlgN).. > Can counting sort be used here? Is an O(N) solution possible.. -- 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 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 Array
u can use radix sort
On Sun, Jun 26, 2011 at 9:44 PM, ross wrote:
> @Divye: Good theoretical proof and analysis as well.. As you
> mentioned, this one works like charm for uniformly distributed
> inputs :)
>
> On Jun 26, 8:36 pm, DK wrote:
> > Use a radix sort.
> > Complexity of the radix sort is O(N k) where k is the number of digits
> used
> > to represent the number in some base b.
> > If we use the convenient fiction that both N and N^2 fit into the same 32
> > bit integer then
> > k is a constant and we get an O(N) sort. (It's kindof cheating :) ).
> > Okay, since we don't want to cheat on this one, keep reading below: :)
> >
> > Another method is to divide the Numbers into N bins of size N numbers.
> > Eg. Bin 1 = 1 to N, Bin 2 = N+1 to 2N ...
> > Assuming uniform distribution, the bins will have N/N ~ 1 element each.
> > If the distribution is non-uniform then no bin will have more than N
> > elements.
> >
> > For small bins, apply a variant of insertion sort (which performs faster
> > than O(n log n) sorts for < 12 elements) and if N is large, will perform
> > much faster than counting sort.
> > For large bins, apply an O(n log n) sort or radix sort or counting sort.
> > (make a choice depending on number of elements in the bin. eg.
> Num_elements
> > ~ N then choose counting sort, else choose radix or O(n log n) sorts)
> >
> > Complexity analysis:
> > 1. No bin will have more than N elements.
> > 2. No bin while being sorted will have a range > N.
> >
> > If the data distribution is uniform, the solution will be very very quick
> > (order of N) as the sorting time for bins with just 2 to 3 elements is
> > approximately O(num_elements) ~ O(1) and number of such bins is O(N).
> > If the data distribution is non-uniform, then complexity will depend on
> the
> > number of bad bins and the size of bad bins.
> >
> > Let K bins be bad. Here, K is a value dependent on data distribution of
> the
> > input.
> > If K is small, number of elements per bin is large -> apply counting sort
> on
> > the bins -> complexity O(K N) which is approximately O(N)
> > If K -> log N, apply an O(N log N) sort to the bins -> complexity O( K *
> N/K
> > log (N/K)) -> O(N log (N/log N))
> > If K > log N but K < N, worst case -> complexity Sum over K bins{min{O(Ni
> > log (Ni)), O(N)}} (you can cheat this to O(N) by using something like
> radix
> > sort)
> > If K -> N -> Not possible as you won't have that many bad bins as the
> number
> > of elements per bin will approach 1.
> >
> > So, in short, you can get a complexity of the kind O(N log (N/log N))
> which
> > is slightly better than O(N log N).
> > Hope this helps!
> >
> > --
> > DK
> >
> > http://twitter.com/divyekapoorhttp://www.divye.in
>
> --
> 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 this group, send email to
> algogeeks+unsubscr...@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 algogeeks@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 Array
@Divye: Good theoretical proof and analysis as well.. As you
mentioned, this one works like charm for uniformly distributed
inputs :)
On Jun 26, 8:36 pm, DK wrote:
> Use a radix sort.
> Complexity of the radix sort is O(N k) where k is the number of digits used
> to represent the number in some base b.
> If we use the convenient fiction that both N and N^2 fit into the same 32
> bit integer then
> k is a constant and we get an O(N) sort. (It's kindof cheating :) ).
> Okay, since we don't want to cheat on this one, keep reading below: :)
>
> Another method is to divide the Numbers into N bins of size N numbers.
> Eg. Bin 1 = 1 to N, Bin 2 = N+1 to 2N ...
> Assuming uniform distribution, the bins will have N/N ~ 1 element each.
> If the distribution is non-uniform then no bin will have more than N
> elements.
>
> For small bins, apply a variant of insertion sort (which performs faster
> than O(n log n) sorts for < 12 elements) and if N is large, will perform
> much faster than counting sort.
> For large bins, apply an O(n log n) sort or radix sort or counting sort.
> (make a choice depending on number of elements in the bin. eg. Num_elements
> ~ N then choose counting sort, else choose radix or O(n log n) sorts)
>
> Complexity analysis:
> 1. No bin will have more than N elements.
> 2. No bin while being sorted will have a range > N.
>
> If the data distribution is uniform, the solution will be very very quick
> (order of N) as the sorting time for bins with just 2 to 3 elements is
> approximately O(num_elements) ~ O(1) and number of such bins is O(N).
> If the data distribution is non-uniform, then complexity will depend on the
> number of bad bins and the size of bad bins.
>
> Let K bins be bad. Here, K is a value dependent on data distribution of the
> input.
> If K is small, number of elements per bin is large -> apply counting sort on
> the bins -> complexity O(K N) which is approximately O(N)
> If K -> log N, apply an O(N log N) sort to the bins -> complexity O( K * N/K
> log (N/K)) -> O(N log (N/log N))
> If K > log N but K < N, worst case -> complexity Sum over K bins{min{O(Ni
> log (Ni)), O(N)}} (you can cheat this to O(N) by using something like radix
> sort)
> If K -> N -> Not possible as you won't have that many bad bins as the number
> of elements per bin will approach 1.
>
> So, in short, you can get a complexity of the kind O(N log (N/log N)) which
> is slightly better than O(N log N).
> Hope this helps!
>
> --
> DK
>
> http://twitter.com/divyekapoorhttp://www.divye.in
--
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 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 Array
Use a radix sort.
Complexity of the radix sort is O(N k) where k is the number of digits used
to represent the number in some base b.
If we use the convenient fiction that both N and N^2 fit into the same 32
bit integer then
k is a constant and we get an O(N) sort. (It's kindof cheating :) ).
Okay, since we don't want to cheat on this one, keep reading below: :)
Another method is to divide the Numbers into N bins of size N numbers.
Eg. Bin 1 = 1 to N, Bin 2 = N+1 to 2N ...
Assuming uniform distribution, the bins will have N/N ~ 1 element each.
If the distribution is non-uniform then no bin will have more than N
elements.
For small bins, apply a variant of insertion sort (which performs faster
than O(n log n) sorts for < 12 elements) and if N is large, will perform
much faster than counting sort.
For large bins, apply an O(n log n) sort or radix sort or counting sort.
(make a choice depending on number of elements in the bin. eg. Num_elements
~ N then choose counting sort, else choose radix or O(n log n) sorts)
Complexity analysis:
1. No bin will have more than N elements.
2. No bin while being sorted will have a range > N.
If the data distribution is uniform, the solution will be very very quick
(order of N) as the sorting time for bins with just 2 to 3 elements is
approximately O(num_elements) ~ O(1) and number of such bins is O(N).
If the data distribution is non-uniform, then complexity will depend on the
number of bad bins and the size of bad bins.
Let K bins be bad. Here, K is a value dependent on data distribution of the
input.
If K is small, number of elements per bin is large -> apply counting sort on
the bins -> complexity O(K N) which is approximately O(N)
If K -> log N, apply an O(N log N) sort to the bins -> complexity O( K * N/K
log (N/K)) -> O(N log (N/log N))
If K > log N but K < N, worst case -> complexity Sum over K bins{min{O(Ni
log (Ni)), O(N)}} (you can cheat this to O(N) by using something like radix
sort)
If K -> N -> Not possible as you won't have that many bad bins as the number
of elements per bin will approach 1.
So, in short, you can get a complexity of the kind O(N log (N/log N)) which
is slightly better than O(N log N).
Hope this helps!
--
DK
http://twitter.com/divyekapoor
http://www.divye.in
--
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/-/OCYjpn_zkigJ.
To post to this group, send email to algogeeks@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 Array
@ross: It seems that after discretization , the time complexity still would be O(nlogn). The discretization idea is: say there are 4 numbers, each of them is in the range[1, 16]. e.g. 12 3 12 15 You can do one time transverse to map each of them to a global increasing index (hashing is the appropriate method) 12 ---> 1 3 ---> 2 15 ---> 3 but we still need some data structure to hold the order of the numbers which is still O(nlogn). for this idea, using STL map would be much easier... -- 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 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 Array
@Rujin Cao: Yea, your formulation of the problem is correct.. my bad,. missed that there are N numbers. can u elaborate more on the discretization procedure and how ll u do counting sort (which might warrant traversing of N^2 elements) On Jun 26, 5:45 pm, Rujin Cao wrote: > @ross: > I guess the orignal problem is that there are N numbers which are all in the > range [1, N * N], can you do the sorting in O(N) time complexity? > > If this is true, we can firstly do the discretization and then do the > counting sort. -- 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 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 Array
@ross: I guess the orignal problem is that there are N numbers which are all in the range [1, N * N], can you do the sorting in O(N) time complexity? If this is true, we can firstly do the discretization and then do the counting sort. -- 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 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 Array
@L: It was asked if we could take advantage of the ranges of the integers between 1-N^2.. I doubt if its possible. On Jun 26, 5:33 pm, ross wrote: > @radhakrishnan: Counting sort in this case, will be O(n2).. as it > involves traversing the entire array! > > On Jun 26, 5:03 pm, L wrote: > > > > > > > > > Count sort is O(n+k), since k~n^2 here, it will be O(N^2). > > Radix sort has complexity O(r.n) which is nearly O(n logn). > > Are you sure that the person asking this question wanted O(n) ? > > > On Jun 26, 1:31 pm, radha krishnan > > wrote: > > > > Yes ! Count Sort !! > > > > On Sun, Jun 26, 2011 at 1:44 PM, ross wrote: > > > > Given a sequence of numbers in the range of 1-N^2, what is the most > > > > efficient way to sort the numbers (better than NlgN).. > > > > Can counting sort be used here? Is an O(N) solution possible.. > > > > > -- > > > > 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 this group, send email to > > > > algogeeks+unsubscr...@googlegroups.com. > > > > For more options, visit this group > > > > athttp://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 algogeeks@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 Array
@radhakrishnan: Counting sort in this case, will be O(n2).. as it involves traversing the entire array! On Jun 26, 5:03 pm, L wrote: > Count sort is O(n+k), since k~n^2 here, it will be O(N^2). > Radix sort has complexity O(r.n) which is nearly O(n logn). > Are you sure that the person asking this question wanted O(n) ? > > On Jun 26, 1:31 pm, radha krishnan > wrote: > > > > > > > > > Yes ! Count Sort !! > > > On Sun, Jun 26, 2011 at 1:44 PM, ross wrote: > > > Given a sequence of numbers in the range of 1-N^2, what is the most > > > efficient way to sort the numbers (better than NlgN).. > > > Can counting sort be used here? Is an O(N) solution possible.. > > > > -- > > > 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 this group, send email to > > > algogeeks+unsubscr...@googlegroups.com. > > > For more options, visit this group > > > athttp://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 algogeeks@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 Array
Count sort is O(n+k), since k~n^2 here, it will be O(N^2). Radix sort has complexity O(r.n) which is nearly O(n logn). Are you sure that the person asking this question wanted O(n) ? On Jun 26, 1:31 pm, radha krishnan wrote: > Yes ! Count Sort !! > > > > > > > > On Sun, Jun 26, 2011 at 1:44 PM, ross wrote: > > Given a sequence of numbers in the range of 1-N^2, what is the most > > efficient way to sort the numbers (better than NlgN).. > > Can counting sort be used here? Is an O(N) solution possible.. > > > -- > > 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 this group, send email to > > algogeeks+unsubscr...@googlegroups.com. > > For more options, visit this group > > athttp://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 algogeeks@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.
