Projeto de Algoritmos

São muitas as abordagens para projetos de algoritmos. A ordenação por inserção utiliza uma abordagem incremental, onde o elemento é isolado no seu lugar apropriado, formando um subarranjo ordenado. Existe outra abordagem chamada de “dividir para conquistar”, a qual pode ser utilizada para projetar um algoritmo de ordenação cujo tempo de execução é muito menor que o da ordenação por inserção.

Muitos algoritmos são recursivos, isto é, chamam a si mesmos recursivamente para resolver problemas menores relacionados. Normalmente esses algoritmos seguem uma abordagem dividir para conquistar. De acordo com Thomas Cormen, nesta abordagem o problema é desmembrado em partes menores, que são semelhantes ao problema original; essas partes são resolvidas recursivamente e as soluções são combinadas em uma única solução para o problema original.

Este paradigma envolve três passos em cada nível da recursão: dividir (divisão do problema em um determinado número de subproblemas), conquistar (resolução dos subproblemas recursivamente, ou não), e combinar (formação da solução para o problema original por meio da combinação das soluções dadas aos subproblemas).

Um exemplo do uso dessa abordagem é o algoritmo de ordenação por intercalação, o qual segue os passos do paradigma da seguinte forma: dividir (divide a sequência de n elementos a serem ordenados em duas subsequências de n/2 elementos cada uma), conquistar (classifica as duas subsequências recursivamente, utilizando a ordenação por intercalação), e combinar (faz a intercalação – merge – das duas sequências ordenadas, de modo a produzir a resposta ordenada).

A figura abaixo demonstra a execução desse algoritmo. Nesse procedimento é necessário o arranjo que se deseja intercalar, e os índices de enumeração do arranjo. O mesmo pressupõe que os subarranjos formados pelos índices de enumeração estão em sequência ordenada. Ele os intercala (ou mescla) para formar um único subarranjo ordenado que substitua o subarranjo atual.

A

2

4

5

7

1

2

3

6

L

2

4

5

7

R

1

2

3

6

A

2

4

5

7

1

2

3

6

L

2

4

5

7

∞

R

1

2

3

6

∞

A

2

4

5

7

1

2

3

6

 k

L

2

4

5

7

∞

 i

R

1

2

3

6

∞

 j

A

1

4

5

7

1

2

3

6

 k

L

2

4

5

7

∞

 i

R

1

2

3

6

∞

 j

A

1

2

5

7

1

2

3

6

     k

L

2

4

5

7

∞

 i

R

1

2

3

6

∞

         j

A

1

2

2

7

1

2

3

6

          k

L

2

4

5

7

∞

         i

R

1

2

3

6

∞

         j

A

1

2

2

3

1

2

3

6

                k

L

2

4

5

7

∞

         i

R

1

2

3

6

∞

                j

A

1

2

2

3

4

2

3

6

                     k

L

2

4

5

7

∞

         i

R

1

2

3

6

∞

                        j

 

A

1

2

2

3

4

5

3

6

                          k

L

2

4

5

7

∞

                i

R

1

2

3

6

∞

                        j

A

1

2

2

3

4

5

6

6

                                k

L

2

4

5

7

∞

                        i

R

1

2

3

6

∞

                        j

A

1

2

2

3

4

5

6

7

                                      k

L

2

4

5

7

∞

                               i

R

1

2

3

6

∞

                               j

Abaixo o pseudocódigo desse algoritmo:

Intercala(A, p, q, r)

n₁ ¬ q – p + 1

n₂ ¬ r – q

criar arranjos L[1.. n₁ + 1] e R[1.. n₂ + 1]

para i ¬ 1 até n₁ faça

            L[i] ¬ A[p + i ­– 1]

para j ¬ 1 até n₂ faça

            R[j] ¬ A[q + j]

L[n₁ + 1] ¬ ∞

R[n₂ + 1] ¬ ∞

i ¬ 1

j ¬ 1

para k ¬ p até r faça

            se L[i] ≤ R[j] então

                        A[k] ¬ L[i]

                        i ¬ i + 1

            senão

                        A[k] ¬ R[j]

                        j ¬ j + 1

O algoritmo Intercala, pode ser utilizado como sub-rotina do algoritmo de Ordenação por Intercalação, o qual ordena os elementos de um subarranjo.

Abaixo o pseudocódigo desse algoritmo:

OrdencacaoIntercalacao(A, p, r)

se p < r então

            q ¬ └ (p + r)/2 ┘

            OrdencacaoIntercalacao(A, p, q)

            OrdencacaoIntercalacao(A, q + 1, r)

            Intercala(A, p, q, r)

Para ordenar uma sequência inteira (A), a chamada inicial ao algoritmo é efetuada passando os parâmetros: A (vetor), 1 (posição inicial do vetor) e comprimento[A] (n). Inicialmente o algoritmo divide o vetor principal em vetores temporários menores até a menor potência de 2, e depois começa a intercalar sequencias de um item, formando sequencias de dois itens; em seguida intercala sequencias de dois itens para formar sequencias de 4 itens; e assim por diante até a última sequencia ser intercalada de comprimento n.

