Classificação de contagem

Classificação de contagem – algoritmo de classificação de contagem. Em termos de? Sim! Simples assim!

O algoritmo envolve pelo menos dois arrays, o primeiro – lista de inteiros a serem classificados, segundo – uma matriz de tamanho = (número máximo – número mínimo) + 1, contendo inicialmente apenas zeros. Em seguida, os números são classificados na primeira matriz e o elemento numérico é usado para obter um índice na segunda matriz, que é incrementado em um. Depois de percorrer toda a lista, obteremos um segundo array completamente preenchido com o número de repetições dos números do primeiro. O algoritmo tem uma séria sobrecarga – a segunda matriz também contém zeros para números que não estão na primeira lista, a chamada. sobrecarga da memória

Após receber o segundo array, iteramos por ele e escrevemos a versão ordenada do número por índice, decrementando o contador a zero. Inicialmente, um contador zero é ignorado.

Um exemplo de operação não otimizada do algoritmo de classificação por contagem:

1. Matriz de entrada 1,9,1,4,6,4,4
2. Então o array a ser contado será 0,1,2,3,4,5,6,7,8,9 (número mínimo 0, máximo 9)
3. Com contadores totais 0,2,0,0,3,0,1,0,0,1
4. Matriz classificada total 1,1,4,4,4,6,9

Código do algoritmo em Python 3:

numbers = [42, 89, 69, 777, 22, 35, 42, 69, 42, 90, 777]

minimal = min(numbers)
maximal = max(numbers)
countListRange = maximal - minimal
countListRange += 1
countList = [0] * countListRange

print(numbers)
print(f"Minimal number: {minimal}")
print(f"Maximal number: {maximal}")
print(f"Count list size: {countListRange}")

for number in numbers:
    index = number - minimal
    countList[index] += 1

replacingIndex = 0
for index, count in enumerate(countList):
    for i in range(count):
        outputNumber = minimal + index
        numbers[replacingIndex] = outputNumber
        replacingIndex += 1

print(numbers)

Published by demensdeum

View all posts by demensdeum