Thank you guys for help and support! My homework is done and waiting
for grading.
Here it comes - bucket sort with time complexity O(n) == linear complexity
#! /usr/bin/python
def sort(numbers):
"sort n positive integers in O(n) provided that they are all from
interval [1, n^2]"
N = len(numbers) # get size of test numbers
buckets_mod = [[] for i in xrange(N)]
buckets_sorted = [[] for i in xrange(N+1)]
# group numbers to buckets (list of numbers) with common modulus
for n in numbers:
buckets_mod[n % N].append(n)
print "buckets_mod: %s" % buckets_mod
# check numbers in buckets
for l in buckets_mod:
for n in l:
# place number into bucket number grouped by result of
division
buckets_sorted[n / N].append(n)
print "buckets_sorted: %s" % buckets_sorted
# search through sorted buckets and return list of sorted numbers
return [n for l in buckets_sorted for n in l]
Regards,
David
On Sun, Dec 14, 2008 at 11:24 AM, Arnaud Delobelle
<arno...@googlemail.com> wrote:
> Steven D'Aprano <st...@remove-this-cybersource.com.au> writes:
>
>> On Sat, 13 Dec 2008 19:17:41 +0000, Duncan Booth wrote:
>>
>>> I think you must have fallen asleep during CS101. The lower bound for
>>> sorting where you make a two way branch at each step is O(n * log_2 n),
>>> but if you can choose between k possible orderings in a single
>>> comparison you can get O(n * log_k n).
>>
>> I think you might have been sleeping through Maths 101 :-)
>>
>> The difference between log_2 N and log_k N is a constant factor (log_2 k)
>> and so doesn't effect the big-oh complexity.
>
> It affects it if k is a function of n. In this particular example, we
> can set k=n so we get O(n).
>
> --
> Arnaud
> --
> http://mail.python.org/mailman/listinfo/python-list
>
--
http://mail.python.org/mailman/listinfo/python-list
