Nas classificações de distribuição, os elementos são distribuídos e redistribuídos em classes até que a matriz seja classificada.
No caso mais geral, isso acontece aproximadamente da mesma maneira. Os elementos são dispersos por classes de acordo com algum critério. Se isso não levar à ordem da matriz, os atributos da classe serão refinados e os elementos serão espalhados novamente para as classes refinadas. E isso acontece até que a matriz seja ordenada.
Nas ordenações por distribuição, quase sempre não há comparações de elementos entre si e suas trocas. O principal é se o elemento pertence a uma determinada classe ou não, sua comparação com outros elementos raramente desempenha um papel.
Normalmente, esses tipos têm complexidade de tempo linear (em vez de logarítmica, como ocorre com tipos eficientes de trocas, mesclagens, escolhas ou inserções). Além disso, os algoritmos dessa classe quase sempre exigem muita memória adicional, pois os elementos agrupados por classes precisam ser armazenados em algum lugar.
As classificações de distribuição são boas para classificar números inteiros e seqüências de caracteres. Classificar números reais com eles geralmente é inconveniente. Além disso, as ordenações de distribuição ordenam perfeitamente matrizes que consistem em números repetidos - quanto mais repetições, menos classes diferentes são necessárias.
Este artigo foi escrito com o apoio da EDISON.
Opinião dos clientes: 10 vantagens dos programadores da EDISON
É interessante e útil saber: Programador de café da manhã
Considere um algoritmo que demonstre mais convexamente as propriedades acima.
Classificação de caçamba :: Classificação de caçamba
Outros nomes são classificação de cesta, classificação de bloco e classificação de bolso.
Nós dispersamos números em cestas, depois em cada cesta nós dispersamos em cestas menores, e assim por diante, até que em algum nível na cesta haja apenas os mesmos elementos. Então, a partir dessas cestas do nível mais baixo, é fácil restaurar a matriz em um estado ordenado.
Vamos explicar com um exemplo específico. Digamos que temos uma matriz não ordenada. Sabe-se que essa matriz contém números de 1 a 8.
Jogamos esses números em 2 grupos: números de 1 a 4 se enquadram em um grupo, de 5 a 8. No segundo, distribuímos os números na primeira cesta em duas cestas: em um número 1 e 2 e nos outros 3 e 4. Também distribuímos essas cestas em cestas bast, que já contêm números do mesmo tamanho. Para essa cesta grande contendo números de 5 a 8, aplicamos uma recursão semelhante.
Então, de pequenas cestas, cada uma das quais contém os mesmos números, retornamos os elementos para a matriz principal em ordem de precedência.
A classificação nuclear desta forma não é particularmente aplicável na prática, mas demonstra de maneira padrão como todas as classificações por distribuição funcionam em geral.
Classificação de Thanos :: Classificação de Thanos
Às vezes, tipos de autores são enviados para mim e esse é apenas o caso. O autor Andrei Danilin chamou de "classificação russa ao meio", no entanto, eu a denominei a classificação de Thanos. Ou, se formalmente prosseguirmos com os métodos utilizados, podemos chamar sua classificação média aritmética.
A média aritmética dos elementos é calculada na matriz e, em seguida, todos os elementos são distribuídos em 2 grupos. Em um grupo, há elementos menores (ou iguais) à média aritmética, no segundo grupo - elementos maiores que a média aritmética. Em seguida, as mesmas ações são aplicadas recursivamente aos dois grupos - e assim por diante até o fim.
E o titânio louco? Se esse é um arranjo aleatório, em geral o elemento, quando comparado com a média aritmética, tem 50/50 de chance de ir para um dos dois grupos.
Aliás, na Internet me deparei com outro algoritmo cômico com o mesmo nome. Se a matriz não for classificada, clique no Infinity Glove e envie metade dos elementos da matriz selecionados aleatoriamente para a inexistência. Se os sobreviventes formarem uma matriz ordenada, então sua grande missão poderá ser considerada cumprida. Se ainda não estiver, você pode fazer mais alguns cliques.
Mas voltando às nossas classificações de distribuição. Todos eles podem ser divididos em apenas dois grupos -
contando classificações e
classificação bit a bit . Bem, se você quiser, também pode destacar
as classificações de bits de contagem , ou seja, aqueles que podem ser atribuídos a ambos.
Também existem algoritmos híbridos (aqueles que usam métodos de classes diferentes, por exemplo, a classificação de Tim é uma mistura entre classificação de mesclagem e classificação de inserção, classificação introspectiva é uma classificação rápida que entra em uma classificação de grupo etc.), incluindo classificações de distribuição No entanto, os híbridos são uma seção separada. Sobre eles mais tarde.
Milhares de classificação e classificação aritmética estão relacionadas às classificações de contagem.
Classes de contagem
A idéia básica é que contemos quantos números existem em cada classe.
Classificação de contagem :: Classificação de contagem
Contamos quantas vezes um ou outro número ocorre na matriz. Conhecendo essas quantidades, formamos rapidamente uma matriz já ordenada.
Para essa classificação, você precisa saber o mínimo e o máximo na matriz. Em seguida, as chaves são geradas para o array auxiliar, no qual corrigimos o que e quantas vezes ele se encontrou.
Código Python:
def CountingSort(array, mn, mx): count = defaultdict(int) for i in array: count[i] += 1 result = [] for j in range(mn,mx+1): result += [j]* count[j] return result
Classificação de pombos :: Classificação de pombos
Percorremos a matriz, se um novo número for encontrado, então iniciaremos o contador (como a chave da lista auxiliar) desse número. Se o número não for encontrado pela primeira vez, o incremento para esse contador é simplesmente acionado.
A diferença do método anterior é que, na classificação por contagem, iniciamos imediatamente os contadores para todos os números possíveis que possam ocorrer na matriz (podemos pagar se o máximo e o mínimo na matriz forem conhecidos). Alguns números nunca aparecem e seus contadores mostram zero. Na classificação de pombos, iniciamos os contadores apenas para os números que realmente ocorrem na matriz. Uma matriz é usada na contagem de classificação de contadores e uma lista duplamente vinculada é usada na classificação de pombos, o que permite adicionar novos contadores em movimento.
Às vezes, esse método é chamado de
classificação de Dirichlet , porque o próprio algoritmo é uma ilustração de várias consequências do princípio de Dirichlet.
Se N objetos estiverem distribuídos entre M contêineres e N> M, pelo menos um contêiner conterá mais de um elemento.
Código Python:
def PigeOnHoleSort(a): mi = min(a) size = max(a) - mi + 1 holes = [0] * size for x in a: holes[x - mi] += 1 i = 0 for count in range(size): while holes[count] > 0: holes[count] -= 1 a[i] = count + mi i += 1
Classificação de bits
Distribuímos os números, dependendo de qual dígito está em uma categoria específica do número. Se fizermos isso várias vezes para dígitos diferentes, subitamente obteremos uma matriz classificada.
Classificação de bits em ordem baixa: classificação de radix LSD
Passamos dos dígitos inferiores para os mais antigos e, a cada iteração, distribuímos os elementos da matriz, dependendo de qual dígito está no dígito.
Após a próxima distribuição, retornamos os elementos para a matriz principal na ordem em que os elementos caíram nas classes durante a próxima redistribuição.
Para classificações bit a bit, é importante que os elementos sejam considerados com o mesmo número de dígitos. Se o número real de dígitos for diferente, o problema será resolvido adicionando zeros adicionais como dígitos mais altos.
Classificação bit a bit de alta ordem: classificação do MSD radix
Primeiro, distribuímos entre os escalões seniores, dos quais passamos para os mais jovens.
Essa opção é mais difícil de implementar, pois a transição para os dígitos inferiores é realizada recursivamente dentro das classes, e não entre todos os elementos da matriz.
Mas essa complexidade é recompensada pelo fato de o MSD ser mais rápido que o LSD. Ao passar dos dígitos inferiores para os mais antigos, é necessário processar todos os dígitos de todos os números para classificar corretamente. Se você passa de sênior para mais jovem, na verdade não precisa processar todos os dígitos de todos os números, o estado classificado, em regra, ocorre mais cedo.
A maioria das classificações bit a bit é uma variação do MSD mais eficiente. Isso é especialmente útil para classificar seqüências de caracteres; para isso, geralmente é usada uma árvore de sufixos. Analisaremos em um dos seguintes artigos.
Contando classificações bit a bit
Às vezes, a classificação da distribuição é simultaneamente contável e bit a bit.
Classificação do grânulo :: Classificação do grânulo
Outros nomes do algoritmo: classificação de ábaco, classificação por gravidade.
Eu já escrevi sobre isso algumas vezes (
1 ,
2 ), então serei breve, apenas a essência.
Suponha que cada número em uma matriz seja um conjunto de bolas, o número de bolas seja o valor de um número. Se organizarmos os números um sobre o outro como linhas horizontais dessas bolas e empurrá-los na vertical, obteremos uma matriz ordenada.
O truque aqui é que representamos cada número usando bolas em um sistema numérico unário. De fato, contamos quantas vezes todos os números têm cada dígito.
BeadSort em Python em uma linha:
Depois de um tempo, analisaremos classificações mais complexas de contagem em bits, entre as quais a classificação da
bandeira americana ocupa um lugar de destaque.
Referências
Baldes /
Baldes ,
Contagem /
Buraco /
Dirichlet ,
Raízes /
Descargas ,
TalãoArtigos da série:
O aplicativo AlgoLab Excel foi significativamente atualizado. Alguns algoritmos do artigo de hoje apareceram lá pela primeira vez. Atualize quem está usando.