Timsort

Timsort é um algoritmo de ordenação híbrido derivado do merge sort e do insertion sort, projetado para ter boa performance em vários tipos de dados do mundo real. Foi inventado por Tim Peters em 2002 para ser usado na linguagem de programação Python, e tem sido o algoritmo de ordenação padrão de Python desde a versão 2.3. Ele atualmente é usado para ordenar arrays em Java SE 7.

Tim Peters descreve o algoritmo da seguinte forma:

[...]um adaptativo, estável, merge sort natural, modestamente chamado de timsort (hey, eu mereço <wink>). Tem desempenho sobrenatural em muitos tipos de arrays parcialmente ordenados (menos de lg(N!) comparações necessárias, e tão poucas quanto N-1), no entanto, tão rápido quanto o algoritmo anterior altamente sintonizado, híbrido, samplesort de Python em matrizes aleatórias. Em suma, a rotina principal passa sobre a matriz uma vez, da esquerda para a direita, alternadamente, identificando o próximo passo, em seguida, fundindo-os em passos anteriores "inteligentemente". Todo o resto é complicação pela velocidade, e alguma medida duramente conquistada da eficiência de memória.

Como o merge sort, é um algoritmo de ordenação por comparação estável com uma complexidade de pior caso de $\Theta (n\log n)$.

De acordo com a teoria da Informação, nenhuma ordenação por comparação pode executar em menos de $\log _{2}(n!)$, no caso médio, o que exige que a ordenação por comparação tome um tempo de $\Omega (n\log n)$ em dados aleatórios. No entanto, em dados do mundo real, o Timsort muitas vezes exige muito menos do que $\log _{2}(n!)$, porque ele tira vantagem do fato de que sublistas dos dados podem já estar em ordem ou ordem inversa.

Introdução

TimSort é um algoritmo híbrido de ordenação baseado no MergeSort e InsertionSort. O algoritmo baseia-se na ideia de que, no mundo real, um vetor de dados a ser ordenado contém sub-vetores já ordenados, não importando como (decrescentemente ou crescentemente). Assim, o TimSort está à frente da maioria dos algoritmos de ordenação, mesmo não apresentando descobertas matemáticas complexas. O fato é que na realidade o TimSort não é um algoritmo autônomo, mas um híbrido, uma combinação eficiente de outros algoritmos, temperado com as idéias do autor. O algoritmo completo comentado, traduzido do Python para Java pode ser encontrado no site da openjdk.

O algoritmo ordena um segmento específico do vetor de entrada incrementalmente da esquerda para a direita, buscando por consecutivos elementos ordenados. Se esses segmentos não forem grande o suficente eles são estendidos e ordenados usando o InsertionSort. A posição de início e o tamanho dos segmentos gerados são armazenados em uma pilha. Durante a execução alguns desses segmentos são combinados (via Mergesort) de acordo com condições analisadas sobre os elementos que estão no topo da pilha, garantindo que os comprimentos dos segmentos gerados estão diminuindo e o comprimento de cada segmento gerado é maior que a soma dos próximos dois. No final, faz-se o merge de todos elementos restante, resultando em um vetor ordenado.

TimSort é um algoritmo de ordenação bastante eficiente se comparado aos demais existentes na literatura. Isso o levou a ser escolhido como algoritomo de ordenação padrão em linguagens de programação como Python e Java.

Passo a passo

O mecanismo do algoritmo pode ser explicado brevemente da seguinte maneira:

1. Um algoritmo específico é usado para dividir o vetor de entrada em sub-vetores.
2. Cada sub-vetor é ordenado usando um simples InsertionSort estável.
3. Os sub-vetores ordenados são mesclados com o uso do MergeSort.

Observação: Algumas otimizações são feitas no passo 1, na divisão em sub-vetores, e no MergeSort.

Definições do algoritmo:

1. N: Comprimento do vetor de entrada.
2. Run: Um sub-vetor ordenado que compõe o vetor de entrada.
3. Minrun: É o comprimento mínimo dos Runs. Este número é calculado baseado no tamanho do vetor de entrada (N).

Calculando os Minruns

O valor de Minrun é determinado com base no valor de N, seguindo os seguintes princípios:

1. Não deve ser muito longo, pois o Minrun será posteriormente submetido ao InsertionSort, que é efetivo para tamanhos menores de vetores (Runs).
2. Não deve ser muito curto, pois quanto mais curto for o Run, mais Runs terão que ser mescladas no próximo passo.
3. Seria bom se N / Minrun fosse uma potência de 2 (ou próximo disso). Esse requisito resulta do fato de que o MergeSort funciona melhor nos Runs que têm aproximadamente o mesmo comprimento.

