Insertion Sort
O algoritmo insertion sort consiste em percorrer o vetor no sentido inverso até encontrar um elemento menor em relação ao elemento atual e então inseri-lo no lado esquerdo do elemento menor e por fim deslocar todos os elementos maiores a direita.
Implementação:
void insertion_sort(int v[], int n) {
// para cada posição do vetor (1º loop)
// observe que começamos pelo 2º elemento, pois consideramos que o 1º elemento já está ordenado
for (int i = 1; i < n - 1; ++i) {
// guardar elemento
int elemento = v[i];
int j = i - 1;
bool encontrou = false;
// percorrer no sentido inverso enquanto não chegar ao início do vetor e não encontrar um menor
while (j >= 0 && !encontrou) {
// se o elemento do 2º loop (da posição "j") for maior que o elemento do 1º loop (da posição "i")
if (v[j] > elemento) {
// deslocar elemento do 2º loop para a direita, para poder liberar espaço para inserir o "elemento" na posição correta
v[j + 1] = v[j];
j--;
} else {
// se o elemento do 2º percurso for menor, encontramos a posição onde o elemento do 1º loop deve ser inserido
encontrou = true;
}
}
// inserir elemento na posição encontrada
v[j + 1] = elemento;
}
}