4

Quero saber qual algoritmo tem o melhor desempenho ao lidar com seu pior caso comparado a outros lidando cada um com o seu próprio pior caso, todos aplicados em ordenação de array.

Para entender melhor o que quero saber, vão alguns questionamentos que levam à resposta.

Há um consenso de qual algoritmo de ordenação por comparação voltado para arrays é melhor ao comparar com outros, cada um em seu respectivo pior casos?

Sendo merge sort, timsort, smootchsort, intro sort e heap sort algoritmos de complexidade O(n*log(n)) de comparações e tempo, qual tem o menor fator de n*log(n)?

Há um outro algoritmo tradicional que supera os cinco no pior caso? Ou uma variante amplamente conhecida de algum algoritmo (como quick sort, já que o simples critério de seleção de pivô tem muita variedade e impacto) ou união de múltiplos algoritmos que supera (tipo intro sort + insertion sort)?

Enfim, qual é o melhor algoritmo de ordenação em pior caso? Leve em conta que é ordenação de arrays e não se aceita só complexidade assintótica mas também o fator desse termo na fórmula de comparações ou medidas experimentais de tempo em problemas de grande porte.

1 Resposta 1

3

Temos que ter cuidados com expectativas e realidades ao lidar com arrays. Como são estruturas sem tanta dinâmica, encontramos neles complicações e inconveniências em implementações de algoritmos para ordená-los que, inclusive, podem parecer até pegadinhas.

Saindo de arrays, a coisa é bem menos restritiva. Neles, o rápido acesso ao dado tendo seu índice é um benefício muito buscado e aproveitado visando bom desempenho em várias operações, mas isso não garante baixa complexidade de operações e tem seu preço e inconveniências em certas circunstâncias, o que dificulta a escolha do algoritmo.

  • Merge sort em listas

Por exemplo, para mover nós em listas encadeadas só precisamos inseri-los numa posição, não precisando manualmente mover todos que estão no caminho como nos arrays, mas sim ter essa posição para nela colocar. Para aplicar o merge sort, dá ainda para manusear os ponteiros de forma otimizada, salvando e usando atalhos para posições chaves da lista para evitar de passear pelos nós até alcançar (ou, se não salvar, percorrer na lista 50% mais vezes ou até em dobro). Isso torna o merge sort muito mais adequado em listas encadeadas do que arrays.

Pode-se percorrer a lista na primeira vez para isoladamente ordenar cada pedacinho dela. Enquanto isso, a custo de O(n) no espaço da memória pode salvar o ponto de início de cada um (portanto de fim do anterior) para depois não percorrer um pedaço inteiro da lista para chegar no próximo.

Pode-se depois percorrê-la O(log(n)) vezes para mesclar pedaços em pares, fazendo O(n) comparações na lista inteira por ciclo (totalizando O(n*log(n))) e quando precisar move elementos simplesmente desencadeando-os de onde estão e encadeando-os em seus destinos (até O(n) vezes por ciclo, totalizando O(n*log(n))).

Isso não só resulta, no pior caso, em 1+n*floor(log2(n))+n-2^floor(log2(n)+1) comparações nas listas (assim como nos arrays, resumido a n*log(n)-n+1 = O(n*log(n))) mas também se bem implementados com atalhos ao menos n+ceil(n/2)*floor(log2(n))-2^floor(log2(n)) movimentos de nós e adicionais que vão de zero a floor(2^ceil(log2(n)-1)/3) (resumido tudo a n*log(n)/2+O(n) = O(n*log(n)) movimentos, ao contrário dos arrays).

Repare que os movimentos de dados durante o mergesort jamais ocorre de maneira que haja no meio do caminho um valor igual ao que é movido, o que mantém então valores iguais sempre na mesma ordem e faz do mergesort um algoritmo estável.

  • Merge sort em arrays

Esses movimentos em arrays ocorrem com atribuições de valores novos sobre os antigos na posição. O custo dessa movimentação em arrays no merge sort depende se há memória suficiente para usar um array auxiliar com tamanho n e manter no pior caso a complexidade O(n*log(n)) não só nas comparações mas também nos movimentos, assim como custa em lista encadeada.

