Escreva o algoritmo que coloca os primeiros quatro termos de uma lista de comprimento arbitrário em ordem crescente. Mostre que este algoritmo tem complexidade temporal O(1) em termos do número de comparações usadas.

Passo 1

O enunciado pede um algoritmo que receba uma lista arbitrária e coloque em ordem crescente apenas os quatro primeiros elementos, sem se preocupar com o resto da lista. O conteúdo é projeto de algoritmo e análise de complexidade em número de comparações.

Passo 2

Uma forma simples é usar selection sort restrito aos índices de 1 a 4. Em pseudocódigo:
para i de 1 até 3 faça
 para j de i\(+1\) até 4 faça
 se A[i] > A[j] então
 trocar A[i] e A[j]
Isso garante que, ao final, A[1] ≤ A[2] ≤ A[3] ≤ A[4].

Passo 3

Contamos quantas comparações A[i] > A[j] são feitas:
– Para i =1: j percorre 2, 3,4\Rightarrow 3 comparações
– Para i =2: j percorre 3,4\Rightarrow 2 comparações
– Para i =3: j percorre 4\Rightarrow 1 comparação
Total =3+2+1=6 comparações.

Passo 4

Como o número de comparações é sempre 6, independentemente do tamanho da lista, o algoritmo usa um número de operações de comparação constante. Portanto, em notação assintótica, o tempo gasto em comparações é O(1).

Resposta

Pseudocódigo:
para i de 1 até 3 faça
 para j de i\(+1\) até 4 faça
 se A[i] > A[j] então
 trocar A[i] e A[j]
Número de comparações =6\Rightarrow complexidade em comparações é O(1).