[Tutor] stable algorithm

[Alan Gauld]

"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