No artigo da proposta do algoritmo o autor se refere a seus próprios experimentos, mostrando que com Minrun > 256, o princípio 1 não está satisfeito, e com Minrun <8, o princípio 2 não está satisfeito e os comprimentos que atingem melhores performances variam de 32 a 65.

Exceção: se N < 64, então Minrun = N e o TimSort se transformam em um simples MergeSort.

Para calcular o Minrun basta pegar os seis bits mais significativos de N, e somar 1 se os bits menos significativos restantes contiverem pelo menos um bit com valor 1.

int minRunLength (int n){
    assert n >= 0;
    int r = 0; // Becomes 1 if any 1 bits are
    shifted off
    while (n >= MIN_MERGE ) {
        r |= (n & 1);
        n > >= 1;
    }
    return n + r;
}

O valor MIN_MERGE pode ser definido como 64 seguindo a recomendação do autor.

Gerando e ordenando os Runs

Nessa fase os parâmetros são o vetor original de entrada com tamanho N e o valor de Minrun calculado anteriormente. O algoritmo para esta etapa é:

1. O endereço base do elemento atual é definido para a posição inicial do vetor de entrada.
2. Começando a partir da posição do elemento atual, procure o Run (um sub-vetor ordenado) no vetor de entrada. Por definição o Run será pelo menos o elemento atual e o próximo (pois formará um vetor ordenado, seja crescente ou decrescente), sendo que a composição de mais elementos no Run dependerá da forma como os elementos estão organizados. O próximo elemento é considerado se ao considerá-lo no Run atual, o Run continue ordenado. Se o Run final está ordenado de forma decrescente, os elementos são "reordenados" em uma ordem crescente (por meio de um algoritmo  simples de inversão de vetor).
3. Se o comprimento do Run atual for menor que o valor do Minrun, pega-se os W elementos que seguem o Run encontrado, sendo que W = Minrun - size(Run atual). Assim, o Run final será do tamanho do Minrun ou mais, sendo que uma parte (ou na melhor hipótese todo) do Run já estará ordenada. O tamanho do Run será menor do que Minrun apenas se for o último Run do vetor.
4. Então o Run atual é ordenado via InsertionSort. Como este Run é pequeno e parcialmente ordenado, a ordenação é rápida.
5. O endereço base do elemento atual é atualizado para o elemento seguinte ao último elemento pertencente ao Run que acabou de ser calculado.
6. Se o fim do vetor não foi alcançado, executa-se esse algoritmo novamente do ponto 2 até o ponto 6.

Exemplo de detecção de Run no vetor de entrada.

Observação: As informações dos Runs são armazenados em uma pilha nessa fase, como é detalhado na próxima seção.

Merge

Essa fase terá como entrada um vetor dividido' em Runs. Se a organização dos dados no vetor original for mais ou menos randômica, o tamanho dos Runs será aproximadamente o valor Minrun, e se o vetor tiver intervalos ordenados, o tamanho de alguns Runs excederá o valor de Minrun. Agora, todos os Runs precisam ser combinados para gerar o vetor completamente ordenado. Para isso, dois requisitos precisam ser satisfeitos:

1. Runs de tamanho relativamente iguais devem ser combinados, para que ganhe-se em eficiência.
2. A estabilidade do algoritmo deve ser mantida, isto é, sem mudanças inúteis (por exemplo, dois números iguais consecutivos não devem trocar lugar).

Isto é feito da seguinte maneira:

1. Cria-se uma pair stack <Posição do primeiro elemento do Run>-<Tamanho do Run>.
2. Insere-se o Run atual à pair stack.
3. Avalia se deve ser feito o merge.
   1. Avaliação: Sejam X, Y e Z os 3 primeiros Runs da pair stack; X > Y + Z e Y > Z. Se uma das duas condições não é satisfeita, então é feito o merge do Run Y com o Run de menor tamanho entre X e Z.
4. Para qualquer Run que não tenha sido considerado, basta tomá-lo e ir para o passo 2 até que reste apenas um Run na pilha (que é o vetor final já ordenado).

Otimizações

Algumas otimizações são feitas no MergeSort utilizado no TimSort visando diminuir o custo do algoritmo, mais precisamente o espaço de memória adicional e o número de comparações. Em algumas implementações, geralmente cria-se um vetor temporário cujo tamanho é dado pela soma dos dois sub-vetores de entrada. Porém isso não é necessário quando deseja-se fazer o merge de dois sub-vetores cujos elementos são consecutivos, pois criar um vetor temporário com o tamanho do menor sub-vetor é suficiente. O processo de merge pode ser feito da seguinte forma:

