Insertion sort

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Insertion sort
classe Algoritmo de ordenação
estrutura de dados Array, Listas ligadas
complexidade pior caso
complexidade caso médio
complexidade melhor caso
complexidade de espaços pior caso total, auxiliar
estabilidade estável
Algoritmos
Exemplo de funcionamento do insertion sort em uma lista de inteiros aleatórios
Insertion-sort-example-300px

Insertion sort, ou ordenação por inserção, é um simples algoritmo de ordenação, eficiente quando aplicado a um pequeno número de elementos. Em termos gerais, ele percorre um vetor de elementos da esquerda para a direita e à medida que avança vai deixando os elementos mais à esquerda ordenados. O algoritmo de inserção funciona da mesma maneira com que muitas pessoas ordenam cartas em um jogo de baralho como o pôquer.[1]

Características[editar | editar código-fonte]

  • Menor número de trocas e comparações entre os algoritmos de ordenação O(n) quando o vetor está ordenado.
  • Pior caso O(n²)

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];
                          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]

int *InsertionSort(int original[], int length)
{
	int i, j, atual;

	for (i = 1; i < length; i++)
	{
		atual = original[i];
		j = i - 1;

		while ((j >= 0) && (atual < original[j]))
		{
			original[j + 1] = original[j];
            j = j - 1;
		}
    
		original[j + 1] = atual;
	}

	return (int*)original;
}

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

Referências

  1. AZEREDO, Paulo A. (1996). Métodos de Classificação de Dados e Análise de suas Complexidades (Rio de Janeiro: Campus). ISBN 85-352-0004-5. 

Ligações externas[editar | editar código-fonte]