[CentOS] [OT] stable algorithm with complexity O(n)

Sun Dec 14 21:02:51 UTC 2008
David Hláčik <david at hlacik.eu>

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 at imag.fr> 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 at centos.org
> http://lists.centos.org/mailman/listinfo/centos
>