Hi, thank you very much.
And how can i write single test which will tell me execution time of this algorithm? I need to write a table with number of data & execution time comparison (and it should be linear in case of this algorithm) Thanks! D. On Sun, Dec 14, 2008 at 5:58 PM, Alan Gauld <[email protected]> wrote: > "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 > _______________________________________________ Tutor maillist - [email protected] http://mail.python.org/mailman/listinfo/tutor
