MAC0338/lista4.md

1. Escreva uma função que recebe um vetor com n letras A’s e B’s e, por meio de trocas, move todos os A’s para o início do vetor. Sua função deve consumir tempo $O(n)$.

A função vai receber o vetor C que possi n elementos.

OrdenaAB(C, n)
1.    dir <- 1
2.    esq <- n
3.    enquanto dir < esq
4.        se C[dir] igual 'A'
5.            dir <- dir + 1
6         senão se C[esq] igual 'B'
7.            esq <- esq + 1
8.        senão
9.            C[esq] <-> C[dir]
10.           dir <- dir + 1
11.           esq <- esq + 1

Note que em cada interação obrigatoriamente dir vai ser subtraído ou esq vai ser adicionado. Com isso o número máximo de vezes que a linha 3 pode ser executada é $O(n)$. Note que as linhas posteriores a essa vão ser executadas menos vezes que essa, portanto o código continuará $O(n)$.

Escreva uma função que rearranje um vetor v[p..r] de inteiros de modo que tenhamos v[p..j−1] ≤ 0 e v[j..r] > 0 para algum j em p..r+1. Faz sentido exigir que j esteja em p..r? Procure fazer uma função rápida que não use vetor auxiliar. Repita o exercício depois de trocar v[j..r] > 0 por v[j..r] ≥ 0. Faz sentido exigir que v[j] seja 0?

OrdenaZero(v, n)
1.    dir <- 1
2.    esq <- n
3.    enquanto dir < esq
4.        se C[dir] <= 0
5.            dir <- dir + 1
6         senão se C[esq] > 0
7.            esq <- esq + 1
8.        senão
9.            C[esq] <-> C[dir]
10.           dir <- dir + 1
11.           esq <- esq + 1

Não faz muito sentido exigir que j esteja em p..r, pois pense no caso em que temo o vetor completo de números negativas, nesse caso se j estiver em p..r, algum desses elemntos será > 0, criando uma contradição.

Para trocarmos v[j..r] > 0 por v[j..r] ≥ 0 basta alterar a linha 6 do programa. No entanto não faz sentido exigir que v[j] seja 0, pois dessa forma nunca saberíamos em qual parte do vetor encontramos os zeros.