Insertion sort

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
	Esta caixa: ver; discutir;

Insertion Sort, ou ordenação por inserção, é um 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 como algumas pessoas organizam um baralho num jogo de cartas. Imagine que você está jogando ás 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 a que as cartas obedeçam à 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, a 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 em diante, até 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 do 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

Em termos de comparação com outros algoritmos de ordenação, o Insert 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(n²)	O(n²)
Bubble sort	O(n)	O(n²)	O(n²)
Selection sort	O(n²)	O(n²)	O(n²)

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

Para a ordenação de uma matriz ordenada de forma aleatória, com diferentes chaves, o algoritmo - Insertion Sort-, se utiliza de ¼ N² comparações e ½ N² trocas. $\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:

$B(z)=zB(z)+{\frac {z}{2}}\sum _{n=>0}kz^{k}=zB(z)+{\frac {1}{2}}{\frac {z^{2}}{(1-z)^{2}}}$ , onde $B(z)$ é a função geradora correspondente ao número total de inversões.

Para o melhor caso (itens já ordenados) temos; $\sum _{i=1}^{n-1}1=n-1=O(n)$

Pior caso (itens em ordem reversa) temos: $\sum _{i=1}^{n-1}i={\frac {(n-1)(n)}{2}}={\frac {n^{2}}{2}}-{\frac {n}{2}}=O(n^{2})$

Matrizes Parcialmente Ordenadas

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

Vantagens

É 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

Alto custo de movimentação de elementos no vetor.

Implementações

Pseudocódigo

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

#include <math.h>
#include <stdio.h>

void insertionSort(int arr[], int size){
    int i, j, key;
    for (i = 1; i < size; 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 size){
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

void main(){
    int arr[] = { 12, 11, 13, 5, 6 };
    int size = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, size);
    printArray(arr, size);
}

C++

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

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

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#

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;

    }
}

Swift

func insert(_ array: inout [Int], rightIndex: Int, value: Int) {
	var leftIndex = rightIndex

	while leftIndex >= 0 && value < array[leftIndex] {
		array[leftIndex + 1] = array[leftIndex]
		leftIndex -= 1
	}

	array[leftIndex + 1] = value
}

func insertionSort(_ array: inout [Int]) {
	if array.count < 1 {
		return
	}

	for rightIndex in 1..<array.count {
		let value = array[rightIndex]
		insert(&array, rightIndex: rightIndex - 1, value: value)
	}
}

TypeScript

function insertionSort(list: number[]): number[] {
  const clonedList = [...list]

  for (let increment = 1; increment < clonedList.length; increment++) {
    const currentValue = clonedList[increment]
    let j = increment - 1

    while (j >= 0 && clonedList[j] > currentValue) {
      clonedList[j + 1] = clonedList[j]
      j -= 1
    }
    clonedList[j + 1] = currentValue
  }

  return clonedList
}

Rust

pub fn insertion_sort<T: Ord>(array: &mut [T]) {
    for i in 1..array.len() {
        let mut j = i;
        while j > 0 && array[j] < array[j - 1] {
            array.swap(j, j - 1);
            j = j - 1;
        }
    }
}

Ver também

Referências

Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 5.2.1: Sorting by Insertion, pp. 80–105.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Section 2.1: Insertion sort, pp. 15–21.
Michael T Goodrich, Algorithm Desing: Foundations, Analysis and Internet Examples, Second Edition. 2002, ISBN 0-471-38365-1. Section 4.4.6; Comparison of Sorting Algorithms, pp. 244-245.
Robert Sedgewick, Philippe Flajolet, An Introduction to the Analysis of Algorithms, Second Edition, Pearson Education, 2013. ISBN-13: 978-0-321-90575-8. Section 7.6: Inversions and Insertion Sorts, pp. 384-388.