Demonstre que os elementos de uma OLista estão em ordem estritamente crescente da esquerda para a direita. Ou seja, se
,
são elementos da lista, mostre que
(Use indução em
.)
Passo 1
O enunciado pede para mostrar que, em toda OList de tamanho
cujos elementos são
vale
O método será indução em
, 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
, a OList tem
elemento, digamos
. 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
, toda OList de tamanho
seja estritamente crescente:
Passo 4
(Construção recursiva) Uma OList de tamanho
é obtida assim:
- dividem-se os elementos em duas sublistas de tamanho
, respectivamente nas posições ímpares e pares; - aplica-se recursivamente OList a cada sublista;
- intercala-se as duas sublistas numa lista
de comprimento fazendo
- por fim, percorre-se
e, para todo , compara-se e , trocando-os se estiverem fora de ordem.
Passo 5
(Pelas sublistas) Pelas hipóteses de indução, cada sublista de tamanho
já está estritamente crescente antes da intercalação.
Passo 6
(Passada final de comparadores) A etapa final compara todos os pares adjacentes
. Sempre que
, faz-se a troca, garantindo que ao fim desta passada queda valha
Logo a lista inteira
fica estritamente crescente.
Resposta
Por indução em
, concluímos que qualquer OList de comprimento
satisfaz