A figura abaixo ilustra o fluxo:

Quando um algoritmo contém uma chamada recursiva a si próprio, seu tempo de execução no pode ser descrito por uma equação de recorrência, que descreve o tempo de execução total sobre um problema de tamanho n em termos do tempo de execução sobre entradas menores.

No algoritmo dividir para conquistar é preciso ter em conta seus três passos básicos. T(n) é o tempo total de execução sobre um problema de tamanho n. Caso o problema seja pequeno o bastante, então n ≤ c para alguma constante c, a solução direta demorará um tempo constante q(1). O problema é divido em a subproblemas, cada um dos quais com 1/b tamanho do problema original. O tempo D(n) é o gasto para dividir o problema em subproblemas, e o tempo C(n) é o gasto para combinar as soluções dadas as subproblemas:

 

No caso do tempo de execução do pior caso da ordenação por intercalação sobre n números têm-se as seguintes afirmações: cada passo de dividir produzirá duas subsequências de tamanho exatamente n/2; quando a ordenação é realizada sobre um único elemento ( T(n) = q(1), quando n = 1) ), o tempo é constante, no entanto; quando se tem n > 1, o tempo é desmembrado da seguinte forma: a etapa de dividir calcula o ponto médio do arranjo, o que demora um tempo constante D(n) = q(1); na etapa de conquistar, dois subproblemas são resolvidos, cada um tem o tamanho n/2, o que contribui com 2T(n/2) para o tempo de execução; por fim, na etapa de conquistar, o procedimento Intercala sobre um subarranjo de n elementos leva o tempo q(n), assim, C(n) = q(n). Ao somar as funções D(n) e C(n) para a análise da ordenação por intercalação, é somada uma função que é q(n) a uma função que é q(1); essa soma é uma função linear de n, ou seja, q(n). Dessa forma, tem-se:

Por meio do “teorema mestre” (assunto para outra ocasião), é possível demonstrar que T(n) = q(n lg n), onde lg significa log₂ n. Para entradas suficientemente grandes, a ordenação por intercalação, com seu tempo de execução q(n lg n), supera a ordenação por inserção, cujo tempo de execução é q(n²), no pior caso.

Convencionalmente, é possível reescrever a solução da forma abaixo, considerando que c é a constante que representa o tempo exigido para resolver um problema de tamanho 1, como também o tempo por elemento do arranjo para as etapas de dividir e combinar.

Para ilustrar esse conceito, é possível expandir uma árvore representando a recorrência do algoritmo, conforme abaixo, onde o termo cn é a raiz (o custo no nível superior da recursão), e as duas sub-árvores da raiz são as duas recorrências menores T(n/2). O custo para cada um dos dois sub-nós no segundo nível de recursão é cn/2. Ao continuar a expandir cada nó na árvore, desmembra-se em suas partes constituintes como determina a recorrência, até os tamanhos de problemas se reduzirem a 1, cada qual com o custo c.

Em seguida, somam-se os custos através de cada nível da árvore: cn, depois c(n/2) + c(n/2) = cn, depois c(n/4) + c(n/4) + c(n/4) + c(n/4) = cn. Em geral, o nível i abaixo do topo tem 2ⁱ nós, cada qual contribuindo com um custo c(n/2ⁱ) de forma que o i-ésimo nível abaixo do topo tem custo total 2ⁱc(n/2ⁱ) = cn.

Exercícios (Livro Algoritmos Teoria e Prática – Thomas Cormen 2012):

1-     Ilustre a operação de ordenação por intercalação sobre o arranjo A = (3, 41, 52, 26, 38, 57, 9, 49).

2-     Reescreva o procedimento MERGE de modo que ele não utilize sentinelas e, em vez disso, se interrompa depois que o arranjo L ou R tiver todos os seus elementos copiados de volta para A, e então copie o restante do outro arranjo de volta em A.

Intercala(A, p, q, r)

n₁ ¬ q – p + 1

n₂ ¬ r – q

criar arranjos L[1.. n₁ ] e R[1.. n₂]

para i ¬ 1 até n₁ faça

            L[i] ¬ A[p + i ­– 1]

para j ¬ 1 até n₂ faça

            R[j] ¬ A[q + j]

i ¬ 1

j ¬ 1

k ¬ p

enquanto k <> i ou k <> j faça

            se L[i] ≤ R[j] então

                        A[k] ¬ L[i]

                        i ¬ i + 1

            senão

                        A[k] ¬ R[j]

                        j ¬ j + 1

            k ¬ k + 1

se k = i então

            para k até j faça

                        A[k] ¬ R[j]

                        k ¬ k + 1

senão

            para k   até i faça

                        A[k] ¬ L[i]

                        k ¬ k + 1

3-     A ordenação por inserção pode ser expressa sob a forma de um procedimento recursivo como a seguir. Para ordenar A[1 .. n], ordenamos recursivamente A[1 .. n – 1] e depois inserimos A[n] no arranjo ordenado A[1 .. n – 1]. Escreva uma recorrência para o tempo de execução dessa versão recursiva da ordenação por inserção.

