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:
|
![](http://upload.wikimedia.org/wikipedia/commons/thumb/0/0f/Insertion-sort-example-300px.gif/220px-Insertion-sort-example-300px.gif)
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(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
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.
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:
, onde é a função geradora correspondente ao número total de inversões.
Para o melhor caso (itens já ordenados) temos;
Pior caso (itens em ordem reversa) temos:
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
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
#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.
Ligações externas
- Uma animação em Java mostrando passo-a-passo a implementação do insertion sort.(Offline)
- Métodos de Ordenação Elementares.
Portal das tecnologias de informação