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@xxxxxxx> 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@xxxxxxxxxx
> http://lists.centos.org/mailman/listinfo/centos
>
_______________________________________________
CentOS mailing list
CentOS@xxxxxxxxxx
http://lists.centos.org/mailman/listinfo/centos
