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 4:08 PM, Ed Greshko <Ed.Greshko@xxxxxxxxxxx> wrote: > Aaron Konstam wrote: >> On Sun, 2008-12-14 at 12:10 +1100, Cameron Simpson wrote: >> >>> | There is the generation counter algorithm. It is O(n), and relies on >>> the fact >>> | that one knows the boundaries of the possible elements of the >>> dataset (and >>> | it's domain). Basically, you simply count the number of appearances >>> of every >>> | element in your set. It's just a single for-loop. >>> >> I am not on the Centos list either not do I understand the sorting >> algorithm you describe above. Could you expand on the explanation above. >> >> > FWIW, a judicious google search answered all of my questions on this > sort of thing. :-) > > -- > Goals... Plans... they're fantasies, they're part of a dream world... -- > Wally Shawn Mei-Mei.Greshko@xxxxxxxxxxx > > > -- > fedora-list mailing list > fedora-list@xxxxxxxxxx > To unsubscribe: https://www.redhat.com/mailman/listinfo/fedora-list > Guidelines: http://fedoraproject.org/wiki/Communicate/MailingListGuidelines > -- fedora-list mailing list fedora-list@xxxxxxxxxx To unsubscribe: https://www.redhat.com/mailman/listinfo/fedora-list Guidelines: http://fedoraproject.org/wiki/Communicate/MailingListGuidelines
