Surprising (for me) benchmark results...
Brian Quinlan
BrianQ at ActiveState.com
Wed May 2 20:04:20 EDT 2001
> There are O(N) sorting algorithms?? I thought that was restricted to
> quantum computation.
Actually, there are O(N) sorting algorithms. Counting sort is O(N). The
algorithm is simple but only works in (small) descrete element spaces. The
following example works with integers:
def sort( A, k ):
b = []
c = []
for i in range(k):
c.append(0)
for j in A:
c[j] += 1
for i in range(len(c)):
b += [i] * c[i]
return b
print sort( [1,2,2,2,2,5,4,3,2,2,2,5], 6 )
>>> [1, 2, 2, 2, 2, 2, 2, 2, 3, 4, 5, 5]
BTW, this isn't an efficient implementation so don't use it or anything :-)
More information about the Python-list
mailing list