Essa pesquisa faz parte da disciplina de Estrutura de Dados e objetiva demonstrar o desempenho de algoritmos de ordenação, semelhante ao trabalho desenvolvido por Souza, Ricarte e de Almeida Lima (2017).
Nove casos foram propostos. Foi necessário utilizar 3 tipos de vetores: ordenados, invertidos e aleatórios (melhor, pior e médio caso respectivamente). Os tamanhos dos vetores para teste foram definidos em mil, 100 mil e 1 milhão de elementos.
A partir disso, implementei um programa em C com base nos códigos de ordenação disponibilizados pelo professor Ednilson, com o acréscimo de contadores de comparações, trocas e tempo de execução, além de adaptações para permitir a execução no Windows manipulando a memória Heap.
Dessa forma, apliquei para cada um dos tamanhos de vetor um teste que executava cada um dos casos (melhor, pior e médio) três vezes e anotei as médias que estão dispostas nas tabelas a seguir.
Resultado médio de testes com mil, 100 mil e 1 milhão de elementos com casos de vetores ordenados, invertidos e aleatórios.
| Mil elementos | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| MELHOR | PIOR | MÉDIO | |||||||
| Comparações | Trocas | Tempo (s) | Comparações | Trocas | Tempo (s) | Comparações | Trocas | Tempo (s) | |
| BUBBLE | 999 | 0 | 0,0013 | 999000 | 499500 | 0,0040 | 964368 | 251729 | 0,0030 |
| INSERT | 999 | 0 | 0,0003 | 999 | 499500 | 0,0020 | 999 | 251729 | 0,0010 |
| SELECTION | 499500 | 1000 | 0,0030 | 499500 | 1000 | 0,0020 | 499500 | 1000 | 0,0023 |
| MERGE | 5044 | 9976 | 0,0000 | 4932 | 14908 | 0,0000 | 8686 | 14275 | 0,0003 |
| QUICK | 8834 | 193 | 0,0000 | 8837 | 1693 | 0,0000 | 11766 | 2503 | 0,0000 |
| 100 Mil elementos | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| MELHOR | PIOR | MÉDIO | |||||||
| Comparações | Trocas | Tempo (s) | Comparações | Trocas | Tempo (s) | Comparações | Trocas | Tempo (s) | |
| BUBBLE | 99999 | 0 | 0,0010 | 9999900000 | 4999950000 | 27,7183 | 9955500444 | 2503891391 | 33,1900 |
| INSERT | 99999 | 0 | 0,0010 | 99999 | 4999950000 | 12,0623 | 99999 | 2503891391 | 5,8307 |
| SELECTION | 4999950000 | 100000 | 8,9123 | 4999950000 | 100000 | 9,0360 | 4999950000 | 100000 | 8,7600 |
| MERGE | 853904 | 1668928 | 0,0340 | 815024 | 2483952 | 0,0343 | 1536329 | 2428689 | 0,0383 |
| QUICK | 1555496 | 126196 | 0,0047 | 1555500 | 176196 | 0,0043 | 2063052 | 403540 | 0,0110 |
| 1 Milhão de elementos | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| MELHOR | PIOR | MÉDIO | |||||||
| Comparações | Trocas | Tempo (s) | Comparações | Trocas | Tempo (s) | Comparações | Trocas | Tempo (s) | |
| BUBBLE | 999999 | 0 | 0,0030 | 999999000000 | 499999500000 | 3191,0133 | 998465001534 | 250154201104 | 3958,679751 |
| INSERT | 999999 | 0 | 0,0033 | 999999 | 499999500000 | 1174,3257 | 999999 | 250154201104 | 690,454152 |
| SELECTION | 499999500000 | 1000000 | 878,9800 | 499999500000 | 1000000 | 884,9253 | 499999500000 | 1000000 | 977,406707 |
| MERGE | 10066432 | 19951424 | 0,0896 | 9884992 | 29836416 | 0,0908 | 18672899 | 29228704 | 4,653309 |
| QUICK | 18803872 | 1209695 | 0,0453 | 18803872 | 1709693 | 0,0462 | 26890127 | 4706043 | 0,152607 |
Tempo de execução X Quantidade de elementos
A variação utilizada nesse algoritmo de troca é a melhorada. Ele apresenta um ótimo resultado para vetores ordenados, mas quando utilizado em vetores invertidos ou aleatórios perde desempenho, além de se tornar o pior dos algoritmos de ordenação para vetores grandes, como no caso de um milhão.
O insertion sort apresenta um desempenho melhor em comparação ao bubble sort, obtendo resultados em até menos da metade do tempo. Ele segue um padrão de comparação de n-1, zero trocas para vetores ordenados e (n(n-1))/2 para vetores invertidos.
O pior resultado de tempo para vetores ordenados e também para vetores pequenos. Seu tempo de resposta é muito semelhante independente do caso, mudando apenas com a variação de tamanho do vetor e segue o mesmo padrão para todos os casos: (n(n-1))/2 comparações e n trocas.
Esse tipo de ordenação é um dos mais rápidos. O merge sort apresenta o conceito de recursividade e cumpre muito bem seu papel. Entretanto, há uma certa dificuldade em contabilizar as trocas quando não é definido exatamente o que é considerado troca. Nesse algoritmo há diversas divisões em outros vetores menores que entram na contagem final, incluindo em vetores já ordenados.
Condizente com o nome, esse é o algoritmo com o melhor tempo de resposta. Ele também apresenta o conceito de recursividade como no merge e é ideal para grandes conjuntos de dados, como pode ser visto no comparativo.
SOUZA, Jackson EG; RICARTE, João Victor G.; DE ALMEIDA LIMA, Náthalee Cavalcanti. Algoritmos de Ordenação: Um estudo comparativo. Anais do Encontro de Computação do Oeste Potiguar ECOP/UFERSA (ISSN 2526-7574), n. 1, 2017.