A expressão da soma dos passos de cada iteração, (1 + (n - 1)) n/2, está incorreta, pois a quantidade de termos (iterações) na PA é (n - 1) e não n. Um contra-exemplo é values = [90, 20, 16, 5, 1], onde a soma dos passos é dada por 1 + 2 + 3 + 4 = 10 e usando a expressão temos (1 + (5 - 1)) 5/2 = 5 * 5/2 = 12,5 ≠ 10. O passo a passo de cada iteração usando o algoritmo Insertion Sort:
Então, usando a fórmula da soma dos termos de uma PA, (a1 + an) n/2, temos que a expressão correta da soma dos passos de cada iteração é (1 + (n - 1)) (n - 1)/2, onde (n - 1) é a quantidade de termos. Voltando ao exemplo, agora temos (1 + (5 - 1)) (5 - 1)/2 = 5 4/2 = 10.
O mesmo erro acontece no material de Selection Sort.
A expressão da soma dos passos de cada iteração, (1 + (n - 1)) n/2, está incorreta, pois a quantidade de termos (iterações) na PA é (n - 1) e não n. Um contra-exemplo é
values = [90, 20, 16, 5, 1], onde a soma dos passos é dada por 1 + 2 + 3 + 4 = 10 e usando a expressão temos (1 + (5 - 1)) 5/2 = 5 * 5/2 = 12,5 ≠ 10. O passo a passo de cada iteração usando o algoritmo Insertion Sort:1° Iteração: inserção ordenada de 20 values = [90, 20, 16, 5, 1] values = [20, 90, 16, 5, 1] -> 1° passo
2° Iteração: inserção ordenada de 16 values = [20, 90, 16, 5, 1] values = [20, 16, 90, 5, 1] -> 2° passo values = [16, 20, 90, 5, 1] -> 3° passo
3° Iteração: inserção ordenada de 5 values = [16, 20, 90, 5, 1] values = [16, 20, 5, 90, 1] -> 4° passo values = [16, 5, 20, 90, 1] -> 5° passo values = [5, 15, 20, 90, 1] -> 6° passo
4° Iteração: inserção ordenada de 1 values = [5, 15, 20, 90, 1] values = [5, 15, 20, 1, 90] -> 7° passo values = [5, 15, 1, 20, 90] -> 8° passo values = [5, 1, 15, 20, 90] -> 9° passo values = [1, 5, 15, 20, 90] -> 10° passo
Então, usando a fórmula da soma dos termos de uma PA, (a1 + an) n/2, temos que a expressão correta da soma dos passos de cada iteração é (1 + (n - 1)) (n - 1)/2, onde (n - 1) é a quantidade de termos. Voltando ao exemplo, agora temos (1 + (5 - 1)) (5 - 1)/2 = 5 4/2 = 10.
O mesmo erro acontece no material de Selection Sort.