Ordenação por inserção

Esta página procura explicar o que é análise de algoritmos. A explicação usa o algoritmo de ordenação por inserção como exemplo.

A página é baseada na seção 2 do capítulo 2 do CLRS.

Ordenação por Inserção

Considere o seguinte problema:

Problema da ordenação:  Rearranjar um vetor A[1 .. n] de modo que ele fique em ordem crescente.

Eis um algoritmo que resolve o problema da ordenação inserindo cada elemento do vetor na posição apropriada da parte do vetor que já está ordenada:

Ordenação-por-Inserção (A, n)
1 . para j := 2 até n
2 .ooo x := A[ j]
3 .ooo i := j−1
4 .ooo enquanto i > 0 e A[i] > x
5 .oooooo A[i+1] := A[i]
6 .oooooo i := i−1
7 .ooo A[i+1] := x

Exercícios 1

  1. Diga o que o algoritmo Ordenação-por-Inserção faz.

Análise 1: O algoritmo funciona?

A melhor maneira de mostrar que um algoritmo iterativo faz o que promete é exibir um invariante do processo iterativo. No presente caso, isso é fácil: no início de cada repetição do para (linha 1), imediatamente antes de verificar se j ≤ n,

o vetor A[1 .. j−1] é crescente.

Esse invariante é trivialmente verdadeiro na primeira repetição do para (pois j = 2 nesse caso). Se o invariante for verdadeiro na última repetição do para (quando j = n+1), nosso problema está resolvido.

1 crescente j−1 j       n
333 555 555 666 888 444 999 222 999 222

O invariante de um algoritmo iterativo é análogo à hipótese de indução em uma prova por indução matemática.

Exercícios 2

  1. ★ Prove o invariante do algoritmo Ordenação-por-Inserção.
  2. ★ Qual a diferença entre provar que um algoritmo está correto e descrever os passos do algoritmo em português (para j de 2 a n, o algoritmo procura na parte inicial do vetor a posição correta para A[ j] …)

Análise 2: Quanto tempo consome?

A pergunta fundamental da análise de algoritmos é Quanto tempo o algoritmo consome?  É claro que a resposta vai depender

  1. do vetor A[1 .. n] e
  2. da máquina que executa o algoritmo.

A contribuição da máquina é simples: ela multiplica o consumo de tempo do algoritmo por um fator constante, ou seja, por um número que não depende de n. Por exemplo, se trocarmos nossa máquina por outra duas vezes mais lenta, o consumo de tempo será multiplicado por 2. Por outro lado, se usarmos uma máquina duas vezes mais rápida, o consumo de tempo será multiplicado por ½ .  Portanto, podemos ignorar a contribuição da máquina e exprimir o consumo em unidades de tempo, sem especificar o valor da unidade.

Podemos dizer então que o consumo de tempo do algoritmo é função apenas do vetor A[1 .. n]. Vamos imaginar, por enquanto, que o consumo depende tão somente do tamanho do vetor: para cada n, o algoritmo consome T(n) unidades de tempo. (As coisas não são tão simples, na realidade, pois nem todos os vetores de tamanho n consomem o mesmo tempo.)

Trataremos a seguir de calcular T(n) para o algoritmo de inserção. Vamos supor que cada execução de cada linha do código consome 1 unidade de tempo e calcular o número de execuções de cada linha. Para alguma linhas, é possível determinar o número exato; para outras, teremos o número de pior caso:

Ordenação-por-Inserção (A, n)  
1 . para j crescendo de 2 até n = n
2 .ooo x := A[ j] = n−1
3 .ooo i := j−1 = n−1
4 .ooo enquanto i > 0 e A[i] > x ≤ 2 + 3 + ... + n
5 .oooooo A[i+1] := A[i] ≤ 1 + 2 + 3 + ... + n−1
6 .oooooo i := i−1 ≤ 1 + 2 + 3 + ... + n−1
7 .ooo A[i+1] := x = n−1

A soma dos números na coluna direita dá uma estimativa de T(n) no pior caso:

