Algoritmos de ordenação tem uma grande importância na área de computação, tendo em vista que a tarefa de ordenação é aplicada em tarefas diversas, entre elas pré-optimização, listagem de valores, indexação e entre outros. Um subproblema de grande ocorrência.
Neste documento será apresentado uma breve análise empírica extraída sobre o comportamento em relação ao tempo de execução dos seguintes algoritmos: BubbleSort, QuickSort, InsertionSort, MergeSort e HeapSort.
Dentre tais citados, estão classificados como algoritmos de ordenação quadráticos \(O(n^2)\) e log-linear \(O(nlog(n)\). Para cada um dos algoritmos foram executados 5 experimentos de execução de ordenação com vetores pseudo-aleatórios. Na análise global é considerado a média desses experimentos.
Algoritmo de complexidade no pior e médio caso de \(O(nlog(n))\). Dados de inferência:
Algoritmo de complexidade no pior caso \(O(n^2)\) e médio caso de \(O(nlog(n))\). Dados de inferência:
Algoritmo de complexidade no pior e médio caso de \(O(nlog(n))\). Dados de inferência:
Algoritmo de complexidade no pior caso \(O(n^2)\). Dados de inferência:
Algoritmo de complexidade no pior caso \(O(n^2)\). Dados de inferência:
Percebe-se experimentalmente,portanto, que o algoritmo que obteve o melhor desempenho entre eles foi o QuickSort. Relevante observar que entre os mais eficientes (\(O(nlog(n))\)) HeapSort foi o mais lento. No caso dos algoritmos quadráticos, BubbleSort demonstrou ter a pior performance assintótica, assim como pior que InsertionSort embora possuam a mesma complexidade computacional de pior caso.
BubbleSort segue um padrão de ser duas vezes pior que InsertionSort. Enquanto para o BubbleSort levou cerca de uma hora para ordenar o caso com um milhão de elementos, InsertionSort levou apenas meia-hora.
O mais impressionante é que os algoritmos considerados eficientes são mais rápidos numa escala muito diferente. Observando os algoritmos quadráticos e log-linear no mesmo gráfico, os algoritmos eficientes tem uma aparência constante comparado com os quadráticos.
As tabelas dos dados coletados estão disponíveis abertamente no sítio: https://github.com/ryukinix/data-structures-ufc/tree/master/src/sort/benchmark