Ordenação adaptativa

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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 | editar código-fonte]

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 | editar código-fonte]

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 | editar código-fonte]

Referências

  1. PETERS, Tim. listsort.txt.

Ver também[editar | editar código-fonte]