[Tutor] stable algorithm

[David Hláčik]

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 <alan.gauld at btinternet.com> wrote:
> "David Hlácik" <david at hlacik.eu> 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  -  Tutor at python.org
> http://mail.python.org/mailman/listinfo/tutor
>