Demonstre que os elementos de uma OLista estão em ordem estritamente crescente da esquerda para a direita. Ou seja, se x1, x2, x3, ldots, x2 p são elementos da lista, mostre que
x1<x2<x3<ldots<x2^p
(Use indução em p.)

Passo 1

O enunciado pede para mostrar que, em toda OList de tamanho 2^p cujos elementos são
x1,x2,dots,x2^p,
vale
x1<x2<dots<x2^p
O método será indução em p, usando a definição recursiva de OList e o fato de que, ao final do merge ímpar-par, há uma passada de comparadores adjacentes que corrige qualquer inversão entre vizinhos.

Passo 2

(Caso base) Para p=0, a OList tem 2^0=1 elemento, digamos [x1]. Não há pares consecutivos a verificar, logo a sequência é trivialmente estritamente crescente.

Passo 3

(Hipótese de indução) Suponha que, para algum k>=0, toda OList de tamanho 2^k seja estritamente crescente:
y1<y2<dots<y2^k

Passo 4

(Construção recursiva) Uma OList de tamanho 2^k+1 é obtida assim:
  1. dividem-se os elementos em duas sublistas de tamanho 2^k, respectivamente nas posições ímpares e pares;
  2. aplica-se recursivamente OList a cada sublista;
  3. intercala-se as duas sublistas numa lista X de comprimento 2^k+1 fazendo
X2i-1=(i-ésimo da sublista ímpar), X2i=(i-ésimo da sublista par); éíé
  1. por fim, percorre-se X e, para todo j=1,dots,2^k+1-1, compara-se Xj e Xj+1, trocando-os se estiverem fora de ordem.

Passo 5

(Pelas sublistas) Pelas hipóteses de indução, cada sublista de tamanho 2^k já está estritamente crescente antes da intercalação.

Passo 6

(Passada final de comparadores) A etapa final compara todos os pares adjacentes (Xj,Xj+1). Sempre que Xj>Xj+1, faz-se a troca, garantindo que ao fim desta passada queda valha
Xj<Xj+1 forall,j=1,dots,2^k+1-1
Logo a lista inteira X fica estritamente crescente.

Resposta

Por indução em p, concluímos que qualquer OList de comprimento 2^p satisfaz
x1<x2<dots<x2^p

Exercícios de Livros Relacionados