Caso não tenha array auxiliar, não tendo memória disponível... somente pode-se dar shift nos elementos (afinal não há outro lugar para colocar) e isso resulta em complexidade O(n²*log(n)) no pior caso (O(log(n)) níveis de merge, para cada nível O(n) comparações e para cada comparação O(n) atribuições).

Nem importa o número exato de atribuições, é absurdamente custoso, tem opções melhores. Em outras palavras, array tem essa dependência de memória para ordenar com bom desempenho usando merge sort e movendo cada elemento apenas uma vez, de um array a outro, em cada uma das ceil(log2(n)) (ou 2*ceil(log2(n)/2)) percorridas do array.

  • Tree sort em árvores binárias

Apesar de complicado, em árvores pode-se temporariamente adaptar os ponteiros de modo que cada nó funcione como de lista e fazer merge sort para depois remontar a árvore em ordem. Porém aparentemente o melhor algoritmo neste caso é o tree sort. Essas várias facilidades juntas dificilmente se encontram em ordenação de array.

Sempre que houver dados novos para inserir numa árvore de busca balanceada o tree sort está pronto para inserir com complexidade O(log(n)) flexivelmente tratando empate como um algoritmo de ordenação estável, mantendo assim a árvore sempre atualizada, ordenada, normalmente sem precisar atuar na árvore inteira e demandando como dados auxiliares apenas o básico que já faz parte dos nós de uma árvore de busca. Mesmo que não tenha feito a árvore ser ordenada desde o princípio, pode-se simplesmente reconstruir a árvore corretamente, inserção por inserção, com base no algoritmo e assim mantê-la.

Se a árvore for completa, o número de comparações no pior caso é igual ao do merge sort, porém o tree sort tem quase o mesmo desempenho entre melhor e pior caso, o que dá uma vantagem ao merge sort nesse aspecto já que ele, do pior caso ao melhor, tem quase 50% menos comparações. Além disso, cada inserção pode requerer O(n) rotações em toda a parte da árvore para mantê-la completa, o que provoca no algoritmo uma complexidade O(n²) de movimentos no pior caso.

A altura de árvore completa, o que determina uma quase proporção de custo de comparações por inserção, é floor(log2(n)+1), já altura de AVL vai de floor(log2(n)+1) a floor(logφ(( n+1.5 )/( 0.5+sqrt(0.45) ))) (sendo φ=sqrt(1.25)+0.5, ou seja, razão áurea), considera-se então no pior caso cerca de 1.44*log2(n)).

Então se ao invés disso a árvore for AVL, as rotações por inserção que conservam o balanceamento ocorrem O(log(n)) vezes até mesmo em pior caso, conservando a complexidade O(n*log(n)) da ordenação não só de comparações mas também de movimentos.

Porém, como visto no parágrafo anterior, o número de comparações é maior que do merge sort (apesar da mesma complexidade), no pior caso em torno de 44% a mais (x1.44). Sendo assim, mesmo com o enorme ganho ele permanece perdendo em desempenho.

  • Tree sort em arrays

Enfim, que eu saiba não são amplamente estudados meios de aplicar este algoritmo num array ou simular uma árvore completa ou AVL num array de uma tal maneira que se possa ordenar com tree sort. Mesmo que se descubra um meio de fazer isso, não parece valer a pena porque teoricamente o tree sort perde para merge sort, só se houver alguma sacada genial que simplifique operações e até agora não encontrei e nem pensei em nada para isso.

Curiosidade:

É possível implementar insertion sort com complexidade O(n*log(n)) de comparações (busca binária da posição correta a cada inserção). O número de comparações no pior caso é o mesmo que tree sort de árvore completa e merge sort. Aliás, pode-se enxergar os passos de comparações como similares a de uma árvore completa, é como se fosse o tree sort no aspecto das comparações.

E adivinha? Isso pouco importa. Mantém-se o problema de ter que dar shift para fazer inserção em arrays, mover elementos numa complexidade O(n) no pior caso a cada inserção, garantindo assim O(n²). Realmente não funciona como uma árvore na prática.

  • Insertion sort

Por falar em insertion sort, vamos falar o óbvio: ele ordena arrays e é estável mas tradicionalmente faz shift, tem complexidade O(n²) de comparações e movimentos no pior caso, portanto é péssima ideia em problemas grandes.

