Insertion sort

Insertion sort

classe	Algoritmo de ordenação
estrutura de dados	Array, Listas ligadas
complexidade pior caso	$O(n^{2})$
complexidade caso médio	$O(n^{2})$
complexidade melhor caso	$O(n)$
complexidade de espaços pior caso	$O(n)$ total, $O(1)$ 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.