T(n) ≤ (3/2)n2 + (7/2)n − 4.

O coeficiente 3/2 de n² é artificial, pois resultou da hipótese arbitrária de 1 unidade de tempo por linha. Mas o n²  é natural e característico do algoritmo em si. Para valores grandes de n, o termo n² é muito maior que (7/2)n − 4. Em resumo, n² é a única parte sólida e significativa de (3/2)n² + (7/2)n − 4. Todo o resto depende da máquina (e sistema operacional) que estivermos usando e de certos detalhes de implementação do algoritmo. Basta dizer então que o algoritmo Ordenação-por-Inserção consome

Ο(n2)

unidades de tempo. A seguinte tabela resume o cáculo do consumo de tempo do algoritmo usando notação assintótica:

Ordenação-por-Inserção (A, n)    
1 . para j crescendo de 2 até n   Θ(n)
2 .ooo x := A[ j]   Θ(n)
3 .ooo i := j−1   Θ(n)
4 .ooo enquanto i > 0 e A[i] > x   Ο(n²)
5 .oooooo A[i+1] := A[i]   Ο(n²)
6 .oooooo i := i−1   Ο(n²)
7 .ooo A[i+1] := x   Θ(n)

Os exercícios a seguir mostram que a cota superior Ο(n²) para o consumo de tempo de Ordenação-por-Inserção não é exagerada: para alguns vetores A[1 .. n], o algoritmo consome Ω(n²) unidades de tempo. Portanto, no pior caso, T(n) = Θ(n²).

Exercícios 3

  1. ★ Refaça a soma da coluna direita da tabela acima. O resultado (3/2)n2 + (7/2)n − 4 está correto?
  2. Prove que (3/2)n2 + (7/2)n − 4 está em Ο(n²). Conclua que T(n) = Ο(n²).
  3. ★ Faça uma análise análoga à que fizemos na seção acima para mostrar que no pior caso T(n) ≥ (3/2)n2 + (7/2)n − 4. Descreva os vetores A[1 .. n] que correspondem ao pior caso. Conclua que, no pior caso, T(n) = Ω(n²).
  4. ★ Qual o consumo de tempo de Ordenação-por-Inserção no melhor caso? (Suponha que cada execução de cada linha do algoritmo consome 1 unidade de tempo.) Como são os vetores que correspondem ao melhor caso?

Número de comparações

O desempenho do algoritmo Ordenação-por-Inserção pode ser calculado de uma maneira indireta que é muito conveniente.

Considere o número de execuções da comparação A[i] > x na linha 4. O tempo que decorre entre duas comparações consecutivas não depende de n. Assim, o consumo de tempo do algoritmo é proporcional ao número de execuções da comparação.

É fácil constatar que o número de execuções da comparação A[i] > x não passa de (n² − n)/2. Portanto, o consumo de tempo do algoritmo é Ο(n²).

No pior caso, o número de comparações A[i] > x é pelo menos (n² − n)/2. Portanto, o consumo de tempo do algoritmo no pior caso é Ω(n²).

Exercícios 4

  1. ★ Verifique que o número de execuções da comparação A[i] > x no pior caso é exatamente (n² − n)/2. Qual o número de comparações no melhor caso?
  2. ★ Seja C(n) o número de execuções da atribuição A[i+1] := A[i] na linha 5 de Ordenação-por-Inserção. O consumo de tempo do algoritmo é proporcional a C(n)? Por que? Calcule C(n) no pior caso. Calcule C(n) no melhor caso caso.
  3. ★ Sabe-se que um certo algoritmo para o problema da ordenação faz Ο(n²) comparações entre elementos do vetor para processar um vetor com n elementos. Quantas comparações, no máximo, o algoritmo fará para processar um vetor com 1000 elementos?

Muito vago?

Se você perguntar a um computólogo quanto tempo o algoritmo Ordenação-por-Inserção consome para processar um vetor com n elementos, ele dirá Ο(n²). Você traduz isso mentalmente para