Ok, mas e os problemas pequenos? Já pensou ter que ordenar várias sequências pequenas que juntas acumulam grande esforço computacional? Pois bem, pode valer a pena testar o desempenho do insertion sort em casos como esses, mesmo nos piores. O insertion sort é considerado um ótimo algoritmo de ordenação de arrays curtos. Testes com inteiros que fiz tempo atrás indicam que em caso médio ele costuma ser bom com uns vinte elementos e pior caso, em torno de oito.

Mesmo com muitas comparações num problema pequeno, são instruções muito simples, rápidas e que bem aproveitam a cash. O problema é se as comparações forem de dados que custam muito, como strings (pior ainda com iniciais parecidas) e estruturas com dados muito repetidos e cheios de desempates (como vestibulandos com pontuações parecidas, nomes parecidos, em mesmas faixas etárias).

Além disso, o insertion sort é muito usado combinado com algoritmos que partem os arrays em pedaços que serão ordenados separadamente e podem ser razoavelmente pequenos.

Um exemplo é o merge sort, que pode partir um array com centenas de elementos em 32 miúdas sequências que serão ordenadas com insertion sort, aí juntam em 16 pedaços ordenados, depois 8, 4, 2 e finalmente o array inteiro ordenado.

O quicksort também costuma partir, de uma lado e do outro do pivô, pedaços cada vez menores de arrays que em algum momento podem ser tão pequenos que é melhor aplicar insertion sort. Pode achar um benefício pequeno, mas é um benefício e pode vir a calhar em vários arrays de tamanhos pequenos e médios, mesmo em piores casos (desde que escolha muito bem até que tamanho de array o insertion sort ordenará).

  • Quick Sort

É um algoritmo conhecido por ser aplicável em arrays e considerado rápido em seus casos médios (O(n*log(n)) comparações e trocas), porém instável, pior que insertion sort no melhor caso (O(n*log(n)) contra O(n)) e ainda pior que heap sort (e portanto merge sort) no pior caso (O(n²) contra O(n*log(n))). Além disso, não se conhece maneiras de implementá-lo sem que haja empilhamento de dados (complexidade O(log(n)) de memória se for bem implementado), quer seja com chamadas recursivas ou "manualmente" com arrays.

Ainda assim, a verdade é que ele tem flexível potencial de variantes com distintas propriedades. O quick sort segue o princípio de selecionar com algum critério (não havendo um padrão mas sim vários populares) um pivô e separar o array em dois a serem em seguida ordenados, um a esquerda do pivô com os valores que devem ficar a esquerda dele ao terminar de ordenar e outro a direita com os que devem ficar a direita. Só a escolha do critério já causa grande impacto no resultado em termos de desempenho.

Para analisar, desenvolvi no Maple 15 o seguinte procedimento que serve para construir fórmulas recursivas com armazenamento de resultados reutilizáveis para acelerar o cálculo e assim permitir calcular a tempo com valores relativamente grandes. Ele será usado para calcular o número de comparações do quick sort no pior caso a partir das recursões.

inserir a descrição da imagem aqui

Se o critério de escolha do pivô, mesmo que aleatório, seja de imediata seleção de um sem comparar com outros, o pior caso envolve esse valor ficar num extremo do array, separando um de tamanho "n" em um de tamanho "0" e outro de tamanho "n-1". Quer dizer, agora tem que ordenar um array de tamanho "n-1". Isso resulta no mesmo número de comparações que o insertion sort no pior caso, ou seja, complexidade quadrática e executa mais instruções.

inserir a descrição da imagem aqui

Se o critério for o clássico mediano de três (ordena três quaisquer para saber qual fica no meio), a divisão do pior caso é em "1" e "n-2" elementos e isso melhora muito o desempenho. Usando a função do maple, vemos que aparentemente a velocidade cresce de x1 nos menores arrays até a convergência para x2 em cada vez maiores.

inserir a descrição da imagem aqui

Se inventarmos de pegar o mediano de cinco, o pior caso resulta em pedaços de tamanho "2" e "n-3". Speed up de x1 a x3.

inserir a descrição da imagem aqui

Mediano de sete? É "3" e "n-4". Speed up x1 a x4.

inserir a descrição da imagem aqui

