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 7:49 PM, Nicolas Thierry-Mieg Nicolas.Thierry-Mieg@imag.fr wrote:
Jerry Franz wrote:
Nicolas Thierry-Mieg wrote:
Jerry Franz wrote:
Marko Vojinovic wrote: [...]
Basically, count the number of appearances of every number in your set. If you have a set a priori bounded from above and below --- which you do, [1, n^2] --- you first allocate an array of integers of length n^2.
By definition, your proposed algorithm is O(n^2), not O(n).
No it isn't, it's O(n) in time. O(n^2) in memory but that wasn't the question, right?
Look closer at it.
"[...] you first allocate an array of integers of length n^2. Set all elements to zero," [...] go through the whole set from 1 to n^2, and if the value of k-th element is nonzero, print number k appropriate number of times. [...]"
O(n^2) operations are required. It is O(n^2) both in time and memory as described.
oh, I see thanks for explaining! _______________________________________________ CentOS mailing list CentOS@centos.org http://lists.centos.org/mailman/listinfo/centos