"David Hlácik" <[email protected]> wrote
yes it is homework , this is result :
#! /usr/bin/python
def sort(numbers):
"sort n positive integers in O(n) provided that they are all
< 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
It would be interesting to see if using a dictionasry aws a sparce
array was any faster - it would save the initialisation step and
reduce the number of accesses of empty lists.
# check numbers in buckets
for l in buckets_mod:
for n in l:
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]
Hope it is optimal and OK, what you guys thinks?
Its almost certainly not optimal but from some basic testing it seems
to
work and is linear as far as I can see (albeit with 5 loops over N).
Alan G
_______________________________________________
Tutor maillist - [email protected]
http://mail.python.org/mailman/listinfo/tutor