Em outras palavras, para ter trecho mínimo de "m" elementos se ordenam "p=2*m+1" valores (quantidade ímpar), logo "m=(p-1)/2". Perceba que se "p=n" então se ordena o array inteiro para pegar o pivô e ordenar os pedaços do array (que já estão ordenados). Tem que ter "p<n" e "m<(n-1)/2" para aplicar a separação em partes e a ordenação delas.

Como resultado, num nível de recursão o algoritmo ordena "p" elementos, um deles é pivô, "m" fica a esquerda dele, "m" fica a direita, restam "n-p" a serem comparados com o pivô e no pior caso acabam todos em um só lado para então ordenar os dois trechos (e indo todos para o outro lado do pivô é pior caso também de movimento de elementos). Recursivamente, o custo de comparação de array de tamanho "n" é o custo de ordenar "p" mais o custo de comparar e mover "m-p" para o outro lado do pivô mais o custo de ordenar "m" e o de ordenar "n-m-1" (ou "m+n-p").

Além disso, aparentemente o aumento do trecho ordenado na seleção de pivô melhora o desempenho no pior caso de arrays grandes. Será? Pegar o array inteiro para isso causa chamada recursiva infinita, claro. E se pegar "n-1"?

inserir a descrição da imagem aqui

Ao ordenar "n-1" e selecionar pivô, somente mais um terá que ser comparado com o ele para decidir de que lado fica. De um lado ficam floor((n-2)/2), do outro ceil((n-2)/2+1) ("+1" porque inclui nesse maior o que não foi usado para escolher pivô) e, apesar da divisão em pedaços quase iguais (é quase melhor caso), pra isso precisou de uma ordenação de quase tudo. O resultado foi multiplicador de velocidade quase zero, ou seja, perdeu velocidade. E se for procurar pivô em "n-2" elementos?

inserir a descrição da imagem aqui

O fator é bem maior que o anterior, mas continua praticamente zero. Quer dizer, arrays pequenos na busca melhoram ao aumentá-los e grandes melhoram ao diminuí-los, o que significa que deve ter um ponto de equilíbrio.

Inclusive perceba que ao passar de um para três elementos usados para achar o pivô há melhorias de desempenho no pior caso de todos os tamanhos de arrays e nenhum piora, já de 3 para 5 piora os arrays de tamanho n=6,7,8,9,10 mas empata com "n=11" e melhora daí para frente. De 5 para 7, também há um tamanho a partir do qual vale a pena, mas é bem maior. Aparentemente quanto maior o array maior é essa quantidade correta de valores a serem usados na busca do pivô.

Será possível encontrar uma fórmula para esse valor ótimo? Se encontrar e o aplicar a cada recursão do quick sort, será que a complexidade no pior caso reduz a O(n*log(n))? Será que vence ao menos o heap sort, quem sabe o merge sort?

inserir a descrição da imagem aqui

Apesar de não ter encontrado resposta para todos os questionamentos, ainda assim foi possível implementar a recursão que encontra comparações do pior caso e valor ótimo por meio de uma recursão de dois valores [ Comparações , ValorÓtimo ] e responder alguns dos mais importantes.

Primeiramente, perceba que para cada quantidade "p=1,3,5,..." o único que aparece uma única vez é 19, logo antes o 17 aparece várias vezes. Não parece fácil encontrar uma fórmula que calcule "p", correto? Parece ser uma sequência bem instável.

Em segundo lugar, repare que o speedup em "n=9999" foi de x58. Quer dizer que a melhoria em relação ao algoritmo mais básico de constante "p=1" é absurdamente alta. Por outro lado, usando a fórmula de comparações do merge sort encontramos x7 de speed up ao sair deste quick sort para o merge sort em "n=9999".

inserir a descrição da imagem aqui

Porém percebe-se que inicialmente o número de comparações do quick sort e do merge sort se equiparam e vão se distanciando, ou seja, até um certo momento o quick sort melhorado vence o heap sort e a partir dele os papéis se invertem.

Há mais variantes do quick sort, por exemplo em meios de selecionar a posição do trecho onde busca o pivô, adaptação para ganhar estabilidade, número de pivôs, etc. Porém vai da criatividade, são infinitas as possibilidades e nunca se termina quando se prende a isso. Além disso, aprofundamentos nisso não parecem compensadores neste contexto, pois afinal se observar os exemplos que citei:

  • posição do trecho não muda complexidade ou estabilidade,
  • essa estabilidade se ganha com shift ou alocação de memória (mesmo par de opções ao implementar merge sort, que é melhor em pior caso) e
  • mais pivôs são experimentalmente bons em casos próximos do médio, mas não parece eficiente no pior caso, pois são mais pivôs para multiplicar as comparações e baixa (ou nenhuma) redução do número de recursões.

Em outras palavras, até então o melhor parece ser usar o merge sort se houver disponibilidade de memória, caso contrário você pode optar por ordenação com heap sort ou "quick sort ótimo" a depender do tamanho do array. Como esses dois algoritmos são instáveis, se priorizar estabilidade acima do desempenho mesmo com diferença de complexidade, pode-se pensar no insertion sort.

  • Heap sort

Diferentemente de tree sort, este algoritmo é voltado também para ordenação de arrays apesar de teoricamente enxergar neles uma estrutura de árvore do tipo heap. Sua complexidade de operações, tanto comparações de dados quanto movimentos deles, é O(n*log(n)). Além disso, tem um benefício que o merge sort não tem: funciona sem array auxiliar. Não tem necessidade de alocar memória para ordenar com máximo desempenho e sem shift.

Mas tem dois pontos fracos. Primeiramente, ele é instável. Repetidamente troca posições de pares de elementos de várias partes do vetor podendo ter entre eles um valor igual a um dos dois e assim trocar a ordem deles sem reordená-los. Em segundo lugar, o número de comparações de valores do array no pior caso do heap sort fica em torno do dobro do pior caso do merge sort.

Sendo assim, aparentemente perde para os algoritmos anteriores, mas pelo menos serve para arrays e não precisa de vetor auxiliar. Até então, parece que o jeito é usar merge sort se puder e, se não conseguir alocar o array auxiliar, lamentavelmente você escolhe entre estabilidade (insertion sort, seja ele "binário" ou não nas comparações) e desempenho em arrays grandes (heap sort). Claro, com mais dados (associando a cada elemento o índice inicial) pode-se dar estabilidade ao heap sort, mas esse desempate da comparação e o movimento de dados custam.

Curiosidade:

Algoritmos assim costumam a cada elemento ter um custo de operações, como comparações, em proporção com log2(n) níveis de profundidade. No caso do heapsort, costumam ser comparações de raiz com filhos, até duas comparações, 2*log2(n). Ele simula uma árvore binária do tipo heap.

E se usasse uma árvore ternária? Ou quaternária? N-ária?

Se as proporções forem N*logN(n), perceba que o mínimo ficaria em N=e=2.718 (impossível), o caso de N=2 daria no mesmo que N=4 e possivelmente N=3 seria a melhor.

Da binária para a ternária, um aumento de uma comparação por nível com uma redução de 36.9% de profundidade, seria aproximadamente 3*log3(n) = 1.893*log2(n), uma redução de 5.36% no número de comparações da binária para a ternária. Como seria na prática?

E se poderia simplificar mais as N-árias para encontrar algo ainda melhor que 1.893*log2(n)?

  • Timsort

Não há muito o que dizer.

  • É voltado para "problemas da realidade", não piores casos.
  • É baseado no merge sort.
  • Aplica em cada um dos menores pedaços que serão unidos um insertion sort adaptado, sem reduzir comparações no pior caso.
  • Para piorar, a implementação oficial desequilibra os tamanhos dos pedaços que serão combinados, piorando o desempenho na etapa do merge sort no pior caso.

Resumindo, em termos de pior caso ele é um merge sort piorado. Adaptações que façam do algoritmo um meio termo entre merge sort e timsort podem criar um algoritmo com custos iguais aos do merge sort no pior caso e melhores que os dele em médio e melhor casos.

  • Observações Finais

É notória a diferença de desempenho de um algoritmo de ordenação não só entre as variadas formas de implementar o mesmo e num mesmo tipo de estrutura ordenável mas também das versões em tipos distintos das estruturas. Há algoritmos exclusivos de certos tipos, outros servem para vários mas são mais adequados para uns que outros. Até há casos de estruturas mais pesadas que, mesmo assim, um algoritmo é melhor nelas que outras porque elas oferecem recursos que possibilitam neles menores complexidades. Há uma vastidão de fatos a serem considerados.

Com o uso de ponteiros, pode-se estruturar dados de modo que se possa inseri-los, acessá-los, deslocá-los e removê-los das mais particulares maneiras, muito além de copiar valores lá salvos e sobrepor os antigos para simular movimento de dados (como se faz em arrays). Enquanto nos arrays lemos e escrevemos ao localizar com índice, outras estruturas têm benesses como modos de busca de um dado e nas redondezas dele a inserção de outro. Isso certamente impacta no desempenho de um algoritmo de ordenação, afinal um caro shift num array não é necessário numa lista por exemplo, só encadear com os ponteiros resolve. Encontrar um dado num índice instantaneamente é melhor que em ordem O(log(n)), mas inseri-lo entre outros dois é mais simples numa árvore. Por aí vai...

Devido a isso, não podemos falar como se os algoritmos fossem sempre ter os resultados de desempenho que pensamos que terão. O que é bom numa situação pode não ser bom em outra. É necessário atenção a cada caso. Podemos não somente num insertion sort fazer shift de elementos, que naturalmente acontece de precisar deslocar vários elementos para inserir um, mas também podemos ter a ideia de fazer isso em merge sort, quick sort e outros algoritmos (que não foram feitos para isso) para implantar estabilidades artificiais, falta de necessidade de alocação de memória e outras coisas que afinal prejudicam o desempenho mesmo mantendo a complexidade de comparações. É necessário cuidado para não cair em armadilhas como essas e se surpreender mais tarde. Os principais custos são de instruções em geral e tempo, não comparações como se popularizou.

Sem certas benesses, a escolha de um algoritmo para arrays fica difícil. A ordenação pode requerer alocação de espaço (como tradicionalmente se faz, por exemplo, no merge sort de array e cria demanda de memória), shift de valores (como tradicionalmente se faz no isertion sort e cria problemas de desempenho em longos shifts), swap de valores (como tradicionalmente se faz no quicksort e destrói a estabilidade da ordenação), não ter estabilidade, não ter a complexidade desejada, tudo por não ter recursos que possam convir e assim encontrando sempre alguma perda a se pensar.

  • Veredito

Como definir então um melhor algoritmo em piores casos?

Vamos começar pelo mais simples. Array pequeno? Insertion sort. Comparações de tipos simples de dados? Melhor ainda.

E grandes volumes de dados? Pode ser adequado fazer misturas de algoritmos, como um algoritmo que ordena pedaços pequenos com insertion sort, médios com "quick sort ótimo" e grandes com heap sort ou merge sort, cada um deles com possíveis adaptações.

O algoritmo principal pode ser o que cria as divisões ou que ordena completamente um array grande mas não arrays médios e pequenos. O algoritmo intermediário pode partir mais ainda o array ou pedaço dele que ele tiver que ordenar, o menorzinho ordena os pedaços menores e se depois disso o intermediário ou principal tiver mais o que fazer (como merge, que faz a maior mesclagem no final) ele pega esses pedaços ordenados para completar o serviço com a estratégia que mais reduz a complexidade.

Mas para escolher os algoritmos precisamos observar suas propriedades em ordenação de array e avaliar as condições. Como observamos anteriormente, o único defeito do merge sort é a demanda de memória. Se você tem espaço, é uma boa usar. Se tem estruturas de dados enormes já ocupando boa parte da memória, você pode precisar abrir mão dos benefícios desse algoritmo.

Se prioriza desempenho sem arriscar nos piores casos, o heap sort faz o serviço sem a demanda de memória. Se aceita arriscar um pouco, o quick sort é considerado uma boa ideia. Talvez o melhor a se fazer pensando em piores casos é em caso de array grande aplicar heap sort (total ou em grande parte e deixar o resto com insertion sort) e em caso de array não tão grande aplicar "quick sort ótimo", talvez refinando em pedaços pequenos para ordenar com insertion sort.

Não conheço algoritmo estável de desempenho razoável que economize memória.

Ainda tenho que olhar bem o smootchsort.

CONTINUA

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .