Smoothsort
Smoothsort
Smoothsort funcionando em uma rede que está quase em ordem. As barras no topo mostram a estrutura da árvore.
| Descobridor ou inventor | Edsger Dijkstra |
|---|---|
| Data da descoberta | Mil novecentos e oitenta e um |
| Problema relacionado | Algoritmo de classificação |
| Estrutura de dados | Borda |
| Baseado em | Classificar por pilha |
| Pior caso | |
|---|---|
| Média | |
| Melhor caso |
| Pior caso | |
|---|---|
| Melhor caso |
Smoothsort é um algoritmo de classificação por comparação inventado em 1981 por Edsger Dijkstra . É uma classificação por complexidade , assim como a classificação de heap a partir da qual é inspirada, e a classificação rápida na maioria dos casos. Mas se os dados já estão quase classificados, é complexidade em . Essa classificação é então mais rápida do que a classificação rápida .
A transição entre os tempos de execução entre listas já ordenadas e listas mistas ou de cabeça para baixo é gradual, por isso o nome smoothsort , smooth significa suave, smooth. É uma classificação no local , ou seja, não há área de memória adicional alocada para armazenar os elementos.
Embora o algoritmo smoothsort seja mais rápido do que classificar por heap para listas pouco misturadas, ele é ligeiramente mais lento do que classificar por heap para listas que são descendentes para começar. Na verdade, os dados iniciais estão, então, mais próximos da estrutura de heap .
Objetivo Smoothsort
Uma grande desvantagem da classificação por heap é que se os dados já estiverem classificados, eles serão primeiro embaralhados antes de serem classificados novamente. Isso ocorre porque os dados intermediários são uma árvore binária em que os nós pais são maiores do que os nós filhos, com os pais à esquerda dos filhos na tabela.
Assim, durante esta fase da classificação por heap , os primeiros elementos da matriz são os maiores, enquanto no final da classificação, os maiores elementos devem estar no final da matriz (assumimos que estamos classificando em ordem crescente )
Para superar essa desvantagem, smoothsort usa uma árvore binária na outra direção, ou seja, cuja ordem parcial imposta aos nós da árvore está na mesma direção que a ordem final desejada (os dados da árvore e os dados de entrada são armazenados na mesma matriz , como acontece com a classificação de heap ). Isso requer a reorganização dos dados na árvore à medida que são classificados. Mas, como a árvore é construída na direção ascendente, se a matriz já estiver classificada, não há nada a fazer e os dados não são misturados.
Etapas do algoritmo
A primeira etapa é transformar o array em uma árvore binária. O primeiro elemento já está trivialmente bem ordenado, então adicionamos os seguintes elementos um por um. Os elementos são reordenados cada vez um pouco se necessário para que correspondam aos critérios:
- Cada nó não pode ser maior que seu nó pai
- O primeiro nó filho não pode ser maior que o segundo nó filho
NB: Estes critérios impõem uma ordem na mesma direção da direção ordenada, daí o interesse deste algoritmo.
A segunda etapa é transformar a árvore binária de volta em um array ordenado. Cada elemento que começa da direita é deixado como está porque é a raiz da árvore que já é o maior elemento, e a árvore restante é reordenada se necessário. Fazemos isso até obter uma matriz classificada.