Insertion Sort
💡 Entendendo a ideia
O Insertion Sort (ou algoritmo de ordenação por inserção) opera de maneira a construir a ordenação progressiva do vetor. Sua lógica envolve percorrer o vetor da segunda posição até a última, considerando cada elemento como uma carta a ser inserida na mão ordenada.
Na prática, o algoritmo compara cada elemento com os anteriores, deslocando-os para a direita enquanto encontra posições adequadas. Esse processo de inserção é repetido até que todo o vetor esteja ordenado.
Dessa forma, o Insertion Sort começa com uma mão vazia (vetor não ordenado) e insere cada carta (elemento) na posição correta, construindo gradualmente uma mão ordenada (vetor ordenado). Esse método é eficaz para lidar com listas pequenas ou parcialmente ordenadas, proporcionando uma abordagem eficiente para a tarefa de ordenação.
🧑💻 Do conceito ao código
void insertionSort(int v[], int tam){
for(int i = 1; i < tam; i++){
int chave = v[i];
int j = i-1;
while(j>=0 && v[j]>chave){
v[j+1] = v[j];
j--;
}
v[j+1] = chave;
}
}