Smoothsort - Smoothsort

Smoothsort
Uma animação que descreve a operação de smoothsort, mostrando a pilha sendo construída e, em seguida, desmontada,
Smoothsort operando em uma matriz que está em ordem. As barras na parte superior mostram a estrutura da árvore.
Classe Algoritmo de classificação
Estrutura de dados Variedade
Desempenho de pior caso O ( n log n )
Melhor caso de desempenho O ( n )
Desempenho médio O ( n log n )
Pior caso de complexidade de espaço O ( n ) total, O (1) auxiliar

Em ciência da computação , smoothsort é um algoritmo de classificação baseado em comparação . Uma variante do heapsort , foi inventado e publicado por Edsger Dijkstra em 1981. Como o heapsort, smoothsort é um algoritmo in-loco com um limite superior de O ( n log  n ) , mas não é um tipo estável . A vantagem do smoothsort é que ele se aproxima do tempo O ( n ) se a entrada já estiver classificada em algum grau , enquanto o heapsort tem a média de O ( n log  n ), independentemente do estado inicial classificado.

Visão geral

Como o heapsort , o smoothsort organiza a entrada em uma fila de prioridade e extrai repetidamente o máximo. Também como o heapsort, a fila de prioridade é uma estrutura de dados de heap implícita (uma árvore binária implícita ordenada por heap ), que ocupa um prefixo do array. Cada extração reduz o prefixo e adiciona o elemento extraído a um sufixo classificado crescente. Quando o prefixo é reduzido a nada, a matriz está completamente classificada.

O Heapsort mapeia a árvore binária para o array usando uma passagem de cima para baixo em largura da árvore; a matriz começa com a raiz da árvore, em seguida, seus dois filhos, quatro netos e assim por diante. Cada elemento tem uma profundidade bem definida abaixo da raiz da árvore e cada elemento, exceto a raiz, tem seu pai no início da matriz. Sua altura acima das folhas, entretanto, depende do tamanho da matriz. Isso tem a desvantagem de que cada elemento deve ser movido como parte do processo de classificação: ele deve passar pela raiz antes de ser movido para seu local final.

Smoothsort usa um mapeamento diferente, uma travessia pós-ordem de profundidade de baixo para cima . Um filho à esquerda é seguido pela subárvore enraizada em seu irmão, e um filho à direita é seguido por seu pai. Cada elemento tem uma altura bem definida acima das folhas, e cada elemento não folha tem seus filhos no início da matriz. Sua profundidade abaixo da raiz, entretanto, depende do tamanho da matriz. O algoritmo é organizado de forma que a raiz esteja no final do heap e, no momento em que um elemento é extraído do heap, ele já está em sua localização final e não precisa ser movido. Além disso, uma matriz classificada já é um heap válido e muitos intervalos classificados são subárvores ordenados por heap válidos.

Mais formalmente, cada posição i é a raiz de uma subárvore única, cujos nós ocupam um intervalo contíguo que termina em i . Um prefixo inicial da matriz (incluindo a matriz inteira) pode ser um intervalo correspondente a uma subárvore, mas em geral se decompõe como uma união de vários intervalos de subárvore sucessivos, que Dijkstra chama de "alongamentos". Qualquer subárvore sem um pai (ou seja, enraizada em uma posição cujo pai está além do prefixo em consideração) dá uma extensão na decomposição desse intervalo, cuja decomposição é, portanto, única. Quando um novo nó é anexado ao prefixo, ocorre um de dois casos: ou a posição é uma folha e adiciona um trecho de comprimento 1 à decomposição, ou combina com os dois últimos trechos, tornando-se o pai de suas respectivas raízes, substituindo assim os dois trechos por um novo trecho contendo sua união mais a nova posição (raiz).

Dijkstra observou que a regra óbvia seria combinar trechos se e somente se eles tivessem o mesmo tamanho, caso em que todas as subárvores seriam árvores binárias perfeitas de tamanho 2 k −1 . No entanto, ele escolheu uma regra diferente, que dá mais tamanhos de árvore possíveis. Isso tem a mesma eficiência assintótica , mas ganha um pequeno fator constante na eficiência, exigindo menos alongamentos para cobrir cada intervalo.

A regra que Dijkstra usa é que os dois últimos trechos são combinados se e somente se seus tamanhos forem números de Leonardo consecutivos L ( i +1) e L ( i ) (nessa ordem), cujos números são definidos recursivamente, de uma maneira muito semelhante aos números de Fibonacci , como:

  • L (0) = L (1) = 1
  • L ( k +2) = L ( k +1) + L ( k ) + 1

