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
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
– Para i : j percorre 2,
comparações
– Para i : j percorre
comparações
– Para i : j percorre
comparação
Total comparações.
A[i] > A[j]
são feitas:– Para i
– Para i
– Para i
Total
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
complexidade em comparações é O(1).