Ordenamento por Inserção
Última atualização
O ordenamento por inserção constrói o array ordenado um elemento de cada vez. Ele pega o próximo elemento não ordenado (a "chave") e desloca cada elemento maior da região ordenada uma posição para a direita, e então coloca a chave na lacuna. É exatamente como a maioria das pessoas ordena uma mão de cartas. Pressione reproduzir acima para ver cada chave sendo inserida, ou avance os deslocamentos um a um.
O ordenamento por inserção é muito rápido em entradas pequenas ou quase ordenadas - ele roda em O(n) quando os dados já estão ordenados - por isso muitos ordenamentos híbridos recorrem a ele para subarrays pequenos.
Complexidade de tempo e espaço
| Caso | Complexidade | Notas |
|---|---|---|
| Melhor caso | O(n) | Já ordenado |
| Caso médio | O(n²) | Ordem aleatória |
| Pior caso | O(n²) | Ordem inversa |
| Espaço | O(1) | No local |
| Estável | Sim | Elementos iguais mantêm sua ordem relativa |
Passo a passo
| Passo | O que acontece |
|---|---|
| 1 | Trate o primeiro elemento como uma região ordenada de tamanho um. |
| 2 | Pegue o próximo elemento como a chave. |
| 3 | Desloque cada elemento ordenado maior que a chave uma posição para a direita. |
| 4 | Insira a chave na lacuna aberta. |
| 5 | Repita até que todos os elementos tenham sido inseridos. |
Exemplo resolvido
Ordenando [5, 2, 4, 1]:
| Passagem | Array | Ação |
|---|---|---|
| Início | [5, 2, 4, 1] | 5 é a região ordenada inicial de tamanho um. |
| 1 | [2, 5, 4, 1] | Chave 2: desloca 5 para a direita, insere 2 no início. |
| 2 | [2, 4, 5, 1] | Chave 4: desloca 5 para a direita, 2 é menor então para, insere 4. |
| 3 | [1, 2, 4, 5] | Chave 1: desloca 5, 4, 2 para a direita, insere 1 no início. |
| Fim | [1, 2, 4, 5] | Todos os elementos inseridos; o array está ordenado. |
Quando usar o ordenamento por inserção
| Use quando | Evite quando |
|---|---|
O array é pequeno (aproximadamente n < 20). | O array é grande e está em ordem aleatória. |
Os dados já estão quase ordenados, dando o melhor caso O(n). | Você precisa de um pior caso garantido de O(n log n). |
Você precisa de um ordenamento estável, no local e com espaço extra O(1). | Mover elementos é caro, pois ele faz muitos deslocamentos. |
| Os dados chegam de forma incremental e devem permanecer ordenados online. | A entrada está em ordem inversa, seu pior caso O(n²). |
Código de Insertion Sort
Uma implementação limpa e executável de Insertion Sort em Python, JavaScript, Java, C++, C. Escolha uma linguagem, copie o código ou abra-o já carregado no Playground da Coddy.
Código de Insertion Sort em Python
Python
1def insertion_sort(a):2 for i in range(1, len(a)):3 key = a[i]4 j = i - 15 # Shift larger elements one slot to the right6 while j >= 0 and a[j] > key:7 a[j + 1] = a[j]8 j -= 19 a[j + 1] = key10 return a11
12
13nums = [7, 3, 9, 1, 5, 8, 2]14print("Before:", nums)15insertion_sort(nums)16print("After: ", nums)Código de Insertion Sort em JavaScript
JavaScript
1function insertionSort(a) {2 for (let i = 1; i < a.length; i++) {3 const key = a[i];4 let j = i - 1;5 // Shift larger elements right to open a slot for key6 while (j >= 0 && a[j] > key) {7 a[j + 1] = a[j];8 j--;9 }10 a[j + 1] = key;11 }12 return a;13}14
15const data = [5, 2, 9, 1, 7, 3];16console.log("Before:", data);17console.log("Sorted:", insertionSort([...data]));Código de Insertion Sort em Java
Java
1import java.util.Arrays;2
3public class Main {4 static void insertionSort(int[] arr) {5 for (int i = 1; i < arr.length; i++) {6 int key = arr[i];7 int j = i - 1;8 // Shift larger elements one slot to the right9 while (j >= 0 && arr[j] > key) {10 arr[j + 1] = arr[j];11 j--;12 }13 arr[j + 1] = key;14 }15 }16
17 public static void main(String[] args) {18 int[] arr = {7, 3, 9, 1, 5, 8, 2};19 System.out.println("Before: " + Arrays.toString(arr));20 insertionSort(arr);21 System.out.println("After: " + Arrays.toString(arr));22 }23}Código de Insertion Sort em C++
C++
1#include <iostream>2#include <vector>3
4void printVec(const std::vector<int>& a) {5 for (int x : a) std::cout << x << " ";6 std::cout << "\n";7}8
9void insertionSort(std::vector<int>& a) {10 for (size_t i = 1; i < a.size(); ++i) {11 int key = a[i];12 int j = static_cast<int>(i) - 1;13 // Shift larger elements one slot to the right14 while (j >= 0 && a[j] > key) {15 a[j + 1] = a[j];16 --j;17 }18 a[j + 1] = key;19 }20}21
22int main() {23 std::vector<int> data = {7, 3, 9, 1, 5, 8, 2};24 std::cout << "Before: ";25 printVec(data);26 insertionSort(data);27 std::cout << "After: ";28 printVec(data);29 return 0;30}Código de Insertion Sort em C
C
1#include <stdio.h>2
3void printArr(const int a[], int n) {4 for (int i = 0; i < n; i++) printf("%d ", a[i]);5 printf("\n");6}7
8void insertionSort(int a[], int n) {9 for (int i = 1; i < n; i++) {10 int key = a[i];11 int j = i - 1;12 // Shift larger elements one slot to the right13 while (j >= 0 && a[j] > key) {14 a[j + 1] = a[j];15 j--;16 }17 a[j + 1] = key;18 }19}20
21int main(void) {22 int data[] = {7, 3, 9, 1, 5, 8, 2};23 int n = sizeof(data) / sizeof(data[0]);24 printf("Before: ");25 printArr(data, n);26 insertionSort(data, n);27 printf("After: ");28 printArr(data, n);29 return 0;30}Perguntas frequentes sobre o ordenamento por inserção
Qual é a complexidade de tempo do ordenamento por inserção?
O ordenamento por inserção é
O(n²) em média e no pior caso, mas O(n) em um array já ordenado ou quase ordenado. Ele usa espaço extra O(1).O ordenamento por inserção é estável?
Sim. O ordenamento por inserção só desloca os elementos estritamente maiores que a chave, então elementos iguais nunca se cruzam e sua ordem relativa é preservada.
Quando devo usar o ordenamento por inserção?
Use-o para arrays pequenos ou dados que já estão quase ordenados. Por causa do baixo custo e do melhor caso adaptativo, algoritmos híbridos como Timsort o usam para trechos pequenos.
Qual é a diferença entre o ordenamento por inserção e o ordenamento por bolha?
Ambos são ordenamentos por comparação
O(n²), mas o ordenamento por inserção desloca elementos para abrir uma lacuna para a chave, enquanto o por bolha troca repetidamente pares adjacentes fora de ordem. O de inserção geralmente faz menos escritas e tem melhor desempenho na prática, especialmente em dados quase ordenados onde atinge seu melhor caso O(n).Por que o ordenamento por inserção é mais rápido que o merge sort em arrays pequenos?
O ordenamento por inserção tem um custo constante muito baixo e não usa recursão nem alocação extra, então em entradas pequenas ele supera os ordenamentos
O(n log n) apesar da pior complexidade assintótica. É exatamente por isso que ordenamentos híbridos como Timsort e introsort mudam para o ordenamento por inserção em subarrays pequenos.O ordenamento por inserção funciona melhor com uma lista encadeada ou um array?
O ordenamento por inserção normalmente é escrito para arrays, onde deslocar elementos é o custo principal. Em uma lista encadeada você evita o deslocamento inserindo o nó no lugar, mas perde o acesso aleatório rápido, então encontrar o ponto de inserção ainda leva tempo linear por elemento e o custo total permanece
O(n²).Recursos relacionados
Mais visualizações