AlgoritmoOrdenaçãoInsercaoRecursiva(A, j)

se j > 2 então

            AlgoritmoOrdenaçãoInsercaoRecursiva(A, j -1)

            chave ¬ A[j]

            i ¬ j -1

            enquanto A[i] > chave e i > 0 faça

                        A[i + 1] ¬ A[i]

                        i ¬ i -1

            A[i + 1] ¬ chave

4-     Voltando ao problema da pesquisa linear abaixo observe que, se a sequência A estiver ordenada, poderemos comparar o ponto médio da sequência com v e eliminar metade da sequência de consideração posterior. A pesquisa binária é um algoritmo que repete esse procedimento, dividindo ao meio o tamanho da porção restante da sequência a cada vez. Escreva pseudocódigo, sendo ele iterativo ou recursivo, para pesquisa binária. Demonstre que o tempo de execução do pior caso da pesquisa binária é q(lg n).

Entrada: Uma sequência de n números A = (a₁, a₂, ..., a_n) e um valor v.

Saída: Um índice i tal que v = A[i] ou o valor especial NIL, se v não aparecer em A.

PesquisaBinaria(A, v)

i ¬ NIL

inferior = 0

superior = comprimento(A) – 1

meio = 0

enquanto inferior ≤ superior faça

            meio = (inferior + superior)/2

            se v == A[meio]

                        i = A[meio]

            se v < A[meio]

                        superior = meio – 1

            senão

                        inferior = meio + 1

escreva(i)

5-     Observe que o loop while do procedimento INSERTION-SORT utiliza uma pesquisa linear para varrer (no sentido inverso) o subarranjo ordenado A[1 .. j – 1]. Podemos usar em vez disso uma pesquisa binária para melhorar o tempo de execução global do pior caso da ordenação por inserção para q(lg n)?

Não, pois a premissa para utilizar a pesquisa binária é que o vetor já esteja ordenado.

6-     Descreva um algoritmo de tempo q(lg n) que, dado um conjunto S de n inteiros e outro inteiro x, determine se existem ou não dois elementos em S cuja soma seja exatamente x.

Pesquisa(S, x)

existe ¬ falso

i ¬ 0

j ¬ 0

para i ¬ 0 ate comprimento[S] faça

enquanto existe <> falso faça

            se x = S[i] + S[j] então

                        existe = verdadeiro

                        j ¬ j + 1

escreva(existe)

7-     Embora a ordenação por intercalação funcione no tempo de pior caso q(n lg n) e a ordenação por inserção funcione no tempo de pior caso q(n²), os fatores constantes na ordenação por inserção a tornam mais rápida para n pequeno. Assim, faz sentido usar a ordenação por inserção dentro da ordenação por intercalação quando os subproblemas se tornam suficientemente pequenos. Considere uma modificação na ordenação por intercalação, na qual n/k sublistas de comprimento k são ordenadas usando-se a ordenação por inserção, e depois intercaladas com o uso do mecanismo padrão de intercalação, onde k é um valor a ser determinado.

OrdencacaoIntercalacao(A)

p ¬ 0

r ¬ comprimento[A]

q ¬ r/2

AlgoritmoOrdenaçãoInsercao (A, p, q)

AlgoritmoOrdenaçãoInsercao (A, q + 1, r)

Intercala(A, p, q, r)

. AlgoritmoOrdenaçãoInsercao(A, j, x)

para j ¬ 2 até x faça

            chave ¬ A[j]

            i ¬ j -1

            enquanto A[i] < chave e i > 0 faça

                        A[i + 1] ¬ A[i]

                        i ¬ i -1

            A[i + 1] ¬ chave

Intercala(A, p, q, r)

n₁ ¬ q – p + 1

n₂ ¬ r – q

criar arranjos L[1.. n₁ + 1] e R[1.. n₂ + 1]

para i ¬ 1 até n₁ faça

            L[i] ¬ A[p + i ­– 1]

para j ¬ 1 até n₂ faça

            R[j] ¬ A[q + j]

L[n₁ + 1] ¬ ∞

R[n₂ + 1] ¬ ∞

i ¬ 1

j ¬ 1

para k ¬ p até r faça

            se L[i] ≤ R[j] então

                        A[k] ¬ L[i]

                        i ¬ i + 1

            senão

                        A[k] ¬ R[j]

                        j ¬ j + 1

8-     Seja A' um valor que denota a saída de BUBBLESORT(A). Para provar que BUBBLESORT é correto, precisamos provar que ele termina e que ordena os valores, onde n = comprimento[A] . O que mais deve ser provado para mostrar que BUBBLESORT realmente realiza a ordenação? (Ordenação por flutuação)

29

41

2

1

i = 1     j = 4

29

41

1

2

i = 1     j = 3

29

1

41

2

i = 1     j = 2

1

29

41

2

i = 1     j = 1

1

29

41

2

i = 2     j = 4

1

29

2

41

i = 2     j = 3

1

2

29

41

i = 2     j = 2

1

2

29

41

i = 3     j = 4

1

2

29

41

i = 3     j = 3

1

2

29

41

i = 4     j = 4