|
TimsortTimsort é 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.[1] Tim Peters descreve o algoritmo da seguinte forma[2]:
Como o merge sort, é um algoritmo de ordenação por comparação estável com uma complexidade de pior caso de .[3] De acordo com a teoria da Informação, nenhuma ordenação por comparação pode executar em menos de , no caso médio, o que exige que a ordenação por comparação tome um tempo de em dados aleatórios. No entanto, em dados do mundo real, o Timsort muitas vezes exige muito menos do que , porque ele tira vantagem do fato de que sublistas dos dados podem já estar em ordem ou ordem inversa.[4] IntroduçãoTimSort [2] é 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 passoO mecanismo do algoritmo pode ser explicado brevemente da seguinte maneira:
Observação: Algumas otimizações são feitas no passo 1, na divisão em sub-vetores, e no MergeSort. Definições do algoritmo:
Calculando os MinrunsO valor de Minrun é determinado com base no valor de N, seguindo os seguintes princípios:
No artigo da proposta do algoritmo[2] 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 RunsNessa 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 é:
 Observação: As informações dos Runs são armazenados em uma pilha nessa fase, como é detalhado na próxima seção. MergeEssa 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:
Isto é feito da seguinte maneira:
OtimizaçõesAlgumas 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:
 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, Essa técnica funciona da seguinte forma:
 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 ComplexidadeA 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 é . Considerações do autor:
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 são os 4 elementos que estão no topo da pilha:
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:
onde, é o custo da relação, é o tamanho da pilha e é o tamanho do i-ésimo Run na pilha. O autor conclui que o custo dessa equação , seguindo o seguinte raciocínio:
Como o conteúdo do somatório é uma multiplicação dessas duas relações, o custo inferido é . Agora, a estratégia que o autor usa para provar que o custo de comparações do TimSort também é , é subtrair de para todos os merges que são feitos, e caso no final do algoritmo o valor de seja maior que , então o custo de comparações também é limitado superiormente por . O que após provar para todas as regras de merge, constata-se que é verdade. ImplementaçõesC++:#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émReferências
Ligações externas
|