Como consequência, o tamanho de qualquer subárvore é um número de Leonardo. A sequência de tamanhos de trecho decompondo as primeiras n posições, para qualquer n , pode ser encontrada de maneira gananciosa: o primeiro tamanho é o maior número de Leonardo que não excede n , e o restante (se houver) é decomposto recursivamente. Os tamanhos dos trechos estão diminuindo, estritamente, exceto possivelmente para dois tamanhos finais 1, e evitando números de Leonardo sucessivos, exceto possivelmente para os dois tamanhos finais.

Além de cada trecho ser uma árvore ordenada por heap, as raízes das árvores são mantidas em ordem de classificação. Isso efetivamente adiciona um terceiro filho (que Dijkstra chama de "enteado") a cada raiz vinculando-o à raiz anterior. Isso combina todas as árvores em um heap global. com o máximo global no final.

Embora a localização do enteado de cada nó seja fixa, o link existe apenas para as raízes das árvores, o que significa que os links são removidos sempre que as árvores são fundidas. Isso é diferente dos filhos comuns, que estão vinculados enquanto o pai existir.

Na primeira fase de classificação (crescimento do heap), uma parte inicial cada vez maior da matriz é reorganizada de modo que a subárvore para cada um de seus trechos seja um heap máximo: a entrada em qualquer posição não-folha é pelo menos tão grande quanto as entradas nas posições que são seus filhos. Além disso, todas as raízes são pelo menos tão grandes quanto seus enteados.

Na segunda fase (redução de heap), o nó máximo é separado do final do array (sem a necessidade de movê-lo) e as invariáveis ​​de heap são restabelecidas entre seus filhos. (Especificamente, entre os enteados recém-criados.)

A implementação prática freqüentemente precisa calcular os números de Leonardo L ( k ) . Dijkstra fornece um código inteligente que usa um número fixo de variáveis ​​inteiras para calcular com eficiência os valores necessários no momento em que são necessários. Alternativamente, se houver um limite finito N no tamanho das matrizes a serem classificadas, uma tabela pré-computada de números de Leonardo pode ser armazenada no espaço O (log  N ) .

Operações

Embora as duas fases do procedimento de classificação sejam opostas uma à outra no que diz respeito à evolução da estrutura de sequência de heaps, elas são implementadas usando uma primitiva de núcleo, equivalente à operação "peneirar" em um máximo binário pilha.

Peneirando para baixo

A operação principal de sift-down (que Dijkstra chama de " trinkle ") restaura a invariante do heap quando possivelmente é violada apenas no nó raiz. Se o nó raiz for menor que qualquer um de seus filhos, ele será trocado por seu maior filho e o processo será repetido com o nó raiz em sua nova subárvore.

A diferença entre smoothsort e um heap máximo binário é que a raiz de cada trecho deve ser ordenada em relação a um terceiro "enteado": a raiz do trecho anterior. Portanto, o procedimento de análise começa com uma série de comparações de quatro fatores (o nó raiz e três filhos) até que o enteado não seja o elemento máximo, em seguida, uma série de comparações de três fatores (a raiz mais dois filhos) até a raiz o nó encontra seu lar final e os invariantes são restabelecidos.

Cada árvore é uma árvore binária completa : cada nó tem dois filhos ou nenhum. Não há necessidade de lidar com o caso especial de um filho que ocorre em um heap binário implícito padrão . (Mas o caso especial de links de enteado mais do que compensa essa economia.)

Como existem trechos O (log  n ) , cada um dos quais é uma árvore de profundidade O (log  n ) , o tempo para realizar cada operação de peneiramento é limitado por O (log  n ) .

Aumentar a região do heap incorporando um elemento à direita

Quando um elemento adicional é considerado para incorporação na sequência de trechos (lista de estruturas de heap disjuntas), ele forma um novo trecho de um elemento ou combina os dois trechos mais à direita tornando-se o pai de suas raízes e formando um novo trecho que substitui os dois na sequência. Qual dos dois acontece depende apenas dos tamanhos dos trechos atualmente presentes (e, em última análise, apenas do índice do elemento adicionado); Dijkstra estipulou que os trechos são combinados se e somente se seus tamanhos forem L ( k +1) e L ( k ) para algum k , ou seja, números de Leonardo consecutivos; o novo trecho terá tamanho L ( k +2) .

Em qualquer um dos casos, o novo elemento deve ser peneirado até seu lugar correto na estrutura do heap. Mesmo se o novo nó for um trecho de um elemento, ele ainda deve ser classificado em relação à raiz do trecho anterior.

