Diskussion:Algorithmensammlung: Sortierverfahren: Countingsort

Der Python-Code scheint mir unnötig "kompliziert" zu sein:

def counting_sort(A):
    C = [0] * (max(A)+1)
    B = [""] * len(A)
    for index in xrange(len(A)):
        C[A[index]]+=1
    for index in xrange(1, len(C)):
        C[index]+=C[index-1]
    for index in xrange(len(A)-1, -1, -1):
        B[C[A[index]]-1]=A[index]
        C[A[index]]-=1
    return B

Hier ist eine bessere Variante:

def counting_sort(A):
    C = [0] * (max(A)+1)
    B = [""] * len(A)
    for el in A:
        C[el] += 1
    for index in xrange(1, len(C)):
        C[index] += C[index-1]
    for el in A[::-1]:
        B[C[el]-1] = el
        C[el] -= 1
    return B

Noch besser ist es mit Kommentaren:

def countingsort(A):
    """ 
        Sort the list A.

        Every element of the list A has to be non-negative.

        @param A: the list that should get sorted
        @return the sorted list
    """
    if len(A) == 0:
        return []

    C = [0] * (max(A)+1)
    B = [""] * len(A)

    # Count the number of elements
    for el in A:
        C[el] += 1
    # Now C[i] contains how often i is in A

    for index in xrange(1, len(C)):
        C[index] += C[index-1]

    for el in A[::-1]:
        B[C[el]-1] = el
        C[el] -= 1

    return B

Grüße, --moose 17:18, 24. Jul. 2012 (CEST)