Algoritmo de ordenação que insere cada elemento na posição correta da parte já ordenada do array, como organizar cartas na mão.
O Insertion Sort funciona como organizar cartas na mão. Pega uma carta por vez e a insere na posição correta entre as cartas já organizadas. Começa considerando o primeiro elemento como já ordenado. Para cada elemento seguinte, compara com os anteriores e desloca os maiores para a direita até encontrar a posição correta para inserir. É eficiente para arrays pequenos ou quase ordenados, e é usado na prática como parte de algoritmos híbridos como o TimSort (Python) e IntroSort (C++).
“O Insertion Sort é adaptativo. Para arrays quase ordenados, tem performance próxima de O(n). É o algoritmo mais eficiente para arrays pequenos (< 10-20 elementos).”
No pior caso, cada elemento é comparado com todos os anteriores.
Comparações: 1 + 2 + ... + (n-1) = n(n-1)/2 = O(n²)
Ordena in-place. Só usa uma variável auxiliar para a chave.
Array já ordenado. O loop interno não executa nenhuma iteração.
Array invertido. Cada elemento é deslocado para o início.
| Algoritmo | Tempo | Espaco | Estavel | Melhor Para |
|---|---|---|---|---|
| Insertion Sort(atual) | O(n²) | O(1) | Sim | Arrays pequenos, dados quase ordenados |
| Selection Sort | O(n²) | O(1) | Nao | Quando trocas são caras |
| Bubble Sort | O(n²) | O(1) | Sim | Fins didáticos |
| Merge Sort | O(n log n) | O(n) | Sim | Grandes datasets |
Pratique respondendo a perguntas comuns de entrevistas tecnicas. Clique em uma pergunta para iniciar uma sessao de pratica com IA.
1def insertion_sort(array):Definição2 for i in range(1, len(array)):Loop Externo3 key = array[i]Elemento Chave4 j = i - 15 6 while j >= 0 and array[j] > key:Loop Interno7 array[j + 1] = array[j]Deslocamento8 j -= 19 10 array[j + 1] = keyInserção11 12 return array13