Algoritmos de ordenação eficientes

Algoritmos de ordenação eficientes são mais recomendados para arquivos muito grandes porque - adivinha - eles são eficientes. Tem 4 algoritmos eficientes: Quicksort, Shellsort, Heapsort e Mergesort.

Quicksort: o quicksort é baseado no bubble sort - ou seja, realiza trocas. Dado um conjunto inicial de dados, é escolhido aleatoriamente um índice cujo conteúdo será chamado pivô. Feita essa escolha, um contador i é iniciado do início para o fim, percorrendo os valores e comparando-os com o pivô. Ao achar um elemento maior ou igual ao pivô, o íncide i para e inicia-se um j, do fim para o início, percorrendo os valores e procurando um menor ou igual ao pivô. Quando esse elemento é encontrado, os valores das posições i e j são trocados e o processo recomeça. Quando os contadores i e j se cruzam (ou seja, i aponta para uma posição à direita de j), são definidas duas partições do vetor e são feitas duas chamadas recursivas do quicksort, uma para cada partição. Antes de prosseguir, note que ao formar partições, todos os elementos de uma delas serão menores ou iguais ao pivô e, da outra, maiores ou iguais ao mesmo.
O tempo de execução do algoritmo depende do bom balanceamento das partições, ou seja, se o número de elementos está bem distribuído dos dois lados do pivô. No caso de um bom balanceamento, o algoritmo é O(n logn). Porém, para o pior caso, o algoritmo é quadrático, o que o torna inviável devido às chamadas recursivas.

Shellsort: o shellsort é um melhoramento do insertion sort. Ele analisa o vetor como uma intercalação de conjuntos e ordena cada um desses conjuntos com o insertion sort. Uma vez ordenados, o processo se repete com conjuntos maiores e, para isso, menos espaçados. Explicando melhor, o shellsort faz passadas pelo vetor analisando elementos equidistantes entre si, com uma distância h dada por uma expressão no início do algoritmo. Ao ordenar os subconjuntos, que são formados por elementos com distância h entre si, o h diminui. Assim, os subconjuntos incluirão mais e diversificados elementos. O processo se repete até que h seja 1, ou seja, elementos adjacentes. O h=1 caracteriza o insertion sort, que é sensível à ordenação parcial do vetor e, portanto, muito eficiente.
Não existe análise de complexidade definida para o shellsort, porque o resultado depende da sequência h escolhida. Para algumas sequências, o algoritmo pode ser O(n^3/2), O(n^7/6), O(n^1,25) ou O(n*(log(n))2), como sugerem alguns experimentos.

Heapsort: o heapsort é um algoritmo baseado no selection sort. Ele organiza o vetor de forma que o elemento dos índices 2k e 2k+1 são sempre menores do que o do índice k. Fica mais fácil visualizar essa estrutura em forma de árvore, em que um elemento tem dois filhos e cada filho tem outros dois filhos e por aí vai. O pai sempre é maior que os filhos. Para montar o heap, inicia-se da metade do vetor (afinal, daí pra frente já não haverão mais filhos) e, para cada elemento, é selecionado o maior filho e comparado com o pai. Caso o maior filho seja maior do que o pai, os dois são trocados. Quando é analisado um elemento cujos filhos tem filhos e é feita uma troca, a análise segue a cadeia de filhos até o final para que o heap se mantenha correto. Quando ele estiver finalmente montado, o elemento da primeira posição é trocado com o da última e, como o atual topo é menor, o heap é corrigido. Ao final da correção, o mesmo é feito, porém com a penúltima posição e por aí vai, até sobrar apenas a posição do topo e aí o vetor estará o ordenado.
O algoritmo tem custo total da construção do heap e da ordenação, totalizando O(n log₂n).

Mergesort: o mergesort é um algoritmo baseado em intercalação. Dado um vetor de tamanho n, ele vai separando em vetores menores cujo tamanho é metade do vetor anterior e por aí vai, até que cada vetor tenha tamanho 1. Em seguida, vai juntando pares de vetores intercalando-os de maneira ordenada. É um algoritmo recursivo. Como usa espaço extra, é aconselhado para situações de mesclar dois vetores já ordenados, por exemplo.
Tem custo O(nlogn) e usa espaço extra de tamanho proporcional a n para todos os casos (insensível a ordenação inicial do vetor).