Ordenação adaptativa
Um algoritmo de ordenação cai na família ordenação adaptativa, se tira vantagem da ordenação existente em sua entrada. Ele se beneficia do pré-ordenamento na seqüência de entrada - ou uma quantidade limitada de desordem para as diversas definições de medidas de desordem - e ordenação mais rápidamente. A ordenação adaptativa é normalmente realizada modificando-se os algoritmos de ordenação existentes.
Motivação editar
Algoritmos de ordenação por comparação tem tradicionalmente tratado com a realização de um ideal de limite de O(n logn) quando se trata de complexidade de tempo. A ordenação adaptativa tira proveito da ordem existente da entrada para tentar e conseguir tempos melhores, de modo que o tempo gasto pelo algoritmo de classificação é uma função de crescimento suave do tamanho da seqüência e da desordem na seqüência. Em outras palavras, quanto mais a entrada é pré-ordenada, o mais rápido deve ser classificado.
Este é um algoritmo atraente porque sequências quase ordenadas são comuns na prática. Assim, o desempenho de algoritmos de ordenação existentes podem ser melhorados, tendo em conta a ordem existente na entrada.
Note que a maioria dos algoritmos de ordenação de pior caso que se comportam otimamente no pior caso, notavelmente o heap sort e o merge sort, não têm a ordem existente dentro de sua entrada em conta, apesar de essa deficiência ser facilmente corrigida no caso do merge sort, verificando se o último item a esquerda ≤ primeiro item a direita, caso em que uma operação de intercalação pode ser substituída por uma concatenação simples - uma alteração que está bem dentro do escopo de fazer uma algoritmo adaptativo.
Exemplos editar
Um exemplo clássico de um algoritmo de ordenação adaptativo é o Straight Insertion Sort. Neste algoritmo de ordenação, nós fazemos a varredura da entrada da esquerda para a direita, várias vezes encontrando a posição do item atual, e inserindo-o em um array de itens previamente classificados.
Em formato de pseudo-código, o algoritmo Straight Insertion Sort poderia ser algo como isto:
procedure Straight Insertion Sort (X, n):
X[0] := − ∞;
for j := 2 to n do
begin i := j − 1;
t := X[j];
while t < X[i] do
begin X[i + 1] := X[i];
i := i + 1
end;
X[i + 1] := t;
end;
O desempenho deste algoritmo pode ser descrito em termos do número de inversões na entrada e, em seguida T(n) será aproximadamente igual a I(A) + (n - 1) , onde I(A) é o número de inversões. Usando essa medida de preordenamento - estar em relação ao número de inversões - o Straight Insertion Sort leva menos tempo para ordenar o quanto mais próximo estiver já ordenado.
Outros exemplos de algoritmos de ordenação adaptativa são Heap sort adaptativo e Merge-Sort adaptativo. O algoritmo de Dijkstra, Smoothsort é uma variação sobre o heap-sort que é considerada também um algoritmo de ordenação adaptativo.
O timsort, usado em Python como seu algoritmo de ordenação genérica, é adaptativo[1]
Bibliografia editar
- HAGERUP, Torben; KATJAINEN, Jyrki (2004). Algorithm Theory – SWAT 2004. Berlin Heidelberg: Springer-Verlag. pp. 221–222. ISBN 3-540-22339-8
- MEHTA, Dinesh P.; SAHNI, Sartaj (2005). Data Structures and Applications. USA: Chapman & Hall/CRC. pp. 11‑8–11‑9. ISBN 1-58488-435-5
- ESTIVILL-CASTRO, Vladmir; WOOD, Derick (Dezembro 1992). «A survey of adaptive sorting algorithms». ACM. 24 (4). New York, NY, USA: ACM. pp. 441–476. ISSN 0360-0300. doi:10.1145/146370.146381. Consultado em 22 de fevereiro de 2009
- PETERSSON, Ola; MOFFAT, Alistair (1992). «A framework for adaptive sorting». Lecture Notes in Computer Science. 621. Berlin: Springer Berlin / Heidelberg. pp. 422–433. ISSN 1611-3349. doi:10.1007/3-540-55706-7_38. Consultado em 22 de fevereiro de 2009
Referências
- ↑ PETERS, Tim. «listsort.txt». Consultado em 31 de março de 2009