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, é 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 a 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[editar | editar código-fonte]

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.

Para o caso médio, assume que todas as permutações de entrada são igualmente prováveis.

Para o melhor caso (itens já ordenados) temos;

Pior caso (itens em ordem reversa) temos:

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]

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

C++[editar | editar código-fonte]

Utilizando os recursos mais recentes da linguagem (C++11) é 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 key = vetor[i];
			int j = i;
			
			while ((j > 0) && (vetor[j-1] > key)){
				vetor[j] = vetor[j-1];
				j -= 1;
			}
			vetor[j] = key;
		}
	
	}

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

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

Referências

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