[OT] stable algorithm with complexity O(n)

[David Hláčik]

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 11:24 AM, Arnaud Delobelle
<arnodel at googlemail.com> wrote:
> Steven D'Aprano <steve at REMOVE-THIS-cybersource.com.au> writes:
>
>> On Sat, 13 Dec 2008 19:17:41 +0000, Duncan Booth wrote:
>>
>>> I think you must have fallen asleep during CS101. The lower bound for
>>> sorting where you make a two way branch at each step is O(n * log_2 n),
>>> but if you can choose between k possible orderings in a single
>>> comparison you can get O(n * log_k n).
>>
>> I think you might have been sleeping through Maths 101 :-)
>>
>> The difference between log_2 N and log_k N is a constant factor (log_2 k)
>> and so doesn't effect the big-oh complexity.
>
> It affects it if k is a function of n.  In this particular example, we
> can set k=n so we get O(n).
>
> --
> Arnaud
> --
> http://mail.python.org/mailman/listinfo/python-list
>