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 3:05 AM, Ben Schmidt
<[email protected]> wrote:
>
>>> Well, it would require looking at each element only a constant number of
>>> times.
>>
>> ...or even a bounded number of times
>
> That's what the word 'only' above was supposed to convey. Good
> clarification, though.
>
> Ben.
>
>
>
>
> >
>
--~--~---------~--~----~------------~-------~--~----~
You received this message from the "vim_use" maillist.
For more information, visit http://www.vim.org/maillist.php
-~----------~----~----~----~------~----~------~--~---
