Escrito por
Mateus Almeida
em
Análise Insertion Sort
Pseudocódigo
1 |PROCEDIMENTO InsertionSort(A[] : Inteiro):
2 |VAR
3 | |i, j : Inteiro
4 |INICIO
5 | |PARA j <- 2 ATÉ Comprimento(A), FAÇA:
6 | | |chave <- A[j] // Insere A[j] na parte ordenada A[1..j-1]
7 | | |i <- j - 1
8 | | |ENQUANTO i > 0 e A[i] > chave, FAÇA:
9 | | | |A[i+1] <- A[i]
10 | | | |i <- i - 1
11 | | |FIM-ENQUANTO
12 | | |A[i+1] <- chave
13 | |FIM-PARA
14 |FIM
Corretude
Laço invariante
Laço para as linhas 5 a 13.
Invariante
Para j=k, A[1..K-1] está ordenado.
Inicialização
Para K=2, temos que A[1..K-1]=A[1..1], ou seja, uma sequência de um único elemento do qual está trivialmente ordenado.
Manutenção
Supondo que o invariante é verdadeiro antes da k-ésima iteração, copiamos o elemento da posição j para a variável chave (linha 6). Nas linhas (7 a 11) deslocamos os elementos maiores que a chave em A[1..k-1] uma posição para a direita. Na linha 12, a chave é inserida na posição anterior ao último elemento deslocado (i+1). Desta forma, a sequência resultante é composta por A[1..i] ordenada, com elementos menores ou iguais a chave, a chave na posição A[i+1] e a sequência A[i+z..k] ordenada com elementos maiores do que a chave. Assim, antes da (k+1)-ésima iteração, temos que A[1..k] está ordenado.
Finalização
Após a n-ésima iteração do laço invariante, temos que n=k e, como foi mostrado na manutenção, A[1..n] está ordenado.
Complexidade de tempo
O melhor caso para o insertion sort ocorre quando o vetor está ordenado, assim, o laço while não será executado.
O pior caso ocorre quando o vetor está ordenado de forma inversa, assim, o laço while interno terá que realizar todas comparações.
O caso médio também é O(n^2), pois, o algoritmo percorre o vetor diversas vezes realizando trocas, independentemente da ordem dos elementos.
\[1+2+3+...+n-3+n-2+n-1+n
\\= \sum_{i=1}^{n}i \\= n(n+1)/2\]
Melhor caso
Comparações
\[\sum_{i=2}^{n}1 = (n-2)+1 = n-1 = \Omega(n)\]
Movimentações
\[1+\sum_{i=2}^{n}2
\\
=1+2((n-2)+1)
\\
=1+2(n-1) = 1+(2n+2)
\\
=2n-1\]
Pior caso
Comparações
\[\sum_{i=2}^{n}\sum_{j=1}^{i}1
\\
=\sum_{i=2}^{i}(i-1)+1
\\
=\sum_{i=2}^{i}i
\\= 2+3+4+...+(n-2)+(n-1)+n
\\=n(n+1)/2 = O(n^{2})\]
Movimentações
\[1+\sum_{i=2}^{n}2 + \sum_{i=2}^{n}\sum_{j=1}^{i-1}1
\\
=(n^{2}+3n-2)/2\]
Caso médio
Para cada valor de j, a linha 8 é executada de 1 a j vezes.
Qual a probabilidade dela ser executada t vezes? R: 1/j.
\[E\left [ x \right ] = t(1/j)\]
Número esperado de execuções (linha 8)
\[\sum_{i=1}^{n}\sum_{j=2}^{i}E\left [ x \right ]
\\
=\sum_{i=1}^{n}\sum_{j=2}^{i}1/2
\\
=1/2\sum_{i=1}^{n}\sum_{j=2}^{i}1
\\
=1/2(n(n-1)/2)
\\
=n(n-1)/4 = \Theta(n^{2})\]
Número esperado de execuções no total (linha 8)
\[\sum_{j=2}^{j}(j+1)/2
\\=(1/2)\sum_{j=2}^{n}(j+1)
\\=((n+4)(n-1))/4
\\=\Theta(n^{2})\]