Estruturas de Dados e Algoritmos de Ordenação

Prévia do material em texto

2. Referencial Teórico
2.1 LIFO e FIFO
Para organizar os elementos em aplicações é necessária a escolha de uma estrutura de dados para regulamentar a entrada e saída das informações.
LIFO usa uma política de entrada e saída como uma pilha, significa ‘Last In, First Out’, ou seja, o último elemento é o primeiro a sair.
Ao contrário do que acontece com o vetor, a definição da pilha compreende a inserção e a eliminação de itens, de modo que uma pilha é um objeto dinâmico, constantemente mutável. Por conseguinte, surge então a pergunta: como uma pilha muda? A definição especifica que uma única extremidade da pilha é designada como o topo da pilha. (Estruturas de Dados Usando C Cap. 2 , pag.86)
É um método simples que vai eliminando o último elemento à medida que um novo é inserido. Como na figura abaixo:
Figura 1
Fonte: https://www.revista-programar.info/wp-content/uploads/2014/12/eds-genericas-pilha-2.png, retirado em: 22/09/2019
As operações mais utilizadas são de criar e verificar se a pilha está vazia, inserir novo elemento empilhando sempre no topo ou desempilhando se a função desejada é excluir e verificar qual o último elemento.
No caso do exemplo acima pop é usado para remover o elemento que estava no topo (c), push insere o elemento (d) empilhando acima de a e b e posteriormente utiliza-se pop novamente para remover o d.
FIFO significa ‘First In, First Out’, ele insere o elemento no final da fila e elimina outro no começo. Diferente da pilha onde é inserido e eliminado a que está no topo.
Ela é uma prima próxima da pilha, pois os itens são inseridos e removidos de acordo com o princípio de que o primeiro que entra é o primeiro que sai - First in, First out (FIFO). O conceito de fila existe no mundo real, vide exemplos como filas de banco, pedágios, restaurantes etc. ( Estrutura de Dados com Algoritmos C, pag.48)
As funções são parecidas: criar, inserir, excluir. Contudo é diferente na forma como o elemento é organizado como na figura abaixo.
Figura 2
Fonte: http://www.ppgia.pucpr.br/~laplima/ensino/tap/contents/images/filas/fila_def.png, retirado em: 22/09/2019
Ao contrário da pilha o elemento novo é inserido no final e ao realizar a remoção é o primeiro item, no caso “A” que sai.
2.2 Algoritmos de ordenação
Algoritmo de ordenação em ciência da computação é um algoritmo que coloca os elementos de uma dada sequência em uma certa ordem -- em outras palavras, efetua sua ordenação completa ou parcial. As ordens mais usadas são a numérica e a lexicográfica.
Existem várias razões para se ordenar uma sequência. Uma delas é a possibilidade se acessar seus dados de modo mais eficiente.
Insertion Sort, ou ordenação por inserção, é o algoritmo de ordenação que, dado uma estrutura (array, lista) constrói uma matriz final com um elemento de cada vez, uma inserção por vez. Assim como algoritmos de ordenação quadrática, é bastante eficiente para problemas com pequenas entradas, sendo o mais eficiente entre os algoritmos desta ordem de classificação.
Podemos fazer uma comparação do Insertion Sort com o modo de como algumas pessoas organizam um baralho num jogo de cartas. Imagine que você está jogando cartas. Você está com as cartas na mão e elas estão ordenadas. Você recebe uma nova carta e deve colocá-la na posição correta da sua mão de cartas, de forma que as cartas obedeçam a ordenação.
A cada nova carta adicionada à sua mão de cartas, a nova carta pode ser menor que algumas das cartas que você já tem na mão ou maior, e assim, você começa a comparar a nova carta com todas as cartas na sua mão até encontrar sua posição correta. Você insere a nova carta na posição correta, e, novamente, sua mão é composta de cartas totalmente ordenadas. Então, você recebe outra carta e repete o mesmo procedimento. Então outra carta, e outra, e assim por diante, até você não receber mais cartas.
Esta é a ideia por trás da ordenação por inserção. Percorra as posições do array, começando com o índice 1 (um). Cada nova posição é como a nova carta que você recebeu, e você precisa inseri-la no lugar correto no subarray ordenado à esquerda daquela posição.
Características 
Apesar de ser menos eficiente que algoritmos como Merge Sort e Quick Sort (de ordem O(nlog(n))), o Insertion Sort possui algumas características consideráveis:
	É de simples implementação, leitura e manutenção;
	In-place: Apenas requer uma quantidade constante de O(1) espaço de memória adicional;
	Estável: Não muda a ordem relativa de elementos com valores iguais;
	Útil para pequenas entradas;
	Muitas trocas, e menos comparações;
	Melhor caso: O(n), quando a matriz está ordenado;
	Médio caso: O(n²/4), quando a matriz tem valores aleatórios sem ordem de classificação (crescente ou decrescente);
	Pior caso: O(n²), quando a matriz está em ordem inversa, daquela que deseja ordenar.
Análise com outros algoritmos de ordenação por comparação e troca[editar | editar código-fonte]
Em termos de comparação com outros algoritmos de ordenação, o Insertion sort e o Bubble sort atingem O(n) em seus melhores casos, diferente do Selection sort que é O(n²) em todos os seus casos (melhor, médio e pior caso).
	Algoritmo
	Complexidade
	
	Melhor
	Médio
	Pior
	Insertion sort
	O(n)
	O(n2)
	O(n2)
	Bubble sort
	O(n)
	O(n2)
	O(n2)
	Selection sort
	O(n2)
	O(n2)
	O(n2)
Obs.: O BubbleSort atinge O(n) em seu melhor caso, quando o vetor já está inteiramente ordenado! Então é necessário apenas uma verificação básica sobre todo o vetor, o que representa um custo de O(n).
Análise Matemática[editar | editar código-fonte]
Para a ordenação de uma matriz ordenado randomicamente com diferentes chaves, o algoritmo - Insertion Sort-, se utiliza de ¼ N² comparações e ½ N² trocas. {\displaystyle \sum _{k=1}^{i}k={\frac {(1)}{i}}{\frac {i(i+1)}{2}}={\frac {(i+1)}{2}}}{\displaystyle \sum _{k=1}^{i}k={\frac {(1)}{i}}{\frac {i(i+1)}{2}}={\frac {(i+1)}{2}}}
Para o caso médio, assume que todas as permutações de entrada são igualmente prováveis. Com a auxílio de funções geradoras, o caso médio do Insertion sort é equivalente a:
{\displaystyle B(z)=zB(z)+{\frac {z}{2}}\sum _{n=>0}kz^{k}=zB(z)+{\frac {1}{2}}{\frac {z^{2}}{(1-z)^{2}}}}{\displaystyle B(z)=zB(z)+{\frac {z}{2}}\sum _{n=>0}kz^{k}=zB(z)+{\frac {1}{2}}{\frac {z^{2}}{(1-z)^{2}}}}, onde {\displaystyle B(z)}{\displaystyle B(z)} é a função geradora correspondente ao número total de inversões.
Para o melhor caso (itens já ordenados) temos; {\displaystyle \sum _{i=1}^{n-1}1=n-1=O(n)}{\displaystyle \sum _{i=1}^{n-1}1=n-1=O(n)}
Pior caso (itens em ordem reversa) temos: {\displaystyle \sum _{i=1}^{n-1}i={\frac {(n-1)(n)}{2}}={\frac {n^{2}}{2}}-{\frac {n}{2}}=O(n^{2})}{\displaystyle \sum _{i=1}^{n-1}i={\frac {(n-1)(n)}{2}}={\frac {n^{2}}{2}}-{\frac {n}{2}}=O(n^{2})}
Matrizes Parcialmente Ordenadas[editar | editar código-fonte]
Realiza inversões de pares de chaves - keys - que estão fora de ordem, exemplo:
A E E L M O T R X P S
Uma matriz é parcialmente ordenado se o número de inversões é <=CN. Onde, c é o número de componentes desta matriz. Exemplo:
 · Um subarray de tamanho 10 é adicionado a um array ordenado de tamanho N.
 · Um array de tamanho N, com apenas 10 entradas desordenadas.
Para um array ou matriz parcialmente ordenado, o Insertion Sort ocorre em um tempo linear. Prova:
 O Número de trocas é igual ao seu número de inversões.
 O Número de comparações = trocas + (N - 1);
 Logo, o seu número de comparações e trocas são lineares.
Vantagens e Desvantagens[editar | editar código-fonte]
Vantagens[editar | editar código-fonte]
	É o método a ser utilizado quando o arquivo está "quase" ordenado
	É um bom método quando se desejar adicionar poucos elementos em um arquivo já ordenado, pois seu custo é linear.
	O algoritmo de ordenação por inserção é estável.
Desvantagens[editar | editar código-fonte]
	Alto custo de movimentação de elementos no vetor.
Implementações[editar | editar código-fonte]
Pseudocódigo[editar | editar código-fonte]
Segue uma versão simples do pseudocódigo do algoritmo, com vetores começando em zero:FUNÇÃO INSERTION_SORT (A[], tamanho)
 VARIÁVEIS
 i, j, eleito
 PARA i <- 1 ATÉ (tamanho-1) FAÇA
 eleito <- A[i];
 j <- i-1;
 ENQUANTO ((j>=0) E (eleito < A[j])) FAÇA
 A[j+1]:= A[j];
# Elemento de lista numerada
 j:=j-1;
 FIM_ENQUANTO
 A[j+1] <- eleito;
 FIM_PARA
