Examine o pseudocódigo da página da Wikipedia sobre ordenação por inserção :
i ← 1
while i < length(A)
j ← i
while j > 0 and A[j-1] > A[j]
swap A[j] and A[j-1]
j ← j - 1
end while
i ← i + 1
end while
Por favor, explique por que isso é afirmado na literatura :
The number of exchanges used by insertion sort is equal to the number of
inversions in the array, and the number of compares is at least equal to
the number of inversions and at most equal to the number of inversions
plus the array size minus 1.
Uma troca de elemento adjacente (ou seja, do ' elemento selecionado atual ', com aqueles no subarray ordenado (ou seja, começando da extremidade esquerda do array original)) removeria apenas uma inversão.
Embora para uma lista dada de elementos, introduzir uma troca pode adicionar muitas inversões; digamos para a lista: 123, trocando o elemento 3com o elemento 1, que introduz 3inversões.
E o número de comparações necessárias é três:
i=1:<2,3>, i=2:<1,3>, <1,2>
Além disso, o número de inversões é três na lista:321
Esse número de inversões também é dado por nC2, onde né o tamanho da lista.
Digamos, para uma lista de tamanho ordenada reversamente 4: 4321, tenha seis inversões: <4,3>,<4,2>,<4,1>,<3,2>,<3,1>,<2,1>, que também é o número de 2-subconjuntos, de um n-conjunto. Em ambos os problemas, devido à ausência de ordenação envolvida, tenha o número de combinações a serem contadas.
As etapas (comparações+trocas) envolvidas na aplicação da ordenação por inserção à lista ordenada inversamente <4321>são:
1. i ← 1, j ← 1, A[0] > A[1]: swap A[1] and A[0], j ← 0: <3421>
2. i ← 2, j ← 2, A[1] > A[2]: swap A[2] and A[1], j ← 1: <3241>
j ← 1, A[0] > A[1]: swap A[1] and A[0], j ← 0: <2341>
3. i ← 3, j ← 3, A[2] > A[3]: swap A[3] and A[2], j ← 2: <2314>
j ← 2, A[1] > A[2]: swap A[2] and A[1], j ← 1: <2134>
j ← 1, A[0] > A[1]: swap A[1] and A[0], j ← 0: <1234>
Mas, não consigo entender quando o número máximo de comparações é igual a number of inversions + array size -1; quanto ao pior caso de uma matriz de classificação reversa, de tamanho n; o número de inversões é igual a nC2.
De onde viriam as demais comparações, ou seja, 'n-1'as comparações?
A literatura mencionada acima afirma que a fonte dessas 'n-1'comparações é:
additional compare might happen for the value of `i` from `1` to `n-1` (when `a[i]` does not reach the left end of the array).
Há confusão causada pela parte, entre colchetes; como o que se quer dizer com: (when a[i] does not reach the left end of the array).
Este caso pode significar o caso de listas, onde o 'primeiro elemento' (i=0)está em sua posição final, digamos: 1423. Ou em outras palavras, fala sobre all the possiblecomparações, incluindo aquela em que há noinversão.
Digamos que, para 1423, há duas inversões, mas é preciso ter comparações extras de: <1,4>, <1,2>, <1,3>, <2,3>. Mas, essas são então quatro comparações, não três (tamanho da matriz: 4 menos 1).
Também não estou claro sobre o texto usado na literatura, pois tal comparação não é mostrada explicitamente no algoritmo.
A mesma literatura lista seu código C++ para Insertion-sort aqui , que também não mostra explicitamente nenhuma comparação desse tipo.
Suponha que o array já esteja ordenado. Então há 0 inversões, mas você ainda tem que executar n-1 comparações.
A variante de ordenação por inserção que você está vendo executará uma comparação para cada troca que fizer. Mas para cada elemento, a menos que esse elemento seja movido para a extremidade esquerda do array, haverá uma comparação que não corresponde a uma troca. Essa é a comparação que diz ao algoritmo que ele terminou com esse elemento.