Passos:
Execute o algoritmo para ver os passos gravados.
Passos:
Execute o algoritmo para ver os passos gravados.
O Insertion Sort é um algoritmo de ordenação que constrói a parte ordenada da lista um elemento por vez. A cada passo ele remove um elemento da parte não ordenada do array e o insere na posição correta da parte já ordenada, deslocando os demais elementos para a direita.
Complexidade: No pior caso e no caso médio (lista em ordem inversa ou aleatória), a complexidade de tempo é O(n²). No melhor caso (lista já ordenada), o algoritmo apenas percorre a lista uma vez sem precisar deslocar elementos, resultando em complexidade de tempo O(n). Assim como o Bubble Sort, ele é um algoritmo in-place com complexidade de espaço O(1).
1const insertionSort = (arr) => {
2 // Assume que a primeira posição já está ordenada
3 for (let i = 1; i < arr.length; i++) {
4 let j = i;
5
6 // Troca com o elemento da esquerda enquanto for menor
7 while (j > 0 && arr[j - 1] > arr[j]) {
8 [arr[j - 1], arr[j]] = [arr[j], arr[j - 1]];
9 j--;
10 }
11 }
12 return arr;
13};O Insertion Sort (Ordenação por Inserção) constrói a lista ordenada progressivamente, um elemento de cada vez. É semelhante a organizar cartas de baralho na mão: você pega uma carta do monte desordenado e a encaixa na posição correta entre as cartas que já estão em ordem.
Diferente do Bubble Sort, o Insertion Sort tem muita utilidade no mundo real. Embora seja ineficiente para listas gigantes e totalmente desordenadas, ele é incrivelmente rápido para listas pequenas (menos de 50 itens) ou dados que já estão quase ordenados. Por causa dessa eficiência cirúrgica, linguagens como Python e Java usam algoritmos híbridos (como o TimSort), que dividem listas imensas em pedaços pequenos e acionam o Insertion Sort por baixo dos panos para ordenar esses fragmentos na velocidade da luz.