FIM
Nessa versão é acrescentada uma verificação para saber se precisa "inserir" o "eleito" na sua nova posição, ou seja, se não houve trocas, não precisa reescrever o valor, já que ele já estará no lugar certo.
FUNÇÃO INSERTION_SORT (A[], tamanho)
 VARIÁVEIS
 i, ,j
 eleito
 PARA i <- 1 ATÉ tamanho-1 FAÇA
 eleito <- A[i];
 j <- i-1;
 ENQUANTO ((j>=0) E (eleito < A[j])) FAÇA
 A[j+1]:=v[j];
 j:=j-1;
 FIM_ENQUANTO
 SE ((j) <> (i-1) ENTÃO //se for diferente teve troca de posições anteriormente
 A[j+1] <- eleito; //escreve na nova posição
 FIM_PARA
FIM
C[editar | editar código-fonte]
#include <math.h> 
#include <stdio.h> 
void insertionSort(int arr[], int n){ 
 int i, key, j; 
 for (i = 1; i < n; i++) { 
 key = arr[i]; 
 j = i - 1; 
 while (j >= 0 && arr[j] > key) { 
 arr[j + 1] = arr[j]; 
 j = j - 1; 
 } 
 arr[j + 1] = key; 
 } 
} 
void printArray(int arr[], int n){ 
 int i; 
 for (i = 0; i < n; i++) 
 printf("%d ", arr[i]); 
 printf("\n"); 
} 
int main(){ 
 int arr[] = { 12, 11, 13, 5, 6 }; 
 int n = sizeof(arr) / sizeof(arr[0]); 
 insertionSort(arr, n); 
 printArray(arr, n); 
 return 0; 
}
C++[editar | editar código-fonte]
Utilizando os recursos mais recentes da linguagem é possível implementar da seguinte maneira:
void insertion_sort(std::vector<int> &vetor) {
 for (int i = 1; i < vetor.size(); i++) {
		int escolhido = vetor[i];
		int j = i - 1;
		
		while ((j >= 0) && (vetor[j] > escolhido)) {
			vetor[j + 1] = vetor[j];
			j--;
		}
		
		vetor[j + 1] = escolhido;
	}
}
Como o algoritmo toma o parâmetro vetor como referência não há sentido em retorná-lo já que ele ordena o vetor passado.
Java[editar | editar código-fonte]
Nessa versão em Java, apresentamos o Insertion sort "in place", ou seja, a ordenação ocorre no próprio vetor.
public void insertionSort(int[] vetor){
		
		for (int i = 1; i < vetor.length; i++){
			
			int aux = vetor[i];
			int j = i;
			
			while ((j > 0) && (vetor[j-1] > aux)){
				vetor[j] = vetor[j-1];
				j -= 1;
			}
			vetor[j] = aux;
 
		}
	
	}
Python[editar | editar código-fonte]
def insertion_sort( lista ):
 for i in range( 1, len( lista ) ):
 chave = lista[i]
 k = i
 while k > 0 and chave < lista[k - 1]:
 lista[k] = lista[k - 1]
 k -= 1
 lista[k] = chave
C#[editar | editar código-fonte]
public void InsertionSort(int[] vetor)
{
 for (var i = 1; i < vetor.Length; i++)
 {
 var aux = vetor[i];
 var j = i-1;
 while (j >= 0 && vetor[j] > aux)
 {
 vetor[j+1] = vetor[j];
 j -= 1;
 }
 vetor[j+ 1] = aux;
 }
}
A ordenação por seleção (do inglês, selection sort) é um algoritmo de ordenação baseado em se passar sempre o menor valor do vetor para a primeira posição (ou o maior dependendo da ordem requerida), depois o de segundo menor valor para a segunda posição, e assim é feito sucessivamente com os {\displaystyle n-1}n-1 elementos restantes, até os últimos dois elementos.
Descrição do algoritmo[editar | editar código-fonte]
É composto por dois laços, um laço externo e outro interno. O laço externo serve para controlar o índice inicial e o interno percorre todo o vetor. Na primeira iteração do laço externo o índice começa de 0 e cada iteração ele soma uma unidade até o final do vetor e o laço mais interno percorre o vetor começando desse índice externo + 1 até o final do vetor. Isso ficará mais explícito no exemplo.
Exemplo:
vetor = 9 - 7 - 8 - 1 - 2 - 0 - 4
O primeiro laço o índice inicial é 0. O laço mais interno começa do índice 1 (índice_inicial_externo + 1) e percorre o vetor até achar o menor elemento, neste caso o número zero. O zero passa para a posição inicial do vetor que na primeira iteração do laço é 0.
0 - 7 - 8 - 1 - 2 - 9 - 4
Ao fim do laço interno, o laço externo incrementa uma unidade, agora a posição inicial do vetor passa a ser 1, pois o zero já se encontra no lugar dele, não é preciso mais fazer verificações pois ele é o menor elemento deste vetor. Agora o processo se repete, buscando o segundo menor elemento, neste caso o um.
0 - 1 - 8 - 7 - 2 - 9 - 4
Consequentemente o terceiro menor, quarto menor,...
Assim sucessivamente até o vetor está ordenado.
0 - 1 - 2 -7 - 8 - 9 - 4
...
0 - 1 - 2 - 4 - 8 - 9 - 7
...
0 - 1 - 2 - 4 - 7 - 9 - 8
...
0 - 1 - 2 - 4 - 7 - 8 - 9
Complexidade[editar | editar código-fonte]
O selection sort compara a cada interação um elemento com os outros, visando encontrar o menor. Dessa forma, podemos entender que não existe um melhor caso mesmo que o vetor esteja ordenado ou em ordem inversa serão executados os dois laços do algoritmo, o externo e o interno. A complexidade deste algoritmo será sempre {\displaystyle O(n^{2})}O(n^{2}) enquanto que, por exemplo, os algoritmos heapsort e mergesort possuem complexidades {\displaystyle O(n\log n).}{\displaystyle O(n\log n).}
Vantagens[editar | editar código-fonte]
	Ele é um algoritmo simples de ser implementado em comparação aos demais.
	Não necessita de um vetor auxiliar (in-place).
	Por não usar um vetor auxiliar para realizar a ordenação, ele ocupa menos memória.
	Ele é uns dos mais velozes na ordenação de vetores de tamanhos pequenos.
Desvantagens[editar | editar código-fonte]
	Ele é um dos mais lentos para vetores de tamanhos grandes.
	Ele não é estável.
	Ele faz sempre {\displaystyle (n^{2}-n)/2}{\displaystyle (n^{2}-n)/2} comparações, independente do vetor está ordenado ou não.
Exemplos de códigos[editar | editar código-fonte]
Implementação em C (linguagem de programação):
void selection_sort(int num[], int tam) { 
 int i, j, min, aux;
 for (i = 0; i < (tam-1); i++) 
 {
 min = i;
 for (j = (i+1); j < tam; j++) {
 if(num[j] < num[min]) 
 min = j;
 }
 if (num[i] != num[min]) {
 aux = num[i];
 num[i] = num[min];
 num[min] = aux;
 }
 }
}
Implementação em C++, colocando os menores no início:
void SelectionSort(int vetor[], int tam) {
 for (int indice = 0; indice < tam; ++indice) {
 int indiceMenor = indice;
 for (int indiceSeguinte = indice+1; indiceSeguinte < tam; ++indiceSeguinte) {
 if (vetor[indiceSeguinte] < vetor[indiceMenor]) {
 indiceMenor = indiceSeguinte;
 }
 }
 int aux = vetor[indice];
 vetor[indice] = vetor[indiceMenor];
 vetor[indiceMenor] = aux;
 }
}
O bubble sort, ou ordenação por flutuação (literalmente "por bolha"), é um algoritmo de ordenação dos mais simples. A ideia é percorrer o vector diversas vezes, e a cada passagem fazer flutuar para o topo o maior elemento da sequência. Essa movimentação lembra a forma como as bolhas em um tanque de água procuram seu próprio nível, e disso vem o nome do algoritmo.
No melhor caso, o algoritmo executa {\displaystyle n}n operações relevantes, onde {\displaystyle n}n representa o número de elementos do vector. No pior caso, são feitas {\displaystyle n^{2}}n^2 operações. A complexidade desse algoritmo é de ordem quadrática. Por isso, ele não é recomendado para programas que precisem de velocidade e operem com quantidade elevada de dados.
Pseudocódigo[editar | editar código-fonte]
Este algoritmo percorre a lista de itens ordenáveis do início ao fim, verificando a ordem dos elementos dois a dois, e trocando-os de lugar se necessário. Percorre-se a lista até que nenhum elemento tenha sido trocado de lugar na passagem anterior.
procedure bubbleSort( A : lista de itens ordenaveis ) defined as:
 do
 trocado := false
 for each i in 0 to length( A ) - 2 do:
 // verificar se os elementos estão na ordem certa
 if A[ i ] > A[ i + 1 ] then
 // trocar elementos de lugar
 trocar( A[ i ], A[ i + 1 ] )
 trocado := true
 end if
 end for
 // enquanto houver elementos sendo reordenados.
 while trocado
end procedure
Uma versão em C, recursiva :
Entra: tamanho do vetor a ser organizado e vetor de números.
Saida: vetor organizado.
 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 void swap(int *a, int *b){ 
 4 int temp = *a; 
 5 *a = *b; 
 6 *b = temp; 
 7 } 
 8 void bubbleSort(int *v, intn){ 
 9 if (n < 1)return; 
10 
11 for (int i=0; i<n; i++) 
12 if (v[i] > v[i+1]) 
13 swap(&v[i], &v[i+1]); 
14 bubbleSort(v, n-1); 
15 } 
16 
17 int main(){
18 int tam,i,*v;
19 scanf("%d",&tam);
20 v=(int*)malloc(tam*sizeof(int));
21 for(i=0;i<tam;i++)scanf("%d",&v[i]);
22 bubbleSort(v,tam-1);
23 for(i=0;i<tam;i++)printf("%d ",v[i]);
24 return 0;
25 }
O algoritmo Comb sort (ou Combo sort ou ainda algoritmo do pente[1]) é um algoritmo de ordenação relativamente simples, e faz parte da família de algoritmos de ordenação por troca. Foi desenvolvido em 1980 por Wlodzimierz Dobosiewicz. Mais tarde, foi redescoberto e popularizado por Stephen Lacey e Richard Box em um artigo publicado na revista Byte em Abril de 1991. O Comb sort melhora o Bubble sort, e rivaliza com algoritmos como o Quicksort. A ideia básica é eliminar as tartarugas ou pequenos valores próximos do final da lista, já que em um bubble sort estes retardam a classificação tremendamente. (Coelhos, grandes valores em torno do início da lista, não representam um problema no bubble sort).
O Algoritmo repetidamente reordena diferentes pares de itens, separados por um salto, que é calculado a cada passagem. Método semelhante ao Bubble Sort, porém mais eficiente.
Na Bubble sort, quando quaisquer dois elementos são comparados, eles sempre têm um gap (distância um do outro) de 1. A ideia básica do Comb sort é que a diferença pode ser muito mais do que um. (O Shell sort também é baseado nesta ideia, mas é uma modificação do insertion sort em vez do bubble sort).
O gap (intervalo) começa como o comprimento da lista a ser ordenada dividida pelo fator de encolhimento (em geral 1,3; veja abaixo), e a lista é ordenada com este valor (arredondado para um inteiro se for necessário) para o gap. Então, a diferença é dividida pelo fator de encolhimento novamente, a lista é ordenada com este novo gap, e o processo se repete até que a diferença seja de 1. Neste ponto, o Comb sort continua usando um espaço de 1 até que a lista esteja totalmente ordenada. A fase final da classificação é, portanto, equivalente a um bubble sort, mas desta vez a maioria dos elementos "tartarugas" já foram tratados, assim o bubble sort será eficiente.
Fator de encolhimento[editar | editar código-fonte]
O fator de encolhimento tem um grande efeito sobre a eficiência do Comb sort. No artigo original, os autores sugeriram 1,3 depois de tentar algumas listas aleatórias e encontrando-se, geralmente as mais eficazes. Um valor muito pequeno retarda o algoritmo porque mais comparações devem ser feitas, ao passo que um valor muito grande não pode tratar um número suficiente de "tartarugas" para ser prático.
O texto descreve uma melhoria no comb sort usando o valor base {\displaystyle 1/\left(1-{\frac {1}{e^{\varphi }}}\right)\approx 1.247330950103979}{\displaystyle 1/\left(1-{\frac {1}{e^{\varphi }}}\right)\approx 1.247330950103979} como fator de encolhimento. Ele também contém uma implementação em pseudocódigo com uma tabela de gaps pré-definidos.
Variações[editar | editar código-fonte]
Combsort11[editar | editar código-fonte]
Com um fator de encolhimento de cerca de 1,3, só existem três caminhos possíveis para a lista de gaps terminar: (9, 6, 4, 3, 2, 1), (10, 7, 5, 3, 2, 1), ou (11, 8, 6, 4, 3, 2, 1). Experimentos mostram que melhorias significativas de velocidade podem ser feitas se o gap for definido como 11, sempre que, caso contrário, tornar-se 9 ou 10. Esta variação é chamada Combsort11.
Se uma das sequências que começam com nove ou 10, forem utilizadas, o passo final, com um intervalo de 1 tem menor probabilidade de ordenar os dados sendo necessário então outro passo com gap de 1. Os dados são ordenados quando não ocorrem mais trocas durante uma passagem com gap= 1.
Também é possível usar uma tabela pré-definida, para escolher quais gaps a utilizar em cada passo.
Combsort com diferentes finais[editar | editar código-fonte]
Como muitos outros algoritmos eficientes de ordenação (como o quick sort ou merge sort), o comb sort é mais eficaz em suas passagens anteriores do que durante o passo final, quando ele se assemelha a um bubble sort. O Comb sort pode ser mais eficaz se o método de classificação é mudado uma vez que os gaps cheguem a um número pequeno o suficiente. Por exemplo, uma vez que a diferença chegue a um tamanho de cerca de 10 ou menor, parando o comb sort e fazendo um simples gnome sort ou cocktail sort, ou, melhor ainda, um insertion sort, se aumentará a eficiência global da ordenação.
Outra vantagem deste método é que não há necessidade de manter o controle das operações de troca durante os passos da classificação para saber se a ordenação deve parar ou não.
Implementações[editar | editar código-fonte]
C#[editar | editar código-fonte]
 1 public void Sort()
 2 {
 3 gap = (int)(values.Count / 1.3);
 4 int i = 0;
 5 while (gap > 0 && i != values.Count - 1)
 6 {
 7 i = 0;
 8 while ((i + gap) < values.Count)
 9 {
10 if (values[i].CompareTo(values[i + gap]) > 0)
11 {
12 Swap(i, (i + gap));
13 }
14 i++;
15 }
16 gap = (int)(gap / 1.3);
17 }
18 }
C++[editar | editar código-fonte]
Esta é uma implementação no estilo STL. Ele irá classificar qualquer intervalo entre a primeira e a última. Isso funciona com quaisquer iteradores posteriores, mas é mais eficaz com iteradores de acesso aleatório ou ponteiros.
template<class ForwardIterator>
void combsort ( ForwardIterator first, ForwardIterator last )
{
 static const double shrink_factor = 1.247330950103979;
 typedef typename std::iterator_traits<ForwardIterator>::difference_type difference_type;
 difference_type gap = std::distance(first, last);
 bool swaps = true;
 while ( (gap > 1) || (swaps == true) ){
 if (gap > 1)
 gap = static_cast<difference_type>(gap/shrink_factor);
 swaps = false;
 ForwardIterator itLeft(first);
 ForwardIterator itRight(first); std::advance(itRight, gap);
 for ( ; itRight!=last; ++itLeft, ++itRight ){
 if ( (*itRight) < (*itLeft) ){
 std::iter_swap(itLeft, itRight);
 swaps = true;
 }
 }
 }
}
Java[editar | editar código-fonte]
public static <E extends Comparable<? super E>> void sort(E[] input) {
 int gap = input.length;
 boolean swapped = true;
 while (gap > 1 || swapped) {
 if (gap > 1){
 gap = (int) (gap / 1.247330950103979);
 }
 int i = 0;
 swapped = false;
 while (i + gap < input.length) {
 if (input[i].compareTo(input[i + gap]) > 0) {
 E t = input[i];
 input[i] = input[i + gap];
 input[i + gap] = t;
 swapped = true;
 }
 i++;
 }
 }
}
C[editar | editar código-fonte]
void combo_sort(int matriz[], int tamanho) 
{
	int i, j, intervalo, trocado = 1;
	int aux;
	intervalo = tamanho;
	while (intervalo > 1 || trocado == 1)
	{
		intervalo = intervalo * 10 / 13;
		if (intervalo == 9 || intervalo == 10) intervalo = 11;
		if (intervalo < 1) intervalo = 1;
		trocado = 0;
		for (i = 0, j = intervalo; j < tamanho; i++, j++)
		{
			if (matriz[i] > matriz[j])
			{
				aux = matriz[i];
				matriz[i] = matriz[j];
				matriz[j] = aux;
				trocado = 1;
			}
		}
	}
}
Ruby[editar | editar código-fonte]
def comb_sort(list)
 shrink_factor = 1.247330950103979
 gap = list.size
 swapped = true
 until (gap == 1) && !swapped
 gap = gap / shrink_factor
 gap = 1 if gap < 1
 i = 0
 swapped = false
 until (i + gap) >= list.size
 if list[i] > list[i + gap]
 list[i], list[i + gap] = list[i + gap], list[i]
 swapped = true
 end
 i = i + 1
 end
 end
 list
end
2.3 Método escolhido
O merge sort, ou ordenação por mistura, é um exemplo de algoritmo de ordenação por comparação do tipo dividir-para-conquistar.
Sua ideia básica consiste em Dividir (o problema em vários subproblemas e resolver esses subproblemas através da recursividade) e Conquistar (após todos os subproblemas terem sido resolvidos ocorre a conquista que é a união das resoluções dos subproblemas). Como o algoritmo Merge Sort usa a recursividade, há um alto consumo de memória e tempo de execução, tornando esta técnica não muito eficiente em alguns problemas.
Características[editar | editar código-fonte]
Algoritmo[editar | editar código-fonte]
Ostrês passos úteis dos algoritmos de divisão e conquista, ou divide and conquer, que se aplicam ao merge sort são:
	Dividir: Calcula o ponto médio do sub-arranjo, o que demora um tempo constante {\displaystyle \Theta (1)}{\displaystyle \Theta (1)};
	Conquistar: Recursivamente resolve dois subproblemas, cada um de tamanho n/2, o que contribui com {\displaystyle 2T(n/2)}{\displaystyle 2T(n/2)} para o tempo de execução;
	Combinar: Unir os sub-arranjos em um único conjunto ordenado, que leva o tempo {\displaystyle \Theta (n)}{\displaystyle \Theta (n)}.
Equação de recorrência[editar | editar código-fonte]
https://upload.wikimedia.org/wikipedia/commons/thumb/4/4d/Rekursionsbaum.JPG/500px-Rekursionsbaum.JPG
Árvore de recursão
{\displaystyle T(n)={\begin{cases}\Theta (1),&{\text{se }}n{\text{ = 1}}\\2T(n/2)+\Theta (n),&{\text{se }}n>{\text{ 1}}\end{cases}}}{\displaystyle T(n)={\begin{cases}\Theta (1),&{\text{se }}n{\text{ = 1}}\\2T(n/2)+\Theta (n),&{\text{se }}n>{\text{ 1}}\end{cases}}}
Complexidade[editar | editar código-fonte]
	Complexidade de tempo: {\displaystyle \Theta (n\log n)}\Theta (n\log n).
	Complexidade de espaço: {\displaystyle \Theta (n)}{\displaystyle \Theta (n)}.
Demonstração da complexidade de tempo[editar | editar código-fonte]
{\displaystyle T(n)={\begin{cases}\Theta (1),&{\text{se }}n{\text{ = 1}}\\2T(n/2)+\Theta (n),&{\text{se }}n>{\text{ 1}}\end{cases}}}{\displaystyle T(n)={\begin{cases}\Theta (1),&{\text{se }}n{\text{ = 1}}\\2T(n/2)+\Theta (n),&{\text{se }}n>{\text{ 1}}\end{cases}}}
{\displaystyle {\begin{array}{l}T(n)={2^{1}}.T\left({\frac {n}{2^{1}}}\right)+1.n\\T(n)={2^{1}}.\left({2.T\left({\frac {n}{2^{2}}}\right)+{\frac {n}{2}}}\right)+n={2^{2}}.T\left({\frac {n}{2^{2}}}\right)+2.n\\T(n)={2^{2}}.\left({2.T\left({\frac {n}{2^{3}}}\right)+{\frac {n}{4}}}\right)+2.n={2^{3}}.T\left({\frac {n}{2^{3}}}\right)+3.n\\\quad \vdots \\T(n)={2^{h-1}}.\left({2.T\left({\frac {n}{2^{h}}}\right)+{\frac {n}{2^{h-1}}}}\right)+h.n={2^{h}}.T\left({\frac {n}{2^{h}}}\right)+h.n\end{array}}}{\displaystyle {\begin{array}{l}T(n)={2^{1}}.T\left({\frac {n}{2^{1}}}\right)+1.n\\T(n)={2^{1}}.\left({2.T\left({\frac {n}{2^{2}}}\right)+{\frac {n}{2}}}\right)+n={2^{2}}.T\left({\frac {n}{2^{2}}}\right)+2.n\\T(n)={2^{2}}.\left({2.T\left({\frac {n}{2^{3}}}\right)+{\frac {n}{4}}}\right)+2.n={2^{3}}.T\left({\frac {n}{2^{3}}}\right)+3.n\\\quad \vdots \\T(n)={2^{h-1}}.\left({2.T\left({\frac {n}{2^{h}}}\right)+{\frac {n}{2^{h-1}}}}\right)+h.n={2^{h}}.T\left({\frac {n}{2^{h}}}\right)+h.n\end{array}}}
Para que {\displaystyle T(1)=T\left({\frac {n}{n}}\right)=\Theta (1)}{\displaystyle T(1)=T\left({\frac {n}{n}}\right)=\Theta (1)} teremos que fazer com que {\displaystyle {2^{h}}=n\Rightarrow \lg {2^{h}}=\lg n\Rightarrow h=\lg n}{\displaystyle {2^{h}}=n\Rightarrow \lg {2^{h}}=\lg n\Rightarrow h=\lg n}
Então:
{\displaystyle T(n)={2^{h}}.T\left({\frac {n}{2^{h}}}\right)+n.h=n.T\left({\frac {n}{n}}\right)+n.\lg n=n.T\left(1\right)+n.\lg n=n.\Theta (1)+n.\lg n=\Theta (n.\lg n)}{\displaystyle T(n)={2^{h}}.T\left({\frac {n}{2^{h}}}\right)+n.h=n.T\left({\frac {n}{n}}\right)+n.\lg n=n.T\left(1\right)+n.\lg n=n.\Theta (1)+n.\lg n=\Theta (n.\lg n)}
Comparação com outros algoritmos de ordenação por comparação[editar | editar código-fonte]
Em comparação a outros algoritmos de divisão e conquista, como o Quicksort, o Merge apresenta a mesma complexidade. Já em comparação a algoritmos mais básicos de ordenação por comparação e troca (bubble, insertion e selection sort), o Merge é mais rápido e eficiente quando é utilizado sobre uma grande quantidade de dados[1]. Para entradas pequenas os algoritmos de ordenação por comparação mais básicos são pró-eficientes.
Abaixo uma tabela para comparação[2]:
	Algoritmo
	Tempo
	
	Melhor
	Médio
	Pior
	Merge sort
	{\displaystyle O(n\log n)}{\displaystyle O(n\log n)}
	{\displaystyle O(n\log n)}{\displaystyle O(n\log n)}
	{\displaystyle O(n\log n)}{\displaystyle O(n\log n)}
	Quick sort
	{\displaystyle O(n\log n)}{\displaystyle O(n\log n)}
	{\displaystyle O(n\log n)}{\displaystyle O(n\log n)}
	{\displaystyle O(n^{2})}O(n^{2})
	Bubble sort
	{\displaystyle O(n)}O(n)
	{\displaystyle O(n^{2})}O(n^{2})
	{\displaystyle O(n^{2})}O(n^{2})
	Insertion sort
	{\displaystyle O(n)}O(n)
	{\displaystyle O(n^{2})}O(n^{2})
	{\displaystyle O(n^{2})}O(n^{2})
	Selection sort
	{\displaystyle O(n^{2})}O(n^{2})
	{\displaystyle O(n^{2})}O(n^{2})
	{\displaystyle O(n^{2})}O(n^{2})
Obs.: O Bubble sort apresenta melhor caso como {\displaystyle O(n)}O(n)porque o algoritmo pode ser modificado de forma que, se a lista já estiver ordenada, basta apenas uma verificação básica que custa {\displaystyle O(n)}O(n)[3]. O Quick sort pode atingir um tempo de {\displaystyle O(n)}O(n)em um caso específico quando o particionamento é desequilibrado.
Observações[editar | editar código-fonte]
https://upload.wikimedia.org/wikipedia/commons/thumb/c/cc/Merge-sort-example-300px.gif/220px-Merge-sort-example-300px.gif
Exemplo de execução do merge sort.
	É possível implementar o merge sort utilizando somente um vetor auxiliar ao longo de toda a execução, tornando assim a complexidade de espaço adicional igual a {\displaystyle \Theta (n\log n)}{\displaystyle \Theta (n\log n)}.
	É um algoritmo estável na maioria das implementações, em que elas podem ser iterativas ou recursivas.
	É possível também implementar o algoritmo com espaço adicional {\displaystyle \Theta (1)}{\displaystyle \Theta (1)}.
	Algoritmo Criado por Von Neumann em 1945.
Desvantagens[editar | editar código-fonte]
	Utiliza funções recursivas;
	Gasto extra de memória. O algoritmo cria uma cópia do vetor para cada nível da chamada recursiva, totalizando um uso adicional de memória igual a {\displaystyle O(n\log n)}{\displaystyle O(n\log n)}.
Implementações do Mergesort[editar | editar código-fonte]
Pseudocódigo[editar | editar código-fonte]
MERGE-SORT(A, p, r)
 if p < r then
 q = ((p + r) / 2)
 Merge-Sort(A, p, q)
 Merge-Sort(A, q + 1, r)
 Merge(A, p, q, r)
Merge(A, p, q, r)
 n1 = q - p + 1
 n2 = r - q
 sejam L[1 ... n1 + 1] e R[1 ... n2 + 1]
 for i = 1 to n1
 L[i] = A[p + i - 1]
 for j = 1 to n2
 R[j] = A[q + j]
 i = 1
 j = 1
 for k = p to r
 if L[i] <= R[j] then A[k] = L[i]
 i = i + 1
 else A[k] = R[j]
 j = j + 1
Código em C[editar | editar código-fonte]
 1 void merge(int vetor[], int comeco, int meio, int fim) {
 2 int com1 = comeco, com2 = meio+1, comAux = 0, tam = fim-comeco+1;
 3 int *vetAux;
 4 vetAux = (int*)malloc(tam * sizeof(int));
 5 
 6 while(com1 <= meio && com2 <= fim){
 7 if(vetor[com1] < vetor[com2]) {
 8 vetAux[comAux] = vetor[com1];
 9 com1++;
10 } else {
11 vetAux[comAux] = vetor[com2];
12 com2++;
13 }
14 comAux++;
15 }
16 
17 while(com1 <= meio){ //Caso ainda haja elementos na primeira metade
18 vetAux[comAux] = vetor[com1];
19 comAux++;
20 com1++;
21 }
22 
23 while(com2 <= fim) { //Caso ainda haja elementos na segunda metade
24 vetAux[comAux] = vetor[com2];
25 comAux++;
26 com2++;
27 }
28 
29 for(comAux = comeco; comAux <= fim; comAux++){ //Move os elementos de volta para o vetor original
30 vetor[comAux] = vetAux[comAux-comeco];
31 }
32 
33 free(vetAux);
34 }
35 
36 void mergeSort(int vetor[], int comeco, int fim){
37 if (comeco < fim) {
38 int meio = (fim+comeco)/2;
39 
40 mergeSort(vetor, comeco, meio);
41 mergeSort(vetor, meio+1, fim);
42 merge(vetor, comeco, meio, fim);
43 }
44 }
Implementação em C++[editar | editar código-fonte]
void merge(int *saida, int *auxiliar, int inicio, int meio, int fim){
 int i, j, k;
 i = inicio;
 j = meio + 1;
 k = inicio;
 while(i <= meio && j <= fim){
 if(auxiliar[i] < auxiliar[j]){
 saida[k] = auxiliar[i];
 i++;
 }
 else{
 saida[k] = auxiliar[j];
 j++;
 }
 k++;
 }
 while(i <= meio){
 saida[k] = auxiliar[i];
 i++;
 k++;
 }
 while(j <= fim){
 saida[k] = auxiliar[j];
 j++;
 k++;
 }
 //Copia os elementos que foram ordenados para o auxiliar
 for(int p = inicio; p <= fim; p++)
 auxiliar[p] = saida [p];
}
void mergeSort(int *saida, int *auxiliar, int inicio, int fim){
 if(inicio< fim){
 int meio = (inicio + fim) / 2;
 mergeSort(saida, auxiliar, inicio, meio);
 mergeSort(saida, auxiliar, meio + 1, fim);
 merge(saida, auxiliar, inicio, meio, fim);
 }
}
Outra implementação em C++:
 1 void Juntar(int vetor[], int ini, int meio, int fim, int vetAux[]) {
 2 int esq = ini;
 3 int dir = meio;
 4 for (int i = ini; i < fim; ++i) {
 5 if ((esq < meio) and ((dir >= fim) or (vetor[esq] < vetor[dir]))) {
 6 vetAux[i] = vetor[esq];
 7 ++esq;
 8 }
 9 else {
10 vetAux[i] = vetor[dir];
11 ++dir;
12 }
13 }
14 //copiando o vetor de volta
15 for (int i = ini; i < fim; ++i) {
16 vetor[i] = vetAux[i];
17 }
18 }
19 
20 void MergeSort(int vetor[], int inicio, int fim, int vetorAux[]) {
21 if ((fim - inicio) < 2) return;
22 
23 int meio = ((inicio + fim)/2);
24 MergeSort(vetor, inicio, meio, vetorAux);
25 MergeSort(vetor, meio, fim, vetorAux);
26 Juntar(vetor, inicio, meio, fim, vetorAux);
27 }
28 
29 void MergeSort(int vetor[], int tamanho) { //função que o usuario realmente chama
30 //criando vetor auxiliar
31 int vetorAux[tamanho];
32 MergeSort(vetor, 0, tamanho, vetorAux);
33 }
Código em Java[editar | editar código-fonte]
 1 public class WikiMerge<T extends Comparable<T>>{
 2 	 /**
 3 	* Método que recebe um array de inteiros e dois inteiros referentes ao início e ao fim
 4 	* da ordenação desse array, o que nos garante o poder de escolher uma faixa do array
 5 	* para ser ordenado.
 6 	*
 7 	* @param array
 8 	* @param indiceInicio
 9 	* @param indiceFim
10 	*/
11 	public void ordena(T[] array, int indiceInicio, int indiceFim) {
12 
13 		// Condicional que verifica a validade dos parâmetros passados.
14 		if (array != null && indiceInicio < indiceFim && indiceInicio >= 0 &&
15 		 indiceFim < array.length && array.length != 0) {
16 			int meio = ((indiceFim + indiceInicio) / 2);
17 
18 			ordena(array, indiceInicio, meio);
19 			ordena(array, meio + 1, indiceFim);
20 
21 			merge(array, indiceInicio, meio, indiceFim);
22 		}
23 
24 	}
25 
26 	/**
27 	* O merge consiste na junção de duas listas já ordenadas.
28 	* Usa um array auxiliar.
29 	*
30 	* @param array
31 	* @param indiceInicio
32 	* @param meio
33 	* @param indiceFim
34 	*/
35 	public void merge(T[] array, int indiceInicio, int meio, int indiceFim) {
36 
37 		T[] auxiliar =(T[]) new Comparable[array.length];
38 		//Copiando o trecho da lista que vai ser ordenada
39 		for (int i = indiceInicio; i <= indiceFim; i++) {
40 			auxiliar[i] = array[i];
41 		}
42 
43 		//Índices auxiliares
44 		int i = indiceInicio;
45 		int j = meio + 1;
46 		int k = indiceInicio;
47 
48 		//Junção das listas ordenadas
49 		while (i <= meio && j <= indiceFim) {
50 			if (auxiliar[i].compareTo(auxiliar[j]) < 0) {
51 				array[k] = auxiliar[i];
52 				i++;
53 			} else {
54 				array[k] = auxiliar[j];
55 				j++;
56 			}
57 			k++;
58 		}
59 
60 		//Append de itens que não foram usados na Junção
61 		while (i <= meio) {
62 			array[k] = auxiliar[i];
63 			i++;
64 			k++;
65 		}
66 
67 		//Append de itens que não foram usados na Junção
68 		while (j <= indiceFim) {
69 			array[k] = auxiliar[j];
70 			j++;
71 			k++;
72 		}
73 	}
74 } 
75 
76 //teste
Código em Python[editar | editar código-fonte]
def mergeSort(lista):
 if len(lista) > 1:
 meio = len(lista)//2
 #também é valido: meio = int(len(lista)/2)
 listaDaEsquerda = lista[:meio]
 listaDaDireita = lista[meio:]
 mergeSort(listaDaEsquerda)
 mergeSort(listaDaDireita)
 i = 0
 j = 0
 k = 0
 while i < len(listaDaEsquerda) and j < len(listaDaDireita):
 if listaDaEsquerda[i] < listaDaDireita[j]:
 lista[k]=listaDaEsquerda[i]
 i += 1
 else:
 lista[k]=listaDaDireita[j]
 j += 1
 k += 1
 while i < len(listaDaEsquerda):
 lista[k]=listaDaEsquerda[i]
 i += 1
 k += 1
 while j < len(listaDaDireita): Código em Java[editar | editar código-fonte]
public static void shellSort(Integer[] nums) {
 int h = 1;
 int n = nums.length;
 
 while(h < n) {
 h = h * 3 + 1;
 }
 
 h = h / 3;
 int c, j;
 
 while (h > 0) {
 for (int i = h; i < n; i++) {
 c = nums[i];
 j = i;
 while (j >= h && nums[j - h] > c) {
 nums[j] = nums[j - h];
 j = j - h;
 }
 nums[j] = c;
 }
 h = h / 2;
 }
}
Código em Python[editar | editar código-fonte]
def shellSort(nums):
 h = 1
 n = len(nums)
 while h > 0:
 for i in range(h, n):
 c = nums[i]
 j = i
 while j >= h and c < nums[j - h]:
 nums[j] = nums[j - h]
 j = j - h
 nums[j] = c
 h = int(h / 2.2)
 return nums
Código em C++11[editar | editar código-fonte]
template <typename T>
void shell_sort(std::vector<T> &v) {
 int h = 1;
 int i, j;
 int rep = 0;
 while (h < v.size()) {
 h = h*3+1;
 }
 while (h > 1) {
 h /= 3;
 for (i = h; i < v.size(); i++) {
 T aux = v[i];
 j = i;
 while (j >= h && aux < v[j-h]) {
 v[j] = v[j-h];
 j -= h;
 rep++;
 }
 v[j] = aux;
 }
 }
}
Código em C[editar | editar código-fonte]
void shellSort(int *vet, int size) {
 int i , j , value;
 
 int gap = 1;
 while(gap < size) {
 gap = 3*gap+1;
 }
 while (gap > 0) {
 for(i = gap; i < size; i++) {
 value = vet[i];
 j = i;
 while (j > gap-1 && value <= vet[j - gap]) {
 vet[j] = vet [j - gap];
 j = j - gap;
 }
 vet [j] = value;
 }
 gap = gap/3;
 }
}
Código em PHP[editar | editar código-fonte]
function shellSort($arr_sort){
 $pet = 1;
 do {
 $pet = 3 * $pet + 1;
 } while ($pet < count($arr_sort));
 do {
 $pet /= 3;
 $pet = intval($pet);
 for ($i = $pet; $i < count($arr_sort); $i++) {
 $temp = $arr_sort[$i];
 $j = $i - $pet;
 while($j >=0 && $temp < $arr_sort[$j]) {
 $arr_sort[$j + $pet] = $arr_sort[$j];
 $j -= $pet;
 }
 $arr_sort[$j + $pet] = $temp;
 }
 } while ($pet > 1);
 return $arr_sort;
}
Código em Ruby[editar | editar código-fonte]
def shellSort(array)
 n = array.length
 h = n/2
 while h > 0
 for i in (h...n)
 c = array[i]
 j = i
 while j >= h && c < array[j-h]
 array[j] = array[j-h]
 j = j-h
 array[j] = c
 end
 end
 h = (h/2.2).to_i
 end
end
Código em Swift[editar | editar código-fonte]
 1 func shellSort<T:Comparable>(_ input:[T]) -> [T] {
 2 
 3 var items : [T] = input
 4 let itemsCount : Int = items.count
 5 var gapSize : Int = items.count
 6 let minGapSize : Int = 1
 7 let half : Int = 2
 8 var swaped : Bool = true
 9 
10 while !swaped || gapSize > minGapSize {
11 
12 swaped = false
13 gapSize = (gapSize + 1) / half
14 
15 for (index, _) in items.enumerated() where index < (itemsCount - gapSize) {
16 let indexToCompare = index + gapSize
17 if items[index] > items[indexToCompare] {
18 swap(&items[index], &items[indexToCompare])
19 swaped = true
20 }
21 }
22 }
23 
24 return items
25 }
Código em JavaScript[editar | editar código-fonte]
 1 public void shellSort(int[] array) {
 2 int[] gaps = { 701, 301, 132, 57, 23, 10, 4, 1 };
 3 int temp;
 4 int i, j;
 5 
 6 for (int gap : gaps) {
 7 for (i = gap; i < array.length; i++) {
 8 temp = array[ i ];
 9 for (j = i; j >= gap && array[ j - gap ] > temp; j -= gap) {
10 array[ j ] = array[ j - gap ];
11 }
12 array[ j ] = temp;
13 }
14 }
15 }
Exemplo de execução[editar | editar código-fonte]
Execução:
Dado o vetor de entrada: 12, 43, 1, 6, 56, 23, 52, 9
12, 43, 1, 6, 56, 23, 52, 9
12, 43, 1, 6, 56, 23, 52, 9
1, 43, 12, 6, 56, 23, 52, 9
1, 6, 12, 43, 56, 23, 52, 9
1, 6, 12, 43, 52, 23, 56, 9
1, 6, 12, 9, 52, 23, 56, 43
1, 6, 9, 12, 52, 23, 56, 43
1, 6, 9, 12, 23, 52, 56, 43
1, 6, 9, 12, 23, 52, 43, 56
1, 6, 9, 12, 23, 43, 52, 56
Em negrito estão os números trocados na atual iteração.
Após as seguintes trocas acima, obtemos o vetor ordenado: 1, 6, 9, 12, 23, 43, 52, 56.
Conclusão[editar | editar código-fonte]
A ordenação Shell utiliza a quebra sucessiva da sequência a ser ordenada e implementa a ordenação por inserção na sequência obtida. Devido a sua complexidade possui excelentes desempenhos em N muito grandes, inclusive sendo melhor que o Merge Sort.
O algoritmo heapsort é um algoritmo de ordenação generalista, e faz parte da família de algoritmos de ordenação por seleção. Foi desenvolvido em 1964 por Robert W. Floyd e J.W.J Williams.
 lista[k]=listaDaDireita[j]
 j += 1
 k += 1
Criado por Donald Shell em 1959,[1] publicado pela Universidadede Cincinnati, Shell sort é o mais eficiente algoritmo de classificação dentre os de complexidade quadrática. É um refinamento do método de inserção direta.[2] O algoritmo difere do método de inserção direta pelo fato de no lugar de considerar o array a ser ordenado como um único segmento, ele considera vários segmentos sendo aplicado o método de inserção direta em cada um deles.[3] Basicamente o algoritmo passa várias vezes pela lista dividindo o grupo maior em menores. Nos grupos menores é aplicado o método da ordenação por inserção. Implementações do algoritmo. Veja a versão em inglês desse mesmo link.
Definição[editar | editar código-fonte]
Tem um desempenho em tempo de execução muito bom em conjuntos ordenados aleatoriamente, tem um uso de memória bem comportado e o seu desempenho em pior cenário é praticamente igual ao desempenho em cenário médio. Alguns algoritmos de ordenação rápidos têm desempenhos espectacularmente ruins no pior cenário, quer em tempo de execução, quer no uso da memória. O heapsort trabalha no lugar e o tempo de execução em pior cenário para ordenar n elementos é de O (n lg n). Lê-se logaritmo (ou log) de "n" na base 2. Para valores de n, razoavelmente grandes, o termo log n é quase constante, de modo que o tempo de ordenação é quase linear com o número de itens a ordenar.
Características[editar | editar código-fonte]
	Comparações no pior caso: 2n log2n + O(n) é o mesmo que 2n lgn + O(n)
	Trocas no pior caso: n log2n + O(n) é o mesmo que n lgn + O(n)
	Melhor e pior caso: O(n log2n) é o mesmo que O(n lgn)
Estabilidade[editar | editar código-fonte]
O heapsort não é um algoritmo de ordenação estável. Porém, é possível adaptar a estrutura a ser ordenada de forma a tornar a ordenação estável. Cada elemento da estrutura adaptada deve ficar no formato de um par (elemento original, índice original). Assim, caso dois elementos sejam iguais, o desempate ocorrerá pelo índice na estrutura original.
Funcionamento[editar | editar código-fonte]
O heapsort utiliza uma estrutura de dados chamada heap, para ordenar os elementos à medida que os insere na estrutura. Assim, ao final das inserções, os elementos podem ser sucessivamente removidos da raiz da heap, na ordem desejada, lembrando-se sempre de manter a propriedade de max-heap.
A heap pode ser representada como uma árvore (uma árvore binária com propriedades especiais[2]) ou como um vetor. Para uma ordenação decrescente, deve ser construída uma heap mínima (o menor elemento fica na raiz). Para uma ordenação crescente, deve ser construído uma heap máxima (o maior elemento fica na raiz).
Implementação em C[editar | editar código-fonte]
void heapsort(int a[], int n) {
 int i = n / 2, pai, filho, t;
 while(true) {
 if (i > 0) {
 i--;
 t = a[i];
 } else {
 n--;
 if (n <= 0) return;
 t = a[n];
 a[n] = a[0];
 }
 pai = i;
 filho = i * 2 + 1;
 while (filho < n) {
 if ((filho + 1 < n) && (a[filho + 1] > a[filho]))
 filho++;
 if (a[filho] > t) {
 a[pai] = a[filho];
 pai = filho;
 filho = pai * 2 + 1;
 } else {
 break;
 }
 }
 a[pai] = t;
 }
}
2.4 Vantagens do método
O Radix sort é um algoritmo de ordenação rápido e estável que pode ser usado para ordenar itens que estão identificados por chaves únicas. Cada chave é uma cadeia de caracteres ou número, e o radix sort ordena estas chaves em qualquer ordem relacionada com a lexicografia.
Na ciência da computação, radix sort é um algoritmo de ordenação que ordena inteiros processando dígitos individuais. Como os inteiros podem representar strings compostas de caracteres (como nomes ou datas) e pontos flutuantes especialmente formatados, radix sort não é limitado somente a inteiros.
Funcionamento do algoritmo[editar | editar código-fonte]
Computadores, na sua maioria, representam internamente todos os tipo de dados como números binários, por isso processar os dígitos na forma de inteiros em grupos representados por dígitos binários se torna mais conveniente. Existem duas classificações do radix sort, que são:
	Least significant digit (LSD – Dígito menos significativo) radix sort;
	Most significant digit (MSD – Dígito mais significativo) radix sort.
O radix sort LSD começa do dígito menos significativo até o mais significativo, ordenando tipicamente da seguinte forma: chaves curtas vem antes de chaves longas, e chaves de mesmo tamanho são ordenadas lexicograficamente. Isso coincide com a ordem normal de representação dos inteiros, como a sequência "1, 2, 3, 4, 5, 6, 7, 8, 9, 10". Os valores processados pelo algoritmo de ordenação são frequentemente chamados de “chaves”, que podem existir por si próprias ou associadas a outros dados. As chaves podem ser strings de caracteres ou números.
Já o radix sort MSD trabalha no sentido contrário, usando sempre a ordem lexicográfica, que é adequada para ordenação de strings, como palavras, ou representações de inteiros com tamanho fixo. A seqüência "b, c, d, e, f, g, h, i, j, ba" será ordenada lexicograficamente como "b, ba, c, d, e, f, g, h, i, j". Se essa ordenação for usada para ordenar representações de inteiros com tamanho variável, então a representação dos números inteiros de 1 a 10 terá a saída "1, 10, 2, 3, 4, 5, 6, 7, 8, 9".
O radix sort LSD opera na notação Big-O, em {\displaystyle O(nk)}{\displaystyle O(nk)}, onde {\displaystyle n}n é o número de chaves, e {\displaystyle k}k é o comprimento médio da chave. É possível garantir esse desempenho para chaves com comprimento variável agrupando todas as chaves que tem o mesmo comprimento e ordenando separadamente cada grupo de chaves, do mais curto para o mais comprido, de modo a evitar o processamento de uma lista inteira de chaves em cada passo da ordenação.
Em muitas aplicações em que é necessário velocidade, o radix sort melhora as ordenações por comparação, como heapsort e o mergesort, que necessitam de {\displaystyle \Omega (n\log n)}{\displaystyle \Omega (n\log n)} comparações, onde {\displaystyle n}n é o número de itens a serem ordenados. Em compensação, algoritmos de ordenação baseados em comparações oferecem flexibilidade por serem aptos a ordenar de outras formas que não a lexicográfica. No entanto, essa habilidade é de pouca importância em várias aplicações práticas.
O algoritmo de ordenação radix sort foi originalmente usado para ordenar cartões perfurados. Um algoritmo computacional para o radix sort foi inventado em 1954 no MIT por Harold H. Seward.
Complexidade assintótica[editar | editar código-fonte]
A complexidade no tempo do algoritmo é {\displaystyle \Theta (nk)}{\displaystyle \Theta (nk)}e a complexidade no espaço: {\displaystyle \Theta (n+s)}{\displaystyle \Theta (n+s)}, onde
	{\displaystyle n}n = número de elementos.
	{\displaystyle k}k = tamanho string.
	{\displaystyle s}s = tamanho do alfabeto.
Implementações[editar | editar código-fonte]
Código em MATLAB[editar | editar código-fonte]
function vetor = radixsort(vetor, tamanho)
	%
	% Ordena vetor de inteiros, exemplo:
	%	tamanho = 10000;
	%	vetor = floor(10000*rand(tamanho,1));
	%	vetor = radixsort(vetor, tamanho);
	%
	ep = 1;
	maior = max(vetor);
	
	while floor(maior/ep) > 0
		V = sortrows([mod(floor(vetor/ep), 10), (1:tamanho)']);
		vetor = vetor(V(:,2));
		ep = ep*10;
	end
end
Código em C[editar | editar código-fonte]
void radixsort(int vetor[], int tamanho) {
 int i;
 int *b;
 int maior = vetor[0];
 int exp = 1;
 b = (int *)calloc(tamanho, sizeof(int));
 for (i = 0; i < tamanho; i++) {
 if (vetor[i] > maior)
 	 maior = vetor[i];
 }
 while (maior/exp > 0) {
 int bucket[10] = { 0 };
 	for (i = 0; i < tamanho; i++)
 	 bucket[(vetor[i] / exp) % 10]++;
 	for (i = 1; i < 10; i++)
 	 bucket[i] += bucket[i - 1];
 	for (i = tamanho - 1; i >= 0; i--)
 	 b[--bucket[(vetor[i] / exp) % 10]] = vetor[i];
 	for (i = 0; i < tamanho; i++)
 	 vetor[i] = b[i];
 	exp *= 10;
 }
 free(b);
}
Código em C#[editar | editar código-fonte]
 1 static void RadixSort(int[] vetor) {
 2 	int i;
 3 	int[] b;
 4 	int maior = vetor[0];
 5 	int exp = 1;
 6 
 7 	b = new int[vetor.Length];
 8 
 9 	for (i = 0; i < vetor.Length; i++) {
10 		if (vetor[i]> maior)
11 			maior = vetor[i];
12 	}
13 
14 	while (maior/exp > 0) {
15 		int[] bucket = new int[10];
16 		for (i = 0; i < vetor.Length; i++)
17 			bucket[(vetor[i] / exp) % 10]++;
18 		for (i = 1; i < 10; i++)
19 			bucket[i] += bucket[i - 1];
20 		for (i = vetor.Length - 1; i >= 0; i--)
21 			b[--bucket[(vetor[i] / exp) % 10]] = vetor[i];
22 		for (i = 0; i < vetor.Length; i++)
23 			vetor[i] = b[i];
24 		exp *= 10;
25 	}
26 }
Código em Java [1][editar | editar código-fonte]
import java.util.*;
public class TestRadix {
 private static final int MAX_CHARS = 28;
	
 private static void radixSort(String[] v) {
		Queue<String> queues[] = createQueues();
		for (int pos = maxSize(v) - 1; pos >= 0; pos--) {
			for (int i = 0; i < v.length; i++) {
				int q = queueNo(v[i], pos);
				queues[q].add(v[i]);
			}
			restore(queues, v);
		}
	}
	private static void restore(Queue<String>[] qs, String[] v) {
		int contv = 0;
		for (int q = 0; q < qs.length; q++)
			while (qs[q].size() > 0)
				v[contv++] = qs[q].remove();
	}
	private static Queue<String>[] createQueues() {
		LinkedList<String>[] result = new LinkedList[MAX_CHARS];
		for (int i = 0; i < MAX_CHARS; i++) {
			result[i] = new LinkedList<String>();
		}
		return result;
	}
	private static int queueNo(String string, int pos) {
		if (pos >= string.length()) {
			return 0;
		}
		char ch = string.charAt(pos);
		if ((ch >= 'A') && (ch <= 'Z')) {
			return (ch - 'A' + 1);
		}
		else if (ch >= 'a' && ch <= 'z') {
			return ch - 'a' + 1;
		}
		else {
			return 27;
		}
	}
	private static int maxSize(String[] v) {
		int maxValue = v[0].length();
		for (int i = 1; i < v.length; i++) {
			if (maxValue < v[i].length()) {
				maxValue = v[i].length();
			}
		}
		return maxValue;
	}
	public static void printStringArray(String[] arrToPrint) {
		for (int i = 0; i < arrToPrint.length; i++) {
			System.out.print(arrToPrint[i]+" ");
		}
		System.out.println();
	}
	
	/**
	 * @param args Array of strings (set of words) to be sorted (ordered) - Must be passed as parameters
	 */
	public static void main(String[] args) {
		System.out.print("Input: ");
		printStringArray(args);
		radixSort(args);
		System.out.print("\nOutput: ");
		printStringArray(args);
	}
}
Código em Java [2][editar | editar código-fonte]
	public void radixSort(int vector[]){
		for(int digit = 0; digit < 3; digit ++){
			int power = (int) Math.pow(10, digit+1);
			
			int z[][] = new int[vector.length][10];
			int n[] = new int[10];
			for(int i = 0; i < vector.length; i ++){
				int num = vector[i];
				z[n[(num%power)/(power/10)]][(num%power)/(power/10)] = num;
				n[(num%power)/(power/10)]++;
				
			}
			int c = 0;
			for(int i = 0; i < 10; i ++){
				
				for(int j = 0; j < vector.length; j ++){
					if(j < n[i]){
						vector[c] = z[j][i];
						c++;
					}else{break;}
				}
			}
			
		}
	}
Código em Python[editar | editar código-fonte]
MAX_CHARS = 28
def radix_sort(lista):
 tamanho_maximo = max([len(palavra) for palavra in lista])
 for pos in range(tamanho_maximo*1, 1, -1):
 baldes = [list() for y in range(MAX_CHARS)]
 for palavra in lista:
 balde = numero_do_balde(palavra, pos)
 baldes[balde] += [palavra]
 lista = sum(baldes, [])
 return lista
def numero_do_balde(palavra, pos):
 if (pos >= len(palavra)): return 0
 ch = palavra[pos]
 if (ch >= 'A' and ch <= 'Z'): return ord(ch) - ord('A') + 1
 if (ch >= 'a' and ch <= 'z'): return ord(ch) - ord('a') + 1
 return MAX_CHARS-1
Código em PHP[editar | editar código-fonte]
function radix_sort (&$a, $n)
{
 $r = 8;
 $R = 256;
 $p = 4;
 $count = null;
 for ($i = 0; $i < $p; ++$i)
 {
 for ($j = 0; $j < $R; ++$j)
 $count[$j] = 0;
 for ($k = 0; $k < $n; ++$k)
 {
 $pos = ($a[$k] >> (r * $i)) & ($R - 1);
 $count[pos] += 1;
 $tempArray[$k] = $a[$k];
 }
 $pos = 0;
 for ($j = 0; $j < $R; ++$j)
 {
 $tmp = $pos;
 $pos += $count[$j];
 $count[$j] = $tmp;
 }
 for ($k = 0; $k < $n; ++$k)
 {
 $pos = (tempArray[$k] >> ($r * $j)) & ($R - 2);
 $a[$count[$pos]] = $tempArray[$k];
 $count[$pos] += 1;
 }
 }
}
Algoritmo similiar ao Insertion sort com a diferença que o Gnome sort leva um elemento para sua posição correta, com uma seqüencia grande de trocas assim como o Bubble sort
O algoritmo percorre o vetor comparando seus elementos dois a dois, assim que ele encontra um elemento que está na posição incorreta, ou seja, um número maior antes de um menor, ele troca a posição dos elementos, e volta com este elemento até que encontre o seu respectivo lugar.
Características
Complexidade de tempo: Θ(n²)
Implementações[editar | editar código-fonte]
Código em Python[editar | editar código-fonte]
# coding: utf-8
def gnome(lista):
 pivot = 0
 lista_length = len(lista) 
 while pivot < lista_length - 1:
 if lista[pivot] > lista[pivot + 1]:
 lista[pivot + 1], lista[pivot] = lista[pivot], lista[pivot + 1]
 if pivot > 0:
 pivot -= 2
 pivot += 1
# Paulo Sérgio dos Santos Araujo
# Bacharelando em Ciência da Computação - Ufcg
Código em C[editar | editar código-fonte]
# include <stdio.h>
# include <stdlib.h>
# include <ctype.h>
# include <string.h>
# include <stdbool.h>
# define MAX 100001
int VectorSort[MAX];
int size = 0;
void swap(int * ,int *);
void GnomeSort();
int main (void){
 while(scanf("%d",&VectorSort[size]),VectorSort[size] >= 1)
 size++;
 GnomeSort();
 return 0;
}
void swap(int *A, int *B){
 int C = *A;
* A = *B;
* B = C;
}
void GnomeSort(){
 int next = 0, previous = 0;
 int i = 0;
 for(i = 0; i < size ; i++) {
 if(VectorSort[i] > VectorSort[i + 1]) {
 previous = i;
 next = i + 1;
 while(VectorSort[previous] > VectorSort[next]) {
 swap(&VectorSort[previous],&VectorSort[next]);
 if(previous > 0)
 previous--;
 if(next > 0) 
 next--;
 }
 }
 }
 for(i = 0; i < size; i++) printf("%d\n",VectorSort[i]);
}
Código em C++ versão 1[editar | editar código-fonte]
template<class T>
void gnome_sort( std::vector<T> &lista )
{
 std::vector<T>::size_type i = 1;
 while( i < lista.size() )
 {
 if( i == 0 || lista.at( i-1 ) <= lista.at( i ) )
 {
 i++;
 }
 else
 {
 std::swap( lista[ i - 1 ], lista [ i ] );
 --i;
 }
 }
}
Código em C++ versão 2[editar | editar código-fonte]
template<class T>
void gnome_sort( std::vector<T> &lista )
{
 std::vector<T>::iterator elem = lista.begin()+1;
 while( elem != lista.end() )
 {
 if( elem == lista.begin() || *(elem-1) <= *elem )
 {
 ++elem;
 }
 else
 {
 std::iter_swap( elem-1, elem );
 --elem;
 }
 }
}
Código em Java[editar | editar código-fonte]
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import java.util.Set;
/**
* Implementa e executa o algoritmo Gnome Sort
*
* @author Dielson Sales, Marcos Paulo J. Melo Silva
*/
public class GnomeSort<E extends Comparable<? super E>> {
 /**
* Ordena uma coleção de dados comparáveis usando o Gnome Sort.
* @param vector uma lista de dados comparáveis
* @return uma lista com os dados ordenados
*/
 public Collection<E> sort(Collection<E> vector) {
 int i = 1;
 List<E> result = new ArrayList<E>(vector);
 while (i < result.size()) {
 if (i == 0 || result.get(i - 1).compareTo(result.get(i))<= 0) {
 i++;
 } else {
 E temp = result.get(i - 1);
 result.set(i - 1, result.get(i));
 result.set(i, temp);
 i--;
 }
 }
 return result;
 }
 /**
* Execução do algoritmo de ordenação Gnome Sort.
*/
 public static void main(String[] args) {
 GnomeSort<Integer> gnomeSort = new GnomeSort<Integer>();
 final int size = 50;
 final Random random = new Random();
 List<Integer> list = new ArrayList<Integer>(size);
 for (int i = 0; i < size; i++) {
 list.add(random.nextInt());
 }
 // Lista com os dados já ordenados.
 Set<Integer> sortedList = new HashSet<Integer>(gnomeSort.sort(list));
 }
}
/**
* Exemplo de código em Java
* Autores: Marcos Paulo J. de Melo Silva e Dielson Sales de Carvalho;
* Instituição: Universidade Federal de Alagoas (UFAL);
*/
Código em Java[editar | editar código-fonte]
/*
* Autor: Felipe da Silva Travassos
* Graduando em Ciência da Computação - UFCG
*/
public static Integer[] gnomeSort(Integer[] array){
 int pivout =0;
 int aux;
 while(pivout<(array.length-1)){
 if(array[pivout]>array[pivout+1]){
 aux = array[pivout];
 array[pivout] = array[pivout+1];
 array[pivout+1] = aux;
 if(pivout>0){
 pivout-=2;
 }
 }
 pivout++;
 }
 return array;
}
Código em C#[editar | editar código-fonte]
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace gnome_sort
{
 class Program
 {
 static void Main(string[] args)
 {
 int men = 1;
 int[] vetor = new int[19];
 Random r = new Random(50);
 while (men != 0)
 {
 Menu();
 ImprimeVetor(vetor);
 Console.WriteLine();
 Console.WriteLine("Opcao:");
 men = int.Parse(Console.ReadLine());
 CaseMenu(men, vetor, r);
 Console.Clear();
 }
 }
 /* Case do Menu */
 private static void CaseMenu(int men, int[] vetor, Random r)
 {
 switch (men)
 {
 case 1: NovoVetor(vetor, r);
 break;
 case 2: GnomeSort(vetor);
 break;
 case 0: break;
 default: Console.WriteLine("INVALIDO! Digite 1 ou 2");
 break;
 }
 }
 /* Imprime o Vetor */
 private static void ImprimeVetor(int[] vetor)
 {
 foreach (var item in vetor)
 {
 Console.Write(item);
 Console.Write(" ");
 }
 }
 /* Gera os os números aleatórios no vetor */
 private static void NovoVetor(int[] vetor, Random r)
 {
 for (int i = 0; i < vetor.Length; i++)
 {
 vetor[i] = r.Next(1, 100);
 }
 }
 /* Menu do programa */
 static void Menu()
 {
 Console.WriteLine("***************** MENU *******************");
 Console.WriteLine(" ");
 Console.WriteLine("1 - Gerar um conjunto de números aleatório");
 Console.WriteLine("2 - Utilizar o algoritmo para a ordenação ");
 Console.WriteLine(" ");
 Console.WriteLine("0 - Sair ");
 Console.WriteLine("******************************************");
 }
 /* Algoritmo de Ordenação */
 static void GnomeSort( int[] array )
 {
 for ( int i = 1, temp_value; i < array.Length; )
 {
 if ( array[i-1] <= array[i] )
 i += 1;
 else
 {
 temp_value = array[i-1];
 array[i-1] = array[i];
 array[i] = temp_value;
 i -= 1;
 if ( i == 0 )
 i = 1;
 }
 Console.Clear();
 Console.WriteLine("Ordenando...");
 ImprimeVetor(array);
 System.Threading.Thread.Sleep(10);
 }
 }
 }
}
Código de um programa em C#. Gera números aleatórios e ordena com o Gnome Sort
Autor: Marcos Latchuk
Universidade: UNICENTRO Guarapuava - Pr
Counting sort é um algoritmo de ordenação estável cuja complexidade é O(n). As chaves podem tomar valores entre 0 e M-1. Se existirem k0 chaves com valor 0, então ocupam as primeiras k0 posições do vetor final: de 0 a k0-1.
A ideia básica do counting sort é determinar, para cada entrada x, o número de elementos menor que x. Essa informação pode ser usada para colocar o elemento x diretamente em sua posição no array de saída. Por exemplo, se há 17 elementos menor que x, então x pertence a posição 18. Esse esquema deve ser ligeiramente modificado quando houver vários elementos com o mesmo valor, uma vez que nós não queremos colocar eles na mesma posição.[1]
Pseudocódigo[editar | editar código-fonte]
//k é o maior valor do vetor A
//Criar vetor auxiliar com k+1 elementos e inicializar com zeros
for i ← 0 to k
 do C[i]←0
 
for j ← 1 to length[A]
 do C[A[j]] ← C[A[j]] + 1
//Agora C[i] contem o numero de elementos igual a i.
for i ← 1 to k
 do C[i] ← C[i] + C[i - 1]
//Agora C[i] contem o numero de elementos menor que ou igual a i.
for j ← length[A] downto 1
 do B[C[A[j]]] ← A[j]
 C[A[j]] ← C[A[j]] - 1
 
//Pseudocodigo do livro "Introduction to Algorithms" 
//de Thomas H. Cormen...[et al.] - 2nd ed.
//The MIT Press (p. 168)
Implementações[editar | editar código-fonte]
	Cria cnt[M+1] e b[max N]
	Inicializa todas as posições de cnt a 0.
	Percorre o vector a e, para cada posição i de a faz cnt[a[i]-1]++ o que faz com que, no final, cada posição i de cnt contem o nº de vezes que a chave i-1 aparece em a.
	Acumula em cada elemento de cnt o elemento somado ao elemento anterior: cnt[i] indica a posição ordenada do primeiro elemento de chave i.
	Guarda em b os valores de a ordenados de acordo com b[cnt[a[i]++]=a[i]
	Copia b para a.
	Counting-Sort trabalha como uma contadora de ocorrências dentro de um programa, especificamente dentro de um vetor. Quando determinado vetor tem números repetidos, números únicos e números que não existem um outro vetor indica a quantidade de ocorrências.
Esta implementação tem a desvantagem de precisar de vectores auxiliares. O Counting Sort ordena exclusivamente números inteiros pelo fato de seus valores servirem como índices no vetor de contagem.
Características
	Estável
	Necessita de memória auxiliar. Logo, não é in-place
	Complexidade linear
Código em C++[editar | editar código-fonte]
template<class T>
std::vector<T> counting_sort( const std::vector<T> &op )
{
 if ( op.empty() )
 return std::vector<T> {};
 auto min = *std::min_element( op.begin(), op.end() );
 auto max = *std::max_element( op.begin(), op.end() );
 std::vector<int> contagem( max - min + 1, 0 );
 for ( auto it = op.begin(); it != op.end(); ++it )
 ++contagem[ *it - min ];
 std::partial_sum( contagem.begin(), contagem.end(), contagem.begin() );
 std::vector<T> ordenado( op.size() );
 for ( auto it2 = op.rbegin(); it2 != op.rend(); ++it2 )
 ordenado[ --contagem[ *it2 - min ] ] = *it2;
 return ordenado;
}
Código em C[editar | editar código-fonte]
# include <stdio.h>
# include <string.h>
# include <stdlib.h>
# include <ctype.h>
# define MAX 100001
struct data
{
 int number;
 char key[100];
} DataBase[MAX], VectorSort[MAX];
int CounterNum[MAX];
int size = 0;
int main (void)
{
 int i = 0;
 while (scanf("%d%s", &DataBase[size].number, DataBase[size].key) >= 1)
 size++;
 int aux[2] = {0, 0};
 for (i = 0; i <= size; i++)
 aux[DataBase[i].number]++;
 aux[1] += aux[0];
 for (i = size - 1; i >= 0; i--)
 VectorSort[--aux[DataBase[i].number]] = DataBase[i];
 for (i = 0; i < size; i++)
 printf("Number: %d --- Key: %s\n", VectorSort[i].number, VectorSort[i].key);
 return 0;
}
Código em Java 1.0[editar | editar código-fonte]
 1 public Integer[] CountingSort(Integer[] v) {
 2 	
 3 //encontra o maior valor em v[]	
 4 	int maior = v[0];
 5 	for (int i = 1; i < v.length; i++) {
 6 		if (v[i] > maior) {
 7 			maior = v[i];
 8 		}
 9 	}
10 		
11 //conta quantas vezes cada valor de v[] aparece
12 	int[] c = new int[maior+1];//+1 pois se 10 for o maior valor, ele iria apenas de 0 a 9
13 	for (int i = 0; i < v.length; i++) {
14 		c[v[i]] += 1;
15 	}
16 		
17 //acumula as vezes de cada elemento de v[] com os elementos anteriores a este
18 	for (int i = 1; i < c.length; i++) {
19 		c[i] += c[i-1];
20 	}
21 		
22 //adiciona os elementos em suas posições conforme o acumulo de suas frequencias
23 	Integer[] b = new Integer[v.length];
24 	for (int i = b.length-1; i >= 0; i--) {//percorre do fim para o inicio para manter estavel, mas não haveria problema em i = 0; i < b.lenght; i++
25 		b[c[v[i]] -1] = v[i];
26 		c[v[i]]--;
27 	}
28 	
29 	return b;
30 }
Código em Java 1.1[editar | editar código-fonte]
public void CountingSort(Integer[] array, int leftIndex, int rightIndex) {
		
		//Encontrar o maior valor 
		int k = 0;
		for(int m = leftIndex; m < rightIndex; m++){
			if(array[m] > k){
				k = array[m];
			}
		}
		
		//Cria vetor com o tamanho do maior elemento
		int[] vetorTemporario = new int[k];
		
		//Inicializar com zero o vetor temporario
		for(int i = 0; i < vetorTemporario.length; i++){
			vetorTemporario[i] = 0;
		}
		
		//Contagem das ocorrencias no vetor desordenado
		for(int j = leftIndex; j < rightIndex; j++){
			vetorTemporario[array[j]] += 1;
		}
		
		//Fazendo o complemento do numero anterior 
		for(int i = leftIndex; i < k; i++){
			vetorTemporario[i] = vetorTemporario[i] + vetorTemporario[i - 1];
		}
		
		//Ordenando o array da direita para a esquerda
		int[] vetorAuxiliar = new int[array.length];
		for(int j = rightIndex; j > leftIndex; j--) {
			vetorAuxiliar[vetorTemporario[array[j]]] = array[j];
			vetorTemporario[array[j]] -= 1; 
		}
		
		//Retornando os valores ordenados para o vetor de entrada
		for (int i = leftIndex; i < rightIndex; i++){
			array[i] = vetorAuxiliar[i];
		}
	}
Bucket sort,ou bin sort, é um algoritmo de ordenação que funciona dividindo um vetor em um número finito de recipientes. Cada recipiente é então ordenado individualmente, seja usando um algoritmo de ordenação diferente, ou usando o algoritmo bucket sort recursivamente. O Bucket Sort tem complexidade linear {\displaystyle \Theta (n)}{\displaystyle \Theta (n)} quando o vetor a ser ordenado contém valores que são uniformemente distribuídos[1]. Funcionamento[editar | editar código-fonte]
Bucket sort funciona do seguinte modo:
	Inicialize um vetor de "baldes", inicialmente vazios.
	Vá para o vetor original, incluindo cada elemento em um balde.
	Ordene todos os baldes não vazios.
	Coloque os elementos dos baldes que não estão vazios no vetor original.
Exemplo em C[editar | editar código-fonte]
//Compilado em Linux.Sujeito a mudanças caso outro sistema seja utilizado.
 
 #include <stdio.h>
 
 #define tam_bucket 100
 #define num_bucket 10
 #define max 10
 
 typedef struct {
 int topo;
 int balde[tam_bucket];
 }bucket;
 
 void bucket_sort(int v[],int tam); //cabeçalho das funções
 void bubble(int v[],int tam); 
 
 void bucket_sort(int v[],int tam){ 
 bucket b[num_bucket]; 
 int i,j,k; 
 /* 1 */ for(i=0;i<num_bucket;i++) //inicializa todos os "topo"
 b[i].topo=0;
 
 /* 2 */ for(i=0;i<tam;i++){ //verifica em que balde o elemento deve ficar
 j=(num_bucket)-1;
 while(1){
 if(j<0)
 break;
 if(v[i]>=j*10){
 b[j].balde[b[j].topo]=v[i];
 (b[j].topo)++;
 break;
 }
 j--;
 }
 }
 
 /* 3 */ for(i=0;i<num_bucket;i++) //ordena os baldes
 if(b[i].topo)
 bubble(b[i].balde,b[i].topo);
 
 i=0;
 /* 4 */ for(j=0;j<num_bucket;j++){ //põe os elementos dos baldes de volta no vetor
 for(k=0;k<b[j].topo;k++){
 v[i]=b[j].balde[k];
 i++;
 }
 }
 }
 
 void bubble(int v[],int tam){
 int i,j,temp,flag;
 if(tam)
 for(j=0;j<tam-1;j++){
 flag=0;
 for(i=0;i<tam-1;i++){
 if(v[i+1]<v[i]){
 temp=v[i];
 v[i]=v[i+1];
 v[i+1]=temp;
 flag=1;
 }
 }
 if(!flag)
 break;
 }
 }
Explicação do código[editar | editar código-fonte]
https://upload.wikimedia.org/wikipedia/commons/thumb/6/61/Bucket_sort_1.png/250px-Bucket_sort_1.png
Bucket sort - fase 1.
https://upload.wikimedia.org/wikipedia/commons/thumb/3/39/Bucket_sort_2.png/250px-Bucket_sort_2.png
Bucket sort - fase 2.
Antes de mais nada, é preciso saber o que cada #define significa.
	tam_bucket é o tamanho de cada balde da estrutura bucket;
	num_bucket é o número de baldes, isto é, o tamanho do vetor de bucket;
	max é o tamanho do vetor a ser ordenado.
A estrutura bucket consiste de um vetor de inteiros (int balde[tam_bucket]) e de uma variável que serve para dizer quantos números estão armazenados no balde.
O parâmetro tam, tanto na função bucket_sort como na bubble, é o tamanho do vetor a ser ordenado.
A explicação dos for agora:
	Inicializa o topo de cada bucket que o vetor de bucket b[num_bucket] contém;
Isso é importante, pois, a princípio, os baldes estão vazios;
	Verifica em que balde o elemento deve ficar;
Cada elemento do vetor a ser ordenado é colocado em seu lugar no vetor de bucket. Por exemplo, suponha o número 26. A variável j receberia num_bucket-1, isto é, 9 no exemplo acima. O while verifica se 26 é maior do que j*10 (90). Como isto não é válido, j é decrementado em 1, e o processo se repete até que j=2, já que 26>=20. Então, o balde de posição 2 recebe 26. Caso não haja nenhum outro elemento no balde 2, isso significa que topo daquele balde vale 0, portanto balde[0] recebe o 26. Caso haja, por exemplo, 3 elementos no balde, isso quer dizer que topo=2, portanto balde[2] recebe 26. Depois disso, topo daquele balde é incrementado em 1 e o processo se repete para os outros elementos do vetor que queremos ordenar;
	Ordena cada balde;
Ordena os baldes cujos topos sejam diferentes de 0, ou seja, não estão vazios. No algoritmo acima, o bubble sort foi utilizado, mas métodos mais eficientes podem ser utilizados;
	Por fim, os baldes são percorridos e seus elementos são devolvidos para o vetor original.
Atente-se para o fato de que o exemplo não ordena elementos negativos. Um tratamento especial para eles seria necessário. Além do mais, o método de separar cada elemento pode ser diferente. O utilizado foi verificar se o elemento está entre 0 e 10, 11 e 20, e assim por diante.
Exemplo em C++ com matriz[editar | editar código-fonte]
Aqui uma matriz linear de inteiros com n elementos, é usado para ordenar os elementos do vetor.
/*************************INICIO*****************************************/
//==================================================================
//
// Projeto: Bucket Sort
// Data de Criacao: 27/02/09
// Autor: Albany Timbo Mesquita
// Colaboracao:Pedro Henrique Fernandes Marques Leitao 
//
//==================================================================
#include <iostream>
#define TAM 20 /*Tamanho do vetor*/
#define NUM 10000 /*base para gerador de numeros aleatorios*/
using std::cout;
using std::cin;
using std::endl;
void gerarVet(int*);
void bucketSort(int*);
void imprimaVet(int*);
int main(){
 int vet[TAM],tinicio,tfim,tempo;
 
 tinicio=time(NULL);
 
 gerarVet(vet);
 imprimaVet(vet);
 bucketSort(vet); 
 imprimaVet(vet);
 
 tfim=time(NULL);
 tempo=difftime(tfim,tinicio);
 cout<<"Tempo de execucao "<<tempo/60<<" Minutos e "<<tempo%60<<" segundos.\n";
 system("pause");
 return 0;
 
 }
/***********************************************************************/
/*******************************FUNCOES*********************************/
/***********************************************************************/
void bucketSort(int *vet){
 int mat[10][TAM],aux[TAM],cont=1,num,w=0,i,j; 
 
 do{
 for(i=0;i<TAM;i++){aux[i] = 0;}//Zerando o vetor auxiliar.
 for(i=0;i<10;i++) {//Setando a Matriz com valores -1
	 for(j=0;j<TAM;j++){
 mat[i][j] = -1;
 }
 }
 for (i=0;i<TAM;i++) {
 	 num = (vet[i]/cont)%10;//verificando o valor da esquerda para direita
 	 mat[num][aux[num]] = vet[i];//colocando o valor na sua posicao na matriz
 	 aux[num]++; //contador de colunas da matriz
 }
 
 for(i=0;i<10;i++) {//volta com os valores da Matriz para o vetor
 	 for(j=0;j<TAM;j++){
 	 if(mat[i][j] != -1){
 	 vet[w] = mat[i][j];
 	 w++;
 	 }
 }
 }
 w = 0; 
 cont=cont*10;
 }while(aux[0] < TAM);//condicao :Enquanto vetor auxiliar < tamanho vetor
} // 
/******************GERADOR DE NUMEROS ALEATORIOS**************************/
void gerarVet(int *vet){
 
 srand(time(NULL));
 for (int i=0;i<TAM;i++){
 vet[i]=rand()%NUM;
 }
 }
/*******************FUNCAO PARA IMPRIMIR VETOR************************/
void imprimaVet(int *vet){
 for (int i=0;i<TAM;i++){
 cout<<vet[i]<<"|";
 }
 cout<<"**************************************************************\n"; 
 }
/********************************FIM*************************************/
Exemplo em Java com LinkedList[editar | editar código-fonte]
/*
* Autor: wilhs
* Data: 28/04/2011
* Crédito: Implementação com base neste Artigo.
*/
public static void BucketSort(int[] vetor, int maiorValor)
{
	int numBaldes = maiorValor/5;
	LinkedList[] B = new LinkedList[numBaldes];
	for (int i = 0; i < numBaldes; i++){
		B[i] = new LinkedList<Integer>();
	}
	//Coloca os valores no balde respectivo:
	for (int i = 0; i < vetor.length; i++) {
		int j = numBaldes-1;
		while (true){
			if(j<0){
				 break;
			}
			if(vetor[i] >= (j*5)){
				 B[j].add(vetor[i]);
				 break;
			}
			j--;
		}
	}
	//Ordena e atualiza o vetor:
	int indice = 0;
	for (int i = 0; i < numBaldes; i++){
		int[] aux = new int[B[i].size()];
		//Coloca cada balde num vetor:
		for (int j = 0; j < aux.length; j++){
				aux[j] = (Integer)B[i].get(j);
		}
		insertionSort(aux); //algoritmo escolhido para ordenação.
		// Devolve os valores ao vetor de entrada:
		for (int j = 0; j < aux.length; j++, indice++){
			vetor[indice] = aux[j];
		}
	}
}
Cocktail shaker sort,[1] também conhecido como bubble sort bidirecional,[2] cocktail sort, shaker sort (o qual também pode se referir a uma variação do insertion sort), ripple sort, shuffle sort,[3] ou shuttle sort, é uma variante do bubble sort, que é umalgoritmo com não-estável e efetua Ordenação por comparação. O algoritmo difere de um bubble sort no qual ordena em ambas as direções a cada iteração sobre a lista. Esse algoritmo de ordenação é levemente mais difícil de implementar que o bubble sort, e e resolve o problema com os chamados coelhos e tartarugas no bubble sort. Ele possui performance levemente superior ao bubble sort, mas não melhora a performance assintótica; assim como o bubble sort, não é muito usado na prática (insertion sort é escolhido para ordenação simples), embora seja usado para fins didáticos.
Complexidade[editar | editar código-fonte]
A complexidade do Cocktail shaker sort em notação big-O é {\displaystyle O(n^{2})}O(n^{2}) para o pior caso e caso médio, mas tende a se aproximar de {\displaystyle O(n)}O(n) se a lista se encontra parcialmente ordenada antes da execução do algoritmo. Por exemplo, se cada elemento se encontra em uma posição cuja distância até sua posição ordenada é k (k ≥ 1), a complexidade do algoritmo se torna {\displaystyle O(kn)}{\displaystyle O(kn)}.
{\displaystyle 1+1+1+1+n(1+n(1(1+1+1+1))+1+n(1(1+1+1+1))+1)}1+1+1+1+n(1+n(1(1+1+1+1))+1+n(1(1+1+1+1))+1)
{\displaystyle 4+n(3+4n+4n)}4+n(3+4n+4n)
{\displaystyle 4+n(3+8n)}4+n(3+8n)
{\displaystyle n(n)}n(n)
O(n²)
Implementações[editar | editar código-fonte]
Código em C[editar | editar código-fonte]
 void cocktail_sort(int list[10]) {
 int length,bottom,top, swapped,i,aux;
 length=10;
 bottom = 0;
 top = length - 1;
 swapped = 0; 
 while(swapped == 0 && bottom < top)//Se não houver troca de posições ou o ponteiro que
 { //sobe ultrapassar o que desce, o vetor esta ordenado
 swapped = 1; 
 //Este for é a “ida” para a direita
 for(i = bottom; i < top; i = i + 1)
 {
 if(list[i] > list[i + 1]) //indo pra direita:testa se o próximo é maior
 { //indo pra direita:se o proximo é maior que o atual,
 //troca as posições
 aux=list[i];
 list[i]=list[i+1];
 list[i+1]=aux;
 swapped = 0;
 }
 }//fecha for
 // diminui o `top` porque o elemento com o maior valor 
 // já está na direita (atual posição top)
 top = top - 1; 
 //Este for é a “ida” para a esquerda
 for(i = top; i > bottom; i = i - 1)
 { if(list[i] < list[i - 1]) 
 {
 aux=list[i];
 list[i]=list[i-1];
 list[i-1]=aux;
 swapped = 0;
 }
 }
 //aumenta o `bottom` porque o menor valor já está
 //na posição inicial (bottom) 
 bottom = bottom + 1; 
 }//fecha while 
 }// fim da funçao
Código em C# e Java (sintaxe idêntica)[editar | editar código-fonte]
 
private static void cocktail(int[] vetor)
{
 int tamanho, inicio, fim, swap, aux;
 tamanho = 10; // para um vetor de 20 elementos
 inicio = 0;
 fim = tamanho - 1;
 swap = 0;
 while (swap == 0 && inicio < fim)
 {
 swap = 1;
 for (int i = inicio; i < fim; i = i + 1)
 {
 if (vetor[i] > vetor[i + 1])
 {
 aux = vetor[i];
 vetor[i] = vetor[i + 1];
 vetor[i + 1] = aux;
 swap = 0;
 }
 }
 fim = fim - 1;
 for (int i = fim; i > inicio; i = i - 1)
 {
 if (vetor[i] < vetor[i - 1])
 {
 aux = vetor[i];
 vetor[i] = vetor[i - 1];
 vetor[i - 1] = aux;
 swap = 0;
 }
 }
 inicio = inicio + 1;
 }
}
Código em Pascal[editar | editar código-fonte]
 
procedure ShakerSort(var A:vetor; n:integer);
var L,R,k,i:integer;
begin
 L:=2;
 R:=n;
 k:=2;
 repeat
 for i:=L to R do
 begin
 if A[i-1]>A[i] then
 begin
 aux := A[i-1];
 A[i-1] := A[i];
 A[i]:= aux; 
 k:=i;
 end;
 end;
 R:=k-1;
 for i:=R downto L do
 begin
 if A[i-1]>A[i] then
 begin
 aux := A[i-1];
 A[i-1] := A[i];
 A[i]:= aux; 
 k:=i;
 end;
 end;
 L:=k+1;
 until L>R;
end;
Código em Ruby[editar | editar código-fonte]
def sort(array)
	swap = true
	begining = 0
	ending = array.length-1
	while(swap)
		swap = false
		begining.upto ending-1 do |i|
			if(array[i] > array[i+1])
				aux = array[i]
				array[i] = array[i+1]
				array[i+1] = aux
				swap = true
			end
		end
		ending -= 1
		ending.downto begining+1 do |i|
			if(array[i] < array[i-1])
				aux = array[i]
				array[i] = array[i-1]
				array[i-1] = aux
				swap = true
			end
		end
		begining += 1
	end
	return array
end
Código em Python[editar | editar código-fonte]
#coding: utf-8
def cocktailSort(lista):
	
	nova_lista = []
	for j in range(len(lista)):
		for i in range(len(lista)-1):
			if lista[len(lista)-1 - i] < lista[len(lista)-2 - i]:
				lista[len(lista)-1-i],lista[len(lista)-2-i] = lista[len(lista)-2-i],lista[len(lista)-1-i]
			if lista[i] > lista[i+1]:
				lista[i],lista[i+1] = lista[i+1],lista[i]
	return lista
		
print cocktailSort([3, 4, 2, 0, 5, 6, 7,1])
Bibliografia
https://www.cin.ufpe.br/~garme/public/(ebook)Estruturas%20de%20Dados%20Usando%20C%20(Tenenbaum).pdf
http://www.mlaureano.org/livro/livro_estrutura_conta.pdf
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.[1]
Tim Peters descreve o algoritmo da seguinte forma[2]:
[...]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 {\displaystyle \Theta (n\log n)}{\displaystyle \Theta (n\log n)}.[3]
De acordo com a teoria da Informação, nenhuma ordenação por comparação pode executar em menos de {\displaystyle \log _{2}(n!)}{\displaystyle \log _{2}(n!)}, no caso médio, o que exige que a ordenação por comparação tome um tempo de {\displaystyle \Omega (n\log n)}{\displaystyle \Omega (n\log n)} em dados aleatórios. No entanto, em dados do mundo real, o Timsort muitas vezes exige muito menos do que {\displaystyle \log _{2}(n!)}{\displaystyle \log _{2}(n!)}, porque ele tira vantagem do fato de que sublistas dos dados podem já estar em ordem ou ordem inversa.[4]
Introdução[editar | editar código-fonte]
TimSort [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 existentesna 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[editar | editar código-fonte]
O mecanismo do algoritmo pode ser explicado brevemente da seguinte maneira:
	Um algoritmo específico é usado para dividir o vetor de entrada em sub-vetores.
	Cada sub-vetor é ordenado usando um simples InsertionSort estável.
	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:
	N: Comprimento do vetor de entrada.
	Run: Um sub-vetor ordenado que compõe o vetor de entrada.
	Minrun: É o comprimento mínimo dos Runs. Este número é calculado baseado no tamanho do vetor de entrada (N).
Calculando os Minruns[editar | editar código-fonte]
O valor de Minrun é determinado com base no valor de N, seguindo os seguintes princípios:
	Não deve ser muito longo, pois o Minrun será posteriormente submetido ao InsertionSort, que é efetivo para tamanhos menores de vetores (Runs).
	Não deve ser muito curto, pois quanto mais curto for o Run, mais Runs terão que ser mescladas no próximo passo.
	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[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.
 1 int minRunLength (int n){
 2 assert n >= 0;
 3 int r = 0; // Becomes 1 if any 1 bits are
 4 shifted off
 5 while (n >= MIN_MERGE ) {
 6 r |= (n & 1);
 7 n > >= 1;
 8 }
 9 return n + r;
10 }
O valor MIN_MERGE pode ser definido como 64 seguindo a recomendação do autor.
Gerando e ordenando os Runs[editar | editar código-fonte]
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 é:
	O endereço base do elemento atual é definido para a posição inicial do vetor de entrada.
	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).
	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.
	Então o Run atual é ordenado via InsertionSort. Como este Run é pequeno e parcialmente ordenado, a ordenação é rápida.
	O endereço base do elemento atual é atualizado para o elemento seguinte ao último elemento pertencente ao Run que acabou de ser calculado.
	Se o fim do vetor não foi alcançado, executa-se esse algoritmo novamente do ponto 2 até o ponto 6.
https://upload.wikimedia.org/wikipedia/commons/thumb/6/63/Selection_of_minrun_by_timsort.png/220px-Selection_of_minrun_by_timsort.png
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[editar | editar código-fonte]
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:
	Runs de tamanho relativamente iguais devem ser combinados, para que ganhe-se em eficiência.
	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:
	Cria-se uma pair stack <Posição do primeiro elemento do Run>-<Tamanho do Run>.
	Insere-se o Run atual à pair stack.
	Avalia se deve ser feito o merge.
	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.
	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[editar | editar código-fonte]
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:
	Um vetor temporário é criado com o tamanho do menor dos dois Runs que são combinados.
	Copia-se o Run mais curto para o vetor temporário.
	Marca-se a posição corrente com os primeiros elementos do maior Run e do "Run" temporário.
	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.
	Repete o passo 4 até um dos Runs esvaziar.
	Adiciona todos os elementos do Run remanescente para o final do Run ordenado.
https://upload.wikimedia.org/wikipedia/commons/thumb/4/49/One-one_merging_timsort.svg/220px-One-one_merging_timsort.svg.png
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:
	Inicia-se o MergeSort como descrito nos passos anteriores.
	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.
	Se uma quantidade X de elementos foi movida de um mesmo Run para o vetor ordenado supõe-se que o próximo elementotambé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 ({\displaystyle 2^{i}}{\displaystyle 2^{i}}, com {\displaystyle i}i começando em {\displaystyle 0}{\displaystyle 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 {\displaystyle 2^{i}}{\displaystyle 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.
	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 {\displaystyle 2^{n-1}+1}{\displaystyle 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.
https://upload.wikimedia.org/wikipedia/commons/thumb/6/6e/Galloping_mode_in_timsort.svg/220px-Galloping_mode_in_timsort.svg.png
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[editar | editar código-fonte]
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 é {\displaystyle O(nlogn)}{\displaystyle O(nlogn)}.
Considerações do autor:
	O merge considera o Run como sendo um único elemento, e neste caso o custo de decomposição de cada Run será constante.
	O custo de dois Runs é definido como {\displaystyle c(R,R0)-1}{\displaystyle c(R,R0)-1}, onde {\displaystyle c(R,R0)=|R|+|R0|}{\displaystyle c(R,R0)=|R|+|R0|}.
	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.
	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 {\displaystyle W,X,Y,\mathrm {Z} }{\displaystyle W,X,Y,\mathrm {Z} } são os 4 elementos que estão no topo da pilha:
{\displaystyle \rho 1:=|X|\geq |\mathrm {Z} |\longrightarrow merge(X,Y)}{\displaystyle \rho 1:=|X|\geq |\mathrm {Z} |\longrightarrow merge(X,Y)}
{\displaystyle \rho 2:=|X|>|Y|+|\mathrm {Z} |\longrightarrow merge(Y,Z)}{\displaystyle \rho 2:=|X|>|Y|+|\mathrm {Z} |\longrightarrow merge(Y,Z)}
{\displaystyle \rho 3:=|W|>|X|+|Y|\longrightarrow merge(Y,Z)}{\displaystyle \rho 3:=|W|>|X|+|Y|\longrightarrow merge(Y,Z)}
{\displaystyle \rho 4:=|Y|>|\mathrm {Z} |\longrightarrow merge(Y,Z)}{\displaystyle \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}|}{\textstyle C\geq \sum _{i=1}^{l}3i|x_{i}|}
onde, {\displaystyle C}C é o custo da relação, {\displaystyle l}l é o tamanho da pilha e {\displaystyle |x_{i}|}{\displaystyle |x_{i}|} é o tamanho do i-ésimo Run na pilha. O autor conclui que o custo dessa equação {\displaystyle O(nlogn)}{\displaystyle O(nlogn)}, seguindo o seguinte raciocínio:
	A soma do tamanho dos Runs terá um custo aproximado a {\displaystyle n}n.
	A distribuição dos Runs na pilha, tendem a formar uma sequência crescente, onde sempre o elemento na posição {\displaystyle i}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 {\displaystyle l}l será limitado superiormente por {\displaystyle log(n)}{\displaystyle log(n)}.
Como o conteúdo do somatório é uma multiplicação dessas duas relações, o custo inferido é {\displaystyle O(nlogn)}{\displaystyle O(nlogn)}.
Agora, a estratégia que o autor usa para provar que o custo de comparações do TimSort também é {\displaystyle O(nlogn)}{\displaystyle O(nlogn)}, é subtrair {\displaystyle c(R,R0)}{\displaystyle c(R,R0)} de {\displaystyle C}C para todos os merges que são feitos, e caso no final do algoritmo o valor de {\displaystyle C}C seja maior que {\displaystyle 0}{\displaystyle 0}, então o custo de comparações também é limitado superiormente por {\displaystyle nlogn}{\displaystyle nlogn}. O que após provar para todas as regras de merge, constata-se que é verdade.
O algoritmo quicksort é um método de ordenação muito rápido e eficiente, inventado por C.A.R. Hoare em 1960[1], quando visitou a Universidade de Moscovo como estudante. Naquela época, Hoare trabalhou em um projeto de tradução de máquina para o National Physical Laboratory. Ele criou o quicksort ao tentar traduzir um dicionário de inglês para russo, ordenando as palavras, tendo como objetivo reduzir o problema original em subproblemas que possam ser resolvidos mais fácil e rápido. Foi publicado em 1962 após uma série de refinamentos.[2]
O quicksort é um algoritmo de ordenação por comparação não-estável.
O algoritmo computacional[editar | editar código-fonte]
https://upload.wikimedia.org/wikipedia/commons/thumb/4/4a/Quicksort_example_small.png/220px-Quicksort_example_small.png
Algumas etapas do algoritmo quicksort.
O quicksort adota a estratégia de divisão e conquista. A estratégia consiste em rearranjar as chaves de modo que as chaves "menores" precedam as chaves "maiores". Em seguida o quicksort ordena as duas sublistas de chaves menores e maiores recursivamente até que a lista completa se encontre ordenada. [3]Os passos são:
	Escolha um elemento da lista, denominado pivô;
	Particiona: rearranje a lista de forma que todos os elementos anteriores ao pivô sejam menores que ele, e todos os elementos posteriores ao pivô sejam maiores que ele. Ao fim do processo o pivô estará em sua posição final e haverá duas sub listas não ordenadas. Essa operação é denominada partição;
	Recursivamente ordene a sub lista dos elementos menores e a sub lista dos elementos maiores;
O caso base da recursão são as listas de tamanho zero ou um, que estão sempre ordenadas. O processo é finito, pois a cada iteração pelo menos um elemento é posto em sua posição final e não será mais manipulado na iteração seguinte.
A escolha do pivô e os passos do Particiona podem ser feitos de diferentes formas e a escolha de uma implementação específica afeta fortemente a performance do algoritmo.
Método de partição de Lomuto[editar | editar código-fonte]
Método atribuído a Nico Lomuto e popularizado por Bentley em seu livro Programming Pearls[4] e por Cormen et al. no livro Introduction to Algorithms. Este método escolhe um pivô tipicamente no início ou no final do array. O Particiona recebe como parâmetro dois índices do array, lo e hi, que será a parte do array a ser particionada, então escolhe-se um índice i e percorre-se o array usando outro índice j realizando trocas, quando necessário, a fim de que todos os elementos menores ou iguais ao pivô fiquem antes do índice i e os elementos i + 1 até hi, ou j - 1, sejam maiores que o pivô . Esta é a maneira mais simples e fácil de entender, geralmente utilizada como uma introdução ao quicksort, entretanto é menos eficiente queo método Hoare. Este Método decai para O(n2) quando o array já está ordenado ou quando só possui elementos iguais. Existem várias formas para melhorar a eficiência do algoritmo através da escolha do pivô, lidar com elementos iguais, usar outros algoritmos para pequenos arrays como o Insertion sort e assim por diante.
Complexidade[editar | editar código-fonte]
	Complexidade de tempo:
Comportamento no pior caso[editar | editar código-fonte]
O pior caso de particionamento ocorre quando o elemento pivô divide a lista de forma desbalanceada, ou seja, divide a lista em duas sub listas: uma com tamanho 0 e outra com tamanho n - 1 (no qual n se refere ao tamanho da lista original). Isso pode ocorrer quando o elemento pivô é o maior ou menor elemento da lista, ou seja, quando a lista já está ordenada, ou inversamente ordenada.
Se isso acontece em todas as chamadas do método de particionamento, então cada etapa recursiva chamará listas de tamanho igual à lista anterior - 1. Teremos assim, a seguinte relação de recorrência:
{\displaystyle T(n)=T(n-1)+T(0)+\theta (n)}
{\displaystyle T(n)=T(n-1)+T(0)+\theta (n)}
{\displaystyle T(n-1)+\theta (n)}
{\displaystyle T(n-1)+\theta (n)}
Se somarmos os custos em cada nível de recursão, teremos uma série aritmética que tem valor {\displaystyle \theta (n^{2})}{\displaystyle \theta (n^{2})}, assim, o algoritmo terá tempo de execução igual à {\displaystyle \theta (n^{2})}{\displaystyle \theta (n^{2})}.
Comportamento no melhor caso[editar | editar código-fonte]
O melhor caso de particionamento acontece quando ele produz duas listas de tamanho não maior que n/2, uma vez que uma lista terá tamanho [n/2] e outra tamanho [n/2] - 1. Nesse caso, o quicksort é executado com maior rapidez. A relação de recorrência é a seguinte:
{\displaystyle T(n)\leq 2T({\frac {n}{2}})+\theta (n)}
{\displaystyle T(n)\leq 2T({\frac {n}{2}})+\theta (n)}
que, a partir do teorema mestre, terá solução {\displaystyle T(n)=O(n*log(n))}{\displaystyle T(n)=O(n*log(n))}.
	Complexidade de espaço: {\displaystyle \theta (log_{2}n)}{\displaystyle \theta (log_{2}n)} no melhor caso e no caso médio e {\displaystyle \theta (log_{2}n)}{\displaystyle \theta (log_{2}n)} no pior caso. R. Sedgewick desenvolveu uma versão do quicksort com partição recursão de cauda que tem complexidade {\displaystyle \theta (n^{2})}{\displaystyle \theta (n^{2})} no pior caso.
Implementação[editar | editar código-fonte]
Em pseudocódigo, o quicksort ordena elementos do índice {\displaystyle i_{0}}{\displaystyle i_{0}} até {\displaystyle H_{i}}{\displaystyle H_{i}} de um array A pode ser escrito da seguinte forma:
procedimento QuickSort(X[], IniVet, FimVet)
var
 i, j, pivo, aux
início
 i <- IniVet
 j <- FimVet
 pivo <- X[(IniVet + FimVet) div 2]
 enquanto(i <= j)
 | enquanto (X[i] < pivo) faça
 | | i <- i + 1
 | fimEnquanto
 | enquanto (X[j] > pivo) faça
 | | j <- j - 1
 | fimEnquanto
 | se (i <= j) então
 | | aux <- X[i]
 | | X[i] <- X[j]
 | | X[j] <- aux
 | | i <- i + 1
 | | j <- j - 1
 | fimSe
 fimEnquanto
 se (IniVet < j) então
 | QuickSort(X, IniVet, j)
 fimSe
 se (i < FimVet) então
 | QuickSort(X, i, FimVet)
 fimse
fimprocedimento
ou de outra maneira, como:
algorithm quicksort(A, lo, hi) is
 if lo < hi then
 p := particiona(A, lo, hi)
 quicksort(A, lo, p – 1)
 quicksort(A, p + 1, hi)
algorithm particiona(A, lo, hi) is
 pivot := A[hi]
 i := lo - 1 
 for j := lo to hi - 1 do
 if A[j] < pivot then
 i := i + 1
 swap A[i] with A[j]
 if pivot < A[i + 1] then
 swap A[i + 1] with A[hi]
 return i + 1
Uma versão do algoritmo com partição aleatória na linguagem Python 3 poderia ser escrito da seguinte forma:
 1 import random
 2 
 3 class Quick(object):
 4 def particao(self, a, ini, fim):
 5 pivo = a[fim-1]
 6 start = ini
 7 end = ini
 8 for i in range(ini, fim):
 9 if a[i] > pivo:
10 end += 1
11 else:
12 end += 1 
13 start += 1
14 a[i], a[start-1] = a[start-1], a[i]
15 return start-1
16 
17 def quickSort(self, a, ini, fim):
18 if ini < fim:
19 pp = self.randparticao(a, ini, fim)
20 self.quickSort(a, ini, pp)
21 self.quickSort(a, pp+1,fim)
22 return a
23 
24 def randparticao(self,a,ini,fim):
25 rand = random.randrange(ini,fim)
26 a[rand], a[fim-1] = a[fim-1], a[rand]
27 return self.particao(a,ini,fim)
28 
29 a = [8,5,12,55,3,7,82,44,35,25,41,29,17]
30 print (a)
31 q = Quick()
32 print (q.quickSort(a,0,len(a)))
Uma versão em C++ do primeiro pseudocódigo é expressa da seguinte maneira:
#include <iostream>
void quicksort(int values[], int began, int end)
{
	int i, j, pivo, aux;
	i = began;
	j = end-1;
	pivo = values[(began + end) / 2];
	while(i <= j)
	{
		while(values[i] < pivo && i < end)
		{
			i++;
		}
		while(values[j] > pivo && j > began)
		{
			j--;
		}
		if(i <= j)
		{
			aux = values[i];
			values[i] = values[j];
			values[j] = aux;
			i++;
			j--;
		}
	}
	if(j > began)
		quicksort(values, began, j+1);
	if(i < end)
		quicksort(values, i, end);
}
int main(int argc, char *argv[])
{
	int array[10] = {5, 8, 1, 2, 7, 3, 6, 9, 4, 10};
	for(int i = 0; i < 10; i++)
	{
		std::cout << array[i] << ' ';
	}
	std::cout << std::endl;
	quicksort(array, 0, 10);
	for(int i = 0; i < 10; i++)
	{
		std::cout << array[i] << ' ';
	}
	return 0;
}
Tendo os valores como saída respectivamente, desorganizados e organizados através da função quicksort;
5 8 1 2 7 3 6 9 4 10
1 2 3 4 5 6 7 8 9 10
Há também uma implementação padrão deste algorítimo melhor detalhada no seguinte endereço função qsort
Quicksort utilizando dois ou mais pivôs[editar | editar código-fonte]
https://upload.wikimedia.org/wikipedia/commons/thumb/4/4a/Quicksort_example_small.png/220px-Quicksort_example_small.png
Algumas etapas do algoritmo quicksort.
Dentre inúmeras tentativas de melhorar a eficiência do quicksort clássico, em 2009 foi proposto por Yaroslavskiy (2009) o Dual-Pivot Quicksort[5] , onde são utilizados 2 pivôs, particionando um array de entrada em 3 partes. Yaroslavskiy demonstra que o uso de dois pivôs é mais eficaz, especialmente quando possui uma quantidade maior de dados de entrada, comprovando a sua vantagem em relação ao algoritmo quicksort clássico.
O algoritmo Dual-Pivot Quicksort, particiona um array de entrada de dados de diferentes dados primitivos (tais como, int, char, double float e long) em três partes, utilizando dois pivôs P1 e P2. Desse modo, estabelecem os seguintes ponteiros, L, K, G e left e right(índices para o primeiro e último elementos).
Segue abaixo a descrição do algoritmo.
	Para pequenos vetores (tamanho < 17) utilizar o algoritmo Insertion Sort.
	Escolha dois pivôs (P1 e P2), podemos escolher por exemplo, o primeiro (a[left]) elemento como P1 e o último como P2.
	P1 deve ser menor do que o P2, caso contrário, eles são trocados. Então, existem as seguintes partes:
	Parte I: com índices elemento mais a esquerda, de left até L-1 contendo os elementos que são menores que o P1.
	Parte II: com índices de L até K-1 contendo os elementos maiores ou iguais a P1 e menores ou iguais a P2.
	Parte III: Com índices de G + 1 até o último elemento a direita, contendo os elementos superiores P2.
	Parte IV: contendo os elementos a ser examinados com índices de K até G
	O próximo elemento na posição K pertencente a parte IV é comparado com os pivôs P1 e P2, e alocado na parte correspondente, I, II ou III.
	Os ponteiros L, K e G são alterados nas direções correspondentes.
	Os passos 4 e 5 são repetidos enquanto G se aproxima de K.
	O pivô P1 é trocado com o último elemento da parte I, o pivô P2 é trocado com o primeiro elemento da parte III.
	As etapas 1 e 7 são repetidas de forma recursiva para cada parte I, II e III.
Também foi demonstrado por Yaroslavskiy[5] que para ordenação de dados primitivos é mais eficiente a utilização do quicksort de 3 partições, sendo o número médio de comparações do Dual-Pivot Quicksort é {\displaystyle {\mathcal {(}}{2})n\ln(n)}{\displaystyle {\mathcal {(}}{2})n\ln(n)}, e o número médio de trocas é {\displaystyle {\mathcal {(}}{0,8})n\ln(n)}{\displaystyle {\mathcal {(}}{0,8})n\ln(n)},enquanto a versão clássica do algoritmo Quicksort possui {\displaystyle {\mathcal {(}}{2})n\ln(n)}{\displaystyle {\mathcal {(}}{2})n\ln(n)} e {\displaystyle {\mathcal {(}}1)n\ln(n)}{\displaystyle {\mathcal {(}}1)n\ln(n)}, respectivamente.
Uma experimento realizado pelo Budiman, Zamzami e Rachmawati (2017)[6], foi proposto, implementado e realizado experimentos com os algoritmos quicksort clássico e quicksort com dois, três, quatro e cinco pivôs. Analisando os resultados experimentais notou-se que o quicksort com um único pivô é o mais lento entre as cinco. Em segundo lugar, analisando o uso de até 5 pivôs foi comprovado que quanto mais pivôs são utilizados em um algoritmo quicksort, mais rápido seu desempenho se torna. Em terceiro lugar, o aumento de velocidade resultante da adição de mais pivôs tende a diminuir gradualmente.
Comparação com outros algoritmos de ordenação [editar | editar código-fonte]
gráfico comparando a eficiência de alguns algorítmos.
Gráfico comparativo, exibindo o comportamento assintótico de alguns algorítmos de ordenação.
O quicksort é uma versão optimizada de uma árvore binária ordenada. Em vez de introduzir itens sequencialmente numa árvore explicita, o quicksort organiza-os correntemente na árvore onde está implícito, fazendo-o com chamadas recursivas à mesma. O algoritmo faz exactamente as mesmas comparações, mas com uma ordem diferente.
O algoritmo que mais se familiariza com o quicksort é o Heapsort. Para o pior caso neste algoritmo temos {\displaystyle {\mathcal {O}}(n\log 2n).}{\displaystyle {\mathcal {O}}(n\log 2n).} Mas, o Heapsort em média trata-se de um algoritmo mais lento que o quicksort, embora essa afirmação já tenha sido muito debatida. No quicksort permanece o caso do pior caso, à exceção quando se trata de usar a variante Intro sort, que muda para Heapsort quando um pior caso é detectado. Caso se saiba à partida que será necessário o uso do heapsort é aconselhável usá-lo directamente, do que usar o introsort e depois chamar o heapsort, torna mais rápido o algoritmo.
O quicksort também compete com o Mergesort, outro algoritmo de ordenação recursiva, tendo este o benefício de ter como pior caso {\displaystyle {\mathcal {O}}(n\log n).}{\displaystyle {\mathcal {O}}(n\log n).} Mergesort, ao contrário do quicksort e do Heapsort, é estável e pode facilmente ser adptado para operar em listas encadeadas e em listas bastante grandes alojadas num tipo de acesso lento a média como um Network-Attached Storage ou num disco. Embora o quicksort possa ser operado em listas encadeadas, por vezes escolhendo um mau pivô sem acesso aleatório. A maior desvantagem do Mergesort é que quando opera em arrays, requer {\displaystyle {\mathcal {O}}(n)}{\displaystyle {\mathcal {O}}(n)} de espaço para o melhor caso, considerando que o quicksort com um particionamento espacial e com recursão utiliza apenas {\displaystyle {\mathcal {O}}(\log n)}{\displaystyle {\mathcal {O}}(\log n)} de espaço.
Bucket sort com dois buckets é muito parecido ao quicksort (quase idêntico), o pivô neste caso é garantidamente o valor do meio do vector.
A pesquisa ou busca binária (em inglês binary search algorithm ou binary chop) é um algoritmo de busca em vetores que segue o paradigma de divisão e conquista. Ela parte do pressuposto de que o vetor está ordenado e realiza sucessivas divisões do espaço de busca comparando o elemento buscado (chave) com o elemento no meio do vetor. Se o elemento do meio do vetor for a chave, a busca termina com sucesso. Caso contrário, se o elemento do meio vier antes do elemento buscado, então a busca continua na metade posterior do vetor. E finalmente, se o elemento do meio vier depois da chave, a busca continua na metade anterior do vetor.
nálise de Complexidade[editar | editar código-fonte]
A complexidade desse algoritmo é da ordem de {\displaystyle \Theta (\log _{2}n)}{\displaystyle \Theta (\log _{2}n)}[1], em que {\displaystyle n}n é o tamanho do vetor de busca. Apresenta-se mais eficiente que a Busca linear cuja ordem é {\displaystyle O(n)}O(n)[2].
Implementações[editar | editar código-fonte]
Pseudo-Código[editar | editar código-fonte]
Um pseudo-código recursivo para esse algoritmo, dados V o vetor com elementos comparáveis e e o elemento que se deseja encontrar:
BUSCA-BINÁRIA (V[], início, fim, e)
 i recebe o índice do meio entre início e fim
 se (v[i] = e) entao
 devolva o índice i # elemento e encontrado
 fimse
 se (inicio = fim) entao
 não encontrou o elemento procurado
 senão
 se (V[i] vem antes de e) então
 faça a BUSCA-BINÁRIA(V, i+1, fim, e)
 senão
 faça a BUSCA-BINÁRIA(V, inicio, i-1, e)
 fimse
 fimse
Código em C[editar | editar código-fonte]
//Implementação Iterativa:
int PesquisaBinaria (int vet[], int chave, int Tam)
{
 int inf = 0; // limite inferior (o primeiro índice de vetor em C é zero )
 int sup = Tam-1; // limite superior (termina em um número a menos. 0 a 9 são 10 números)
 int meio;
 while (inf <= sup)
 {
 meio = (inf + sup)/2;
 if (chave == vet[meio])
 return meio;
 if (chave < vet[meio])
 sup = meio-1;
 else
 inf = meio+1;
 }
 return -1; // não encontrado
}
//Implementação Recursiva:
// x => chave | v[] => vetor ordenado | e => limite inferior (esquerda) | d => limite superior (direita)
int PesquisaBinaria (int x, int v[], int e, int d)
{
 int meio = (e + d)/2;
 if (v[meio] == x)
 return meio;
 if (e >= d)
 return -1; // não encontrado
 else
 if (v[meio] < x)
 return PesquisaBinaria(x, v, meio+1, d);
 else
 return PesquisaBinaria(x, v, e, meio-1);
}
Obs: A linguagem C fornece a função bsearch[3] na sua biblioteca padrão.
Na área de informática, ou Ciência da Computação, costuma-se usar o termo busca linear (ou busca sequencial) para expressar um tipo de pesquisa em vetores ou listas de modo sequencial, i. e., elemento por elemento, de modo que a função do tempo em relação ao número de elementos é linear, ou seja, cresce proporcionalmente. Num vetor ordenado, essa não é a pesquisa mais eficiente, a pesquisa (ou busca) binária, por exemplo, é um tipo de pesquisa com o gráfico de tempo logarítmo.
Análise de Complexidade[editar | editar código-fonte]
No melhor caso, o elemento a ser buscado é encontrado logo na primeira tentativa da busca. No pior caso, o elemento a ser buscado encontra-se na última posição e são feitas N comparações, sendo N o número total de elementos. No caso médio, o elemento é encontrado após (N+1)/2 comparações. O algoritmo de busca linear é um algoritmo O(n).
Exemplos de Código[editar | editar código-fonte]
Exemplo de código em C[editar | editar código-fonte]
/**
 * Retorna -1 caso não encontre ou a posição, caso encontre.
 */
 int procura(char vetor[], int tamanho, char elementoProcurado) {
 int i;
 for (i = 0; i < tamanho; i++) {
 if (vetor[i] == elementoProcurado) {
 return i;
 }
 }
 return -1;
 }
Exemplo de código em Pascal[editar | editar código-fonte]
function procura(vetor :array [1..10] of integer; elementoProcurado: integer ): Integer; {supondo que o vetor tem tamanho 10}
var
 i : integer;
 retorno: integer;
begin
 retorno := -1;
 for i := 1 to 10 do
 begin
 if (vetor[i] = elementoProcurado) then
 begin
 retorno := i; {retorna o índice do elemento procurado}
 break;
 end;
 end;
 procura := retorno;
end.
Exemplo de código em Java[editar | editar código-fonte]
 public int procura(Object[] vetor, Object elementoProcurado) {
 int tamanhoVetor = vetor.length; /* o for, não precisa verificar o tamanho do vetor toda 
 vez que for comparar. */
 for (int i = 0; i < tamanhoVetor; i++)
 if (vetor[i].equals(elementoProcurado))
 return i;
 return -1; // Não achou, retorna -1
 }
Exemplo de código em PHP[editar | editar código-fonte]
<?php
 /**
 * Retorna -1 caso não encontre ou a posição
 * caso encontre.
 */
 function buscaSequencial($elementoProcurado, array $vetor) {
 $tamanhoVetor = count($vetor);
 for ($i = 0; $i < $tamanhoVetor; $i++) {
 if ($vetor[$i] == $elementoProcurado) {
 return $i;
 }
 }
 return -1;
 }
$a = array(1, 2, 3, 4, 5, 6);
print "<br /> buscaSequencial(4, [1, 2, 3, 4, 5, 6]); return: "; var_dump(buscaSequencial(4,$a));
print "<br /> buscaSequencial(6, [1, 2, 3, 4, 5, 6]); return: "; var_dump(buscaSequencial(6, $a));
print "<br /> buscaSequencial(1, [1, 2, 3, 4, 5, 6]); return: "; var_dump(buscaSequencial(1, $a));
print "<br /> buscaSequencial(8, [1, 2, 3, 4, 5, 6]); return: "; var_dump(buscaSequencial(8, $a));
?>
Exemplo de código em Python[editar | editar código-fonte]
# Retorna None caso não encontre ou a posição, caso encontre.
def procura(lista, elemento):
 assert isinstance(lista, list)
 for indice in range(len(lista)):
 if lista[indice] == elemento:
 return indice
 else:
 return None
Fluxograma do Algoritmo[editar | editar código-fonte]
Busca sequencial.png
Bogosort (também conhecido como CaseSort ou Estou com Sort), é um algoritmo de ordenação extremamente ineficiente. É baseado na reordenação aleatória dos elementos. Não é utilizado na prática, mas pode ser usado no ensino de algorítmos mais eficientes. Seu nome veio do engraçado termo quantum bogodynamics e, ultimamente, a palavra bogus.
Esse algoritmo é probabilístico por natureza. Se todos os elementos a serem ordenados são distintos, a complexidade esperada é {\displaystyle O(n\times n!)}{\displaystyle O(n\times n!)}. O tempo exato de execução esperado depende do quantos diferentes valores de elementos ocorrem, e quantas vezes cada um deles ocorre, mas para casos não-triviais o tempo esperado de execução é exponencial ou super-exponencial a {\displaystyle n}n. Ele termina pela mesma razão do teorema do macaco infinito; existe alguma probabilidade de que aconteça a permutação correta, dado que em um infinito número de tentativas fatalmente a encontrará.
Deve-se notar que com os algoritmos geradores de números pseudo-aleatórios, que têm um número finito de estados e não são realmente aleatórios, o algoritmo pode nunca terminar para certos conjuntos de valores a serem ordenados.
Bogosort é um algoritmo de ordenação não estável.
Exemplo[editar | editar código-fonte]
Para se ordenar um baralho usando-se este algorítmo, seria necessário jogar as cartas ao ar, juntá-las aleatoriamente, e então verificar se as mesmas estão ordenadas.
Algorítmo[editar | editar código-fonte]
função bogosort(array)
 enquanto não está_ordenado(array)
 array := permutação_aleatória(array)
Implementações[editar | editar código-fonte]
C[editar | editar código-fonte]
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
 
bool is_sorted(int *a, int n)
{
 while ( --n >= 1 ) {
 if ( a[n] < a[n-1] ) return false;
 }
 return true;
}
 
void shuffle(int *a, int n)
{
 int i, t, r;
 for(i=0; i < n; i++) {
 t = a[i];
 r = rand() % n;
 a[i] = a[r];
 a[r] = t;
 }
}
 
void bogosort(int *a, int n)
{
 while ( !is_sorted(a, n) ) shuffle(a, n);
}
 
int main()
{
 int numbers[] = { 1, 10, 9, 7, 3, 0 };
 int i;
 
 bogosort(numbers, 6);
 for (i=0; i < 6; i++) printf("%d ", numbers[i]);
 printf("\n");
}
C++[editar | editar código-fonte]
 #include <algorithm>
 #include <vector>
 
 template<class T>
 void bogosort(std::vector<T>& array)
 {
 while (! is_sorted(array))
 std::random_shuffle(array.begin(), array.end());
 }
 
 template<class T>
 bool is_sorted(const std::vector<T>& array)
 {
 for (typename std::vector<T>::size_type i = 1; i < array.size(); ++i)
 if (array[i] < array[i-1]) return false;
 return true;
 }
Java[editar | editar código-fonte]
public static void bogoSort(int length, int range) {
	int []array = randomIntArray(length,range);
		
	while (! isSorted(array))
		array = randomArray(array);
		
	for (int i = 0; i < array.length; i++) {
		System.out.print(array[i] + " ");
	}
		
}
	
private static boolean isSorted(int [] array)
{
 for (int i = 0; i < (array.length - 1); ++i) {
 	if (array[i] > array[i+1])
 		return false;
 }
 
 return true;
}
	
private static int [] randomArray(int [] array) {
		 
 int size = array.length;
 int[] indices = new int[size]; 
 for (int i=0; i<size; i++) {
 	indices[i] = i;
 }
	 
 Random random = new Random();
 for (int i = 0; i < size; i++) {
 boolean unique = false;
 int nRandom = 0;
 while (!unique) {
 unique = true;
 nRandom = random.nextInt(size);
 for (int j = 0; j < i; j++) {
 if (indices[j] == nRandom) {
 unique = false;
 break;
 }
 }
 } 
	 
 indices[i] = nRandom; 
 }
	 
 int [] result = new int[size];
 for (int k = 0; k < size; k++) {
 result[indices[k]] = array[k];
 }
 return result;
}
	
private static int[] randomIntArray(int length, int n)
{
 int[] a = new int[length];
 Random generator = new Random();
 for (int i = 0; i < a.length; i++)
 {
 a[i] = generator.nextInt(n);
 }
 return a;
}
Pascal[editar | editar código-fonte]
 program bogosort (input, output);
 const max=10; {*Tamanho do vetor *}
 type vetor=array[1..max] of integer;
 var lista, lista1: vetor;
 i: integer;
 j: boolean;
 pos: integer;
 
 	 function teste(var proto: vetor): boolean; {*Verifica se o vetor NÃO está ordenado.*}
 	 var i: integer;
 	 begin
 		 teste:=true;
 		 for i:=2 to max do
 			 if (proto[i]<proto[i-1]) then
 				 break;
 		 if (i=max) and (proto[max]>=proto[max-1]) then
 			 teste:=false;
 	 end;
 
 begin
 	 randomize; {*Inicializa o gerador de numeros aleatórios *}
 	 writeln('Escreva abaixo os ', max,' elementos do vetor:');
 	 for i:=1 to max do
 	 begin
 		 read(lista[i]); 
 		 lista1[i]:=lista[i];
 	 end;
 	 for i:=1 to max do {*Escreve o vetor recebido *}
 		 write(lista1[i],' ');
 	 writeln;
 	 while teste(lista1) do {*Enquanto o vetor nao esta ordenado...*}
 	 begin
 		 j:=true;
 		 for i:=1 to max do {*Inicializa o vetor auxiliar *}
 			 lista1[i]:=0;
 		 for i:=1 to max do {* Este loop preenche aleatoriamente o vetor auxiliar *}
 		 begin
 			 j:=true;
 			 while j do {* Este while garante que nenhum dado será sobrescrito *}
 			 begin
 				 pos:= random(max)+1; {* Gera posição aleatória *}
 				 if lista1[pos]=0 then {*Garante que a posição não está ocupada *}
 				 begin
 	 				 lista1[pos]:=lista[i];
 					 j:=false;
 				 end;
 			 end;
 		 end;
 		 for i:=1 to max do	{* Imprime na tela a tentativa *}	
 			 write(lista1[i],' ');
 		 writeln;		
 	 end;
 	 write('A LISTA FOI ORDENADA!');
 end.
Perl[editar | editar código-fonte]
 use List::Util qw(shuffle);
 
 sub bogosort {
 my @a = @_;
 my @sorted = sort @a;
 while("@a" ne "@sorted") {
 @a = shuffle(@a);
 }
 return @a;
 }
Python[editar | editar código-fonte]
from random import shuffle
 
def bogosort(seq):
 while not all(x <= y for x, y in zip(seq, seq[1:])):
 shuffle(seq)
 return seq
Ruby[editar | editar código-fonte]
def bogosort(seq)
 seq.shuffle! while not seq.each_cons(2).all? {|a,b| a <= b}
end
Fluxograma[editar | editar código-fonte]
Bogosort.png
Bibliografia
https://pt.wikipedia.org/wiki/Algoritmo_de_ordenação