Para entender o princípio de operação dessa classificação "de várias bandas", é mais fácil começar com um exemplo de uma bandeira com três faixas. E, para lidar facilmente com a bandeira de três cores, é melhor ver primeiro como ela funciona com o exemplo de duas cores.
E para lidar com duas cores ... 
Este artigo foi escrito com o apoio da EDISON.
Estamos engajados na migração e migração de software , bem como no desenvolvimento de aplicativos móveis Android e iOS .
Adoramos a teoria dos algoritmos! ;-)
Bandeira de duas cores
Primeiro, considere o caso quando os números na matriz classificada são distribuídos em apenas dois bits. Para simplificar, assumimos que temos uma matriz de zeros (ordem baixa) e uns (ordem alta).
Assim, temos apenas duas "bandas": em uma, moveremos os bits menos significativos (zeros) e, na outra, os bits mais altos (unidades). Qualquer sinalizador de duas cores irá para demonstração. Por exemplo, a bandeira da Ucrânia.
O que está acontecendo aqui? Como no primeiro estágio não se sabe quantos zeros e quantas unidades temos, não está claro em que tamanhos cada uma das "bandas" terminará. Portanto, colocamos dois ponteiros nas chaves da matriz. Para a ordem baixa, o ponteiro é definido para o início da matriz, para a ordem alta até o fim. Em seguida, fazemos uma única passagem pela matriz da esquerda para a direita e olhamos para cada elemento do bit.
Se durante a passagem um elemento é igual à ordem mais alta, o segundo ponteiro nos diz para onde transferir esse elemento (fazemos uma troca). O ponteiro para inserir o próximo elemento se move para a esquerda; a "faixa" do dígito sênior foi expandida.
Se for igual ao dígito menos significativo, movemos o ponteiro para um elemento à direita. Como temos apenas dois dígitos, não é necessário transferir o elemento, ele já está em seu lugar. A “faixa” para a categoria mais jovem naturalmente se tornou mais ampla.
Como resultado, dois ponteiros se movendo um contra o outro colidirão em um ponto e as descargas serão ordenadas em suas “bandas”. Você não precisa percorrer toda a matriz. Quando os ponteiros se encontram em algum lugar no meio, o algoritmo faz seu trabalho.
O problema da bandeira nacional holandesa :: Problema da bandeira nacional holandesa
Para complicar um pouco a tarefa, considere não dois dígitos, mas três. Vamos fazer com que os elementos da matriz pertençam aos dígitos mais baixos (zeros), médios (unidades) e seniores (dois).
Para demonstração, levamos a bandeira vermelha, branca e azul de três vias da
França, Luxemburgo da Rússia e Schleswig-Goldstein da Holanda. Por que exatamente a bandeira da Holanda? Porque Edsger Dijkstra, em suas palestras sobre o exemplo dessa bandeira, examinou o algoritmo correspondente, que foi chamado de "a tarefa da bandeira nacional holandesa".
Como você pode ver, não há nada particularmente novo. Cada categoria tem seu próprio ponteiro. Inicialmente, os rótulos para junior e middle ocupam as posições iniciais no início da matriz e se movem para a direita quando o elemento correspondente é encontrado. O ponteiro para a ordem alta é o primeiro no final da matriz e se move para a esquerda.
A passagem pelo array também estará incompleta, se os bits forem distribuídos de maneira mais ou menos uniforme, o algoritmo passará por 2/3 do array antes de espalhar todos os elementos em suas “bandas”.
Tipo de bandeira americana :: Tipo de bandeira americana
Agora, em nossas explicações, podemos passar para a bandeira americana multibanda.
Quando não temos dois, nem três, mas qualquer número de dígitos, fixamos onde cada dígito deve começar (sua "banda") e redesenhamos os elementos em suas "bandas".
Nesse algoritmo, os números geralmente são considerados não como decimais, mas com uma profundidade de bits diferente, sendo na maioria das vezes uma potência de dois. Freqüentemente, o número 256 é tomado como base para a profundidade de bits (um pouco menos que 128), o que permite adaptar com eficiência a classificação para organizar as strings. Para números com profundidade de bits, é mais conveniente usar 2
n pequenos (2, 4, 16 etc.), o que permite comparar deslocando-se por bits, em vez de aumentar a potência ao comparar números decimais.
A animação mostra um exemplo de profundidade de bits com base 16:
- Na primeira passagem - pesquise o máximo para determinar o número máximo de bits entre os elementos da matriz (para extrair corretamente os bits determinados da conta dos elementos).
- Em seguida, ocorre o processamento recursivo. Quando chamado, os limites da sub-matriz e o bit processado atual são indicados. Na primeira chamada, toda a matriz é uma sub-matriz; o primeiro bit à esquerda é obtido.
- Entre os elementos da sub-matriz, é realizado um cálculo inicial - quantas vezes cada dígito ocorre na categoria atual. Essa contagem permite determinar a localização desses dígitos dos dígitos (ou seja, são conhecidos os limites e a localização da "banda" para a qual você deseja mover os elementos que têm o próximo dígito em um dígito específico). De fato, as localizações são ponteiros para "bandas" onde os elementos correspondentes precisam ser movidos.
- De acordo com os indicadores de localização, ocorre uma troca no local - o dígito na categoria mostra para onde o item precisa ser enviado, outro elemento com o qual a troca ocorreu. Essa cláusula é executada até que, na próxima troca, um elemento que chegue de outro local não esteja em seu lugar (então você pode passar para o próximo elemento do subarray e executar essa cláusula da mesma forma).
- Depois que, como resultado das trocas, os elementos foram redistribuídos em blocos por números no próximo dígito, ocorre uma recursão - o mesmo algoritmo é aplicado a cada bloco como uma sub-matriz e o próximo é o dígito atual.
No artigo sobre
contagem de classificações com uma distribuição aproximada, existe um algoritmo visualmente muito semelhante -
classificação por aproximação . Contamos quantas vezes cada número na matriz ocorreu - e redistribuímos os elementos de acordo com as localizações obtidas. Aqui, contamos quantas vezes cada dígito na categoria ocorre para elementos da sub-matriz - e também redistribuímos os elementos na sub-matriz de acordo com as localizações obtidas. Se a aproximação for uma espécie de classificação de contagem, então "americano" será uma classificação de bits de contagem.
Classificação da Bandeira Americana - Implementação em Python Ska sort :: Ska sort
O programador alemão Malte Skarupke anunciou que desenvolveu um novo algoritmo de classificação, que é uma “bandeira americana” radicalmente aprimorada e supera
std :: sort em média 2 vezes (std :: sort - um algoritmo também conhecido como
classificação introspectiva - um híbrido de
classificação e
classificação rápidas por heap ).
- A matriz é classificada recursivamente, no primeiro nível de recursão, toda a matriz é tomada como uma sub-matriz.
- Se o subarray tiver menos de 128 elementos, std :: sort será chamado.
- Se a sub-matriz contiver de 128 a 1024 elementos, a classificação da bandeira americana será solicitada.
- Se houver mais de 1024 elementos em uma sub-matriz, a classificação de ska será solicitada.
- Além disso, para evitar o pior caso, se o aninhamento recursivo for muito grande (mais de 16 níveis), o algoritmo alterna para std :: sort , mesmo se houver mais de 128 elementos na sub-matriz.
Aparentemente, é um algoritmo muito eficaz e, ao mesmo tempo, extremamente complexo - a implementação do autor leva quase mil e quinhentas linhas. Talvez um dia consideremos essa classificação, agora não entraremos nela. Os interessados podem clicar nos links abaixo.
Referências
Problema da bandeira nacional holandesa ,
tipo de bandeira americanaTipo Ska: 
Escrevi um algoritmo de classificação mais rápida (
Parte 1 ,
Parte 2 )
Código do GithubArtigos da série:
No aplicativo AlgoLab Excel, classificando por um sinalizador de duas cores (classifica zeros e uns), um sinalizador de três cores (classifica zeros, uns e duques), sendo exibido pela classificação americana. Para classificar a "bandeira americana", você pode (em um comentário na célula com o nome do algoritmo) especificar o sistema numérico para distribuição - o padrão é hexadecimal.