existe um número positivo c tal que o consumo de tempo do algoritmo não passa de cn² para todo n suficientemente grande.

À primeira vista a resposta parece muito vaga. Mas é impossível dar uma resposta mais precisa (a menos que se conheça muito bem a máquina que será usada para executar o algoritmo).

A resposta é até bastante informativa num sentido relativo: ela garante que se o tamanho do vetor for multiplicado por 10, o tempo de execução será multiplicado no máximo por 100. Isso não é tão bom quanto multiplicar o tempo por 10, mas é menos desastroso que multiplicar o tempo por 1000.

Adendo: versão recursiva da ordenação por inserção

Não há uma razão muito forte para reescrever o algoritmo de ordenação por inserção em estilo recursivo. Mas é um bom exercício fazer isso.

Inserção-R (A, n)
1 . se n > 1
2 .ooo Inserção-R (A, n−1)
3 .ooo x := A[n]
4 .ooo i := n−1
5 .ooo enquanto i > 0 e A[i] > x
6 .oooooo A[i+1] := A[i]
7 .oooooo i := i−1
8 .ooo A[i+1] := x

Quanto tempo esse algoritmo consome? Denote por T(n) o consumo de tempo no pior caso. Supondo que cada linha (exceto a linha 2) consome 1 unidade de tempo, a figura mostra o consumo de uma execução de cada linha do algoritmo,

Inserção-R (A, n)    
1 . se n > 1   1
2 .ooo Inserção-R (A, n−1)   T(n−1)
3 .ooo x := A[n]   1
4 .ooo i := n−1   1
5 .ooo enquanto i > 0 e A[i] > x   n
6 .oooooo A[i+1] := A[i]   n−1
7 .oooooo i := i−1   n−1
8 .ooo A[i+1] := x   1

Fica claro então que T satisfaz a recorrência

T(n)  =  T(n−1) + 3n + 2

para n = 2, 3, 4, etc., com valor inicial T(1) = 1. Já mostrei em outra página que uma fórmula fechada para T(n) é

T(n)  =  3n2/2 + 7n/2 − 4.

Eu poderia ter simplificado as coisas. Se estou apenas interessado em mostrar que T(n) = Ο(n²), bastaria ter verificado, por indução a partir da recorrência, que

T(n)  ≤  2n2

para n = 2, 3, 4, etc.  E isso é fácil. (Foi necessário um pouco de experimentação para casar o coeficiente 2 na frente de n² com o valor inicial 2 de n.)

Exercícios 5

  1. Diretamente a partir da recorrência T(n) = T(n−1) + 3n + 2, prove que T(n) ≤ 7n²/4 para n = 100, 101, etc.
  2. ★ Seja N(n) o número de execuções, no pior caso, da comparação A[ j] > x na linha 5 de Inserção-R. (Esse número é interessante porque é proporcional ao consumo de tempo do algoritmo no pior caso.)  Mostre que N satisfaz a recorrência

    N(n) = N(n−1) + n

    para n = 2, 3, 4, 5, etc. com valor inicial N(0) = N(1) = 0. Deduza daí que N(n) = ½ (n² + n − 2) para todo n natural não-nulo.

  3. Seja N a função definida pela recorrência N(n) = N(n−1) + n para n = 2, 3, 4, 5, etc. com valor inicial N(1) = 0. Prove, diretamente a partir da recorrência, que N(n) ≤ n² para todo n natural não-nulo.

Exercícios 6

  1. Selection-Sort. Considere o problema de colocar em ordem crescente um vetor A[1 .. n]. Escreva um algoritmo de ordenação por seleção para resolver o problema. A ideia do algoritmo é a seguinte: no início de cada iteração, o vetor A[1 .. j−1] está em ordem crescente e contém os elementos pequenos enquanto o vetor A[ j .. n] contém os elementos grandes. Escreva uma versão iterativa e uma recursiva do algoritmo. Faça uma análise do consumo de tempo do algoritmo no pior caso.