Otimização

O algoritmo de Dijkstra economiza trabalho observando que o invariante de heap completo é necessário no final da fase de crescimento, mas não é necessário em todas as etapas intermediárias. Em particular, o requisito de que um elemento seja maior do que seu enteado só é importante para os elementos que são as raízes finais da árvore.

Portanto, quando um elemento é adicionado, calcule a posição de seu futuro pai. Se estiver dentro da faixa de valores restantes a serem classificados, aja como se não houvesse enteado e apenas peneire dentro da árvore atual.

Reduzindo a região do heap, separando o elemento mais à direita dele

Durante esta fase, a forma da sequência de alongamentos passa pelas mudanças da fase de crescimento ao contrário. Nenhum trabalho é necessário ao separar um nó folha, mas para um nó não folha seus dois filhos tornam-se raízes de novos trechos e precisam ser movidos para seu lugar apropriado na sequência de raízes de trechos. Isso pode ser obtido aplicando-se o peneiramento duas vezes: primeiro para a criança esquerda e depois para a direita (cujo enteado era o filho esquerdo).

Como metade de todos os nós em uma árvore binária completa são folhas, isso executa uma média de uma operação de seleção por nó.

Otimização

Já se sabe que as raízes recém-expostas estão corretamente ordenadas em relação aos seus filhos normais; é apenas a ordem relativa a seus enteados que está em questão. Portanto, ao diminuir a pilha, a primeira etapa de peneirar pode ser simplificada para uma única comparação com o enteado. Se ocorrer uma troca, as etapas subsequentes devem fazer a comparação completa de quatro vias.

Análise

Smoothsort leva O ( n ) tempo para processar uma matriz pré-classificada, O ( n log  n ) no pior caso, e atinge desempenho quase linear em muitas entradas quase classificadas. No entanto, ele não trata todas as sequências quase ordenadas de maneira ideal. Utilizando a contagem de inversões como uma medida de un-sortedness (o número de pares de índices i e j com i < j e A [ i ]> A [ J ] ; para entrada ordenados aleatoriamente isto é aproximadamente n 2 /4 ), existem sequências de entrada possíveis com inversões O ( n log  n ) que fazem com que demore Ω ( n log  n ) tempo, enquanto outros algoritmos de ordenação adaptativos podem resolver esses casos em tempo O ( n log log  n ) .

O algoritmo smoothsort precisa ser capaz de manter na memória os tamanhos de todas as árvores no heap Leonardo. Como eles são classificados por ordem e todos os pedidos são distintos, isso geralmente é feito usando um vetor de bits que indica quais pedidos estão presentes. Além disso, como a ordem maior é no máximo O (log  n ) , esses bits podem ser codificados em O (1) palavras de máquina, assumindo um modelo de máquina transdicotômico .

Observe que O (1) palavras de máquina não é a mesma coisa que uma palavra de máquina. Um vetor de 32 bits seria suficiente apenas para tamanhos menores que L (32) = 7049155 . Um vetor de 64 bits serve para tamanhos menores que L (64) = 34335360355129 ≈ 2 45 . Em geral, leva 1 / log 2 ( φ ) ≈ 1,44 bits de vetor por bit de tamanho.

Tipo de choupo

Um algoritmo mais simples inspirado no smoothsort é o poplar sort . Nomeado após as fileiras de árvores de tamanho decrescente freqüentemente vistas em pôlderes holandeses , ele realiza menos comparações do que smoothsort para entradas que não são principalmente classificadas, mas não podem atingir o tempo linear para entradas classificadas.

A mudança significativa feita pela classificação do choupo, em que as raízes das várias árvores não são mantidas em ordem; não há links de "enteado" amarrando-os juntos em uma única pilha. Em vez disso, cada vez que o heap é reduzido na segunda fase, as raízes são pesquisadas para encontrar a entrada máxima.

Como há n etapas de redução, cada uma das quais deve pesquisar O (log  n ) raízes da árvore para o máximo, o melhor caso de tempo de execução para classificação de choupo é O ( n log  n ) .

Os autores também sugerem o uso de árvores binárias perfeitas em vez de árvores de Leonardo para fornecer mais simplificação, mas esta é uma mudança menos significativa.

A mesma estrutura foi proposta como uma fila de prioridade de propósito geral sob o nome de heap pós-pedido , alcançando tempo de inserção O (1) amortizado em uma estrutura mais simples do que um heap binomial implícito .

Formulários

A biblioteca musl C usa smoothsort para sua implementação de qsort().

Referências

links externos