1. Um vetor temporário é criado com o tamanho do menor dos dois Runs que são combinados.
2. Copia-se o Run mais curto para o vetor temporário.
3. Marca-se a posição corrente com os primeiros elementos do maior Run e do "Run" temporário.
4. Em cada passo seguinte compare os primeiros elementos do maior Run e do Run temporário e mova o menor para o vetor ordenado. Move-se (incrementa) o endereço base do Run que teve o elemento movido.
5. Repete o passo 4 até um dos Runs esvaziar.
6. Adiciona todos os elementos do Run remanescente para o final do Run ordenado.

Processo de merge no TimSort

Caso o Run da direita seja menor, a comparação é feita marcando o endereço base do Run da esquerda e do Run temporário na última posição válida e ambos os vetores são percorridos da direita para a esquerda, sempre buscando o maior elemento em vez do menor.

O processo de merge apresentado supre as necessidades do algoritmo, mas existe um cenário onde ele pode ser otimizado. Suponha-se que dois Runs, A = {1000000,1000001} e B = {0,1,2,3,...,999999}  serão combinados. Um Run temporário de comprimento 2 é criado e recebe os elementos de A. Ao comparar-se os primeiros elementos de A e B é verificado que os elementos de B sempre serão menores, mas mesmo assim, 1 milhão de comparações são feitas, um custo que pode ser significante ao considerar-se grandes quantidades de elementos a serem ordenados. Uma maneira de contornar esse cenário seria percorrer o Run B de forma binária ao detectar-se esse comportamento.

Essa técnica funciona da seguinte forma:

1. Inicia-se o MergeSort como descrito nos passos anteriores.
2. Em cada movimento de um elemento do Run temporário ou do Run maior para o ordenado, o Run de onde o elemento foi movido é gravado. Isso gerenciamento pode ser feito atribuindo uma flag para cada Run e manipulá-las conforme os elementos são movidos.
3. Se uma quantidade X de elementos foi movida de um mesmo Run para o vetor ordenado supõe-se que o próximo elemento também provirá desse Run. Assim, para que operações desnecessárias sejam evitadas, em vez de percorrer o Run B linearmente, ele será percorrido de forma binária ($2^{i}$, com $i$ começando em $0$ e sendo incrementado a cada passo). Isso é feito até que o elemento corrente do Run B seja maior que o primeiro elemento do Run A, ou $2^{i}$ ultrapasse o tamanho do vetor. O valor de X pode ser fixado pelo usuário, mas sugere-se um valor próximo a 8.
4. Finalmente, os dados do Run A podem ser movidos em massa para o Run ordenado (o que pode ser mais eficiente do que mover os elementos separadamente, além de evitar uma exaustiva e desnecessária comparação linear). O endereço base do Run A é definido para a posição $2^{n-1}+1$, que é a posição seguinte à do último elemento que satisfez o "galopeamento binário", quando uma das condições de paradas do ponto 3 são alcançadas.

Galopeamento binário adotado no processo de merge do TimSort.

O galopeamento binário é uma técnica que minimiza o custo de comparações, entretanto deve ser chamada apenas quando percebe-se que os dados apresentam o padrão em que ela pode ser empregada. Caso essa função fosse chamada em todos os casos, seriam exigidas mais comparações do que a busca linear. Nota-se também que caso o Run da esquerda seja menor, o galopeamento binário é feito da esquerda para a direita, caso contrário é feito no sentido oposto.

Análise de Complexidade

A análise de complexidade aqui presente, é baseada no artigo, onde o autor prova que o custo de comparações para o pior caso no TimSort é $O(nlogn)$.

Considerações do autor:

1. O merge considera o Run como sendo um único elemento, e neste caso o custo de decomposição de cada Run será constante.
2. O custo de dois Runs é definido como $c(R,R0)-1$, onde $c(R,R0)=|R|+|R0|$.
3. O autor não utiliza o tamanho dos Runs como sendo Minrun, ou seja, ele não usa tamanhos artificiais de Runs, apenas considera Runs que realmente estejam originalmente ordenados. Logo não existe o custo relacionado à ordenação feita pelo Insertion sort.
4. Não são consideradas as otimizações do merge. Isso não implica mudanças da análise do pior caso.

O autor também define um conjunto de regras, propostas no trabalho, que visavam tornar o algoritmo do TimSort correto após a detecção de um erro gerado na implementação usada na linguagem Java. Abaixo são apresentadas as regras e as implicações caso as mesmas NÃO sejam satisfeitas, onde $W,X,Y,\mathrm {Z}$ são os 4 elementos que estão no topo da pilha:

$\rho 1:=|X|\geq |\mathrm {Z} |\longrightarrow merge(X,Y)$

$\rho 2:=|X|>|Y|+|\mathrm {Z} |\longrightarrow merge(Y,Z)$

