4
A ordenação de dados em memória é uma das operações mais comuns executadas por algoritmos computacionais. Embora existam diferentes estratégias para esse tipo de operação, poucas delas conseguem alcançar um tempo computacional linear.
Algoritmo Ordenação Linear Simplificada
Entrada: Um vetor A de n inteiros cujos valores são 1 ou 2.
Saída: Vetor A com os valores ordenados de forma não-decrescente
1. Defina k ← 0
2. para i ← 1 até n faça
3. se A[ i ] = 1, então k ← k + 1
4. para i ← 1 até k faça
5. A[ i ] ← 1
6. para i ← k + 1 até n faça
7. A[ i ] ← 2
8. retorna A
Nesse contexto, considerando o algoritmo apresentado, analise as afirmativas a seguir e assinale V para a(s) verdadeira(s) e F para a(s) falsa(s).
I. ( ) Para um vetor A contendo m posições com valor 1 e n posições com valor 2, o algoritmo realiza m + n operações de atribuições ao vetor A.
II. ( ) O algoritmo é estável.
III. ( ) Para qualquer sequência de valores aceitos pelo algoritmo, as primeiras posições do vetor A serão ocupadas pelo valor 2.
IV. ( ) O maior valor possível para k é n.
Agora, assinale a alternativa que apresenta a sequência correta:
a) V, V, F, F.
b) V, V, F, V.
c) F, F, V, V.
d) F, V, F, V.
e) V, F, V, F.
Soluções para a tarefa
Resposta:
b) V, V, F, V.
Explicação:
É necessário verificar o funcionamento do algoritmo para as diferentes sequências de valores 1 e 2 e verificar como o vetor de saída é construído
Resposta:
V,V,F,V
Explicação:
Resposta certa. Para uma entrada composta de m valores 1 e n valores 2, o primeiro laço do algoritmo vai finalizar com o valor de k = m e, portanto, o segundo laço vai realizar m atribuições ao vetor A. O último laço realiza tantas atribuições ao vetor A quanto o número de valores 2 presentes na entrada, ou seja, n atribuições. Portanto, serão realizadas m + n atribuições a A. Como os elementos com mesmo valor não têm sua ordem alterada no vetor de saída, o algoritmo é dito estável. O segundo laço do algoritmo é responsável pela atribuição das primeiras posições do vetor com valor 1. Finalmente, como o valor k é incrementado para cada valor 1 encontrado no vetor, o seu maior valor possível acontece quando a entrada é composta de apenas valores 1. Neste caso, k = n.