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 existentes