Re: stable algorithm with complexity O(n)

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



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 4:08 PM, Ed Greshko <Ed.Greshko@xxxxxxxxxxx> wrote:
> Aaron Konstam wrote:
>> On Sun, 2008-12-14 at 12:10 +1100, Cameron Simpson wrote:
>>
>>> | There is the generation counter algorithm. It is O(n), and relies on
>>> the fact
>>> | that one knows the boundaries of the possible elements of the
>>> dataset (and
>>> | it's domain). Basically, you simply count the number of appearances
>>> of every
>>> | element in your set. It's just a single for-loop.
>>>
>> I am not on the Centos list either not do I understand the sorting
>> algorithm you describe above. Could you expand on the explanation above.
>>
>>
> FWIW, a judicious google search answered all of my questions on this
> sort of thing.  :-)
>
> --
> Goals... Plans... they're fantasies, they're part of a dream world... --
> Wally Shawn Mei-Mei.Greshko@xxxxxxxxxxx
>
>
> --
> fedora-list mailing list
> fedora-list@xxxxxxxxxx
> To unsubscribe: https://www.redhat.com/mailman/listinfo/fedora-list
> Guidelines: http://fedoraproject.org/wiki/Communicate/MailingListGuidelines
>

-- 
fedora-list mailing list
fedora-list@xxxxxxxxxx
To unsubscribe: https://www.redhat.com/mailman/listinfo/fedora-list
Guidelines: http://fedoraproject.org/wiki/Communicate/MailingListGuidelines
[Index of Archives]     [Older Fedora Users]     [Fedora Announce]     [Fedora Package Announce]     [EPEL Announce]     [Fedora Magazine]     [Fedora News]     [Fedora Summer Coding]     [Fedora Laptop]     [Fedora Cloud]     [Fedora Advisory Board]     [Fedora Education]     [Fedora Security]     [Fedora Scitech]     [Fedora Robotics]     [Fedora Maintainers]     [Fedora Infrastructure]     [Fedora Websites]     [Anaconda Devel]     [Fedora Devel Java]     [Fedora Legacy]     [Fedora Desktop]     [Fedora Fonts]     [ATA RAID]     [Fedora Marketing]     [Fedora Management Tools]     [Fedora Mentors]     [SSH]     [Fedora Package Review]     [Fedora R Devel]     [Fedora PHP Devel]     [Kickstart]     [Fedora Music]     [Fedora Packaging]     [Centos]     [Fedora SELinux]     [Fedora Legal]     [Fedora Kernel]     [Fedora OCaml]     [Coolkey]     [Virtualization Tools]     [ET Management Tools]     [Yum Users]     [Tux]     [Yosemite News]     [Gnome Users]     [KDE Users]     [Fedora Art]     [Fedora Docs]     [Asterisk PBX]     [Fedora Sparc]     [Fedora Universal Network Connector]     [Libvirt Users]     [Fedora ARM]

  Powered by Linux