$\rho 3:=|W|>|X|+|Y|\longrightarrow merge(Y,Z)$

$\rho 4:=|Y|>|\mathrm {Z} |\longrightarrow merge(Y,Z)$

Baseado em algumas observações e heurísticas dadas pelas regras utilizadas para gerenciar as estratégias de merge entre os Runs, o autor chega na seguinte equação:

${\textstyle C\geq \sum _{i=1}^{l}3i|x_{i}|}$

onde, $C$ é o custo da relação, $l$ é o tamanho da pilha e $|x_{i}|$ é o tamanho do i-ésimo Run na pilha. O autor conclui que o custo dessa equação $O(nlogn)$, seguindo o seguinte raciocínio:

• A soma do tamanho dos Runs terá um custo aproximado a $n$.
• A distribuição dos Runs na pilha, tendem a formar uma sequência crescente, onde sempre o elemento na posição $i$ será no mínimo a soma dos dois elementos anteriores na pilha, o que caracteriza um comportamento semelhante à sequência de Fibonacci. Com essa característica, o valor relacionado a $l$ será limitado superiormente por $log(n)$.

Como o conteúdo do somatório é uma multiplicação dessas duas relações, o custo inferido é $O(nlogn)$.

Agora, a estratégia que o autor usa para provar que o custo de comparações do TimSort também é $O(nlogn)$, é subtrair $c(R,R0)$ de $C$ para todos os merges que são feitos, e caso no final do algoritmo o valor de $C$ seja maior que $0$, então o custo de comparações também é limitado superiormente por $nlogn$. O que após provar para todas as regras de merge, constata-se que é verdade.

Implementações

C++:

#include<bits/stdc++.h>
using namespace std;
const int RUN = 32; // Initialising the RUN to get chunks
void insertionSort(int arr[], int left, int right) // Implementing insertion
sort for RUN size chunks{
   for (int i = left + 1; i <= right; i++){
      int t = arr[i];
      int j = i - 1;
      while (j >= left && t < arr[j]){
         arr[j+1] = arr[j--];
      }
      arr[j+1] = t;
   }
}
void merge(int arr[], int l, int m, int r) // using the merge function the
sorted chunks of size 32 are merged into one{
   int len1 = m - l + 1, len2 = r - m;
   int left[len1], right[len2];
   for (int i = 0; i < len1; i++)
      left[i] = arr[l + i]; // Filling left array
   for (int i = 0; i < len2; i++)
      right[i] = arr[m + 1 + i]; // Filling right array
   int i = 0;
   int j = 0;
   int k = l;
   while (i < len1 && j < len2) // Iterate into both arrays left and right{
      if (left[i] <= right[j]) // IF element in left is less then increment i by pushing into larger array{
         arr[k] = left[i];
         i++;
      } else {
         arr[k] = right[j]; // Element in right array is greater
         increment j
         j++;
      }
      k++;
   }
   while (i < len1) // This loop copies remaining element in left array{
      arr[k] = left[i];
      k++;
      i++;
   }
   while (j < len2) // This loop copies remaining element in right array{
      arr[k] = right[j];
      k++;
      j++;
   }
}
void timSortAlgo(int arr[], int n){
   for (int i = 0; i < n; i+=RUN) insertionSort(arr, i, min((i+31), (n-1))); //Call insertionSort()
   for (int s = RUN; s < n; s = 2*s) // Start merging from size RUN (or 32). It will continue upto 2*RUN{
      // pick starting point of left sub array. We are going to merge
      arr[left..left+size-1]
      // and arr[left+size, left+2*size-1]
      // After every merge, we
      // increase left by 2*size
      for (int left = 0; left < n;left += 2*s){
         int mid = left + s - 1; // find ending point of left sub
         array mid+1 is starting point of right sub array
         int right = min((left + 2*s - 1), (n-1));
         merge(arr, left, mid, right); // merge sub array
         arr[left.....mid] & arr[mid+1....right]
      }
   }
}
void printArray(int arr[], int n){
   for (int i = 0; i < n; i++)
      cout << arr[i] << " ";
   cout << endl;
}
// Main function to implement timsort algorithm
int main(){
   int arr[] = {-2, 7, 15, -14, 0, 15, 0, 7, -7, -4, -13, 5, 8, -14, 12};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout << "The Original array- ";
   printArray(arr, n);
   // calling the timsortAlgo function to sort array
   timSortAlgo(arr, n);
   cout<<"After Sorting Array Using TimSort Algorithm- ";
   printArray(arr, n); // Calling print function
   return 0;
}

Ver também

• Merge sort
• Insertion sort
• Algoritmos de ordenação

Ligações externas

• Visualising Timsort - a fonte para a imagem desta página.