[Exercícios] Algoritmos de ordenação
1) Quais destes algoritmos de ordenação têm a classe de complexidade
assintótica, no pior caso, em O(n.log n) ?
(A) QuickSort, MergeSort, e HeapSort
(B) QuickSort e SelectionSort
(C) MergeSort e HeapSort
(D) QuickSort e BubbleSort
(E) QuickSort, MergeSort e SelectionSort
Resposta correta (C)
Nesse exercício você precisa lembrar qual é complexidade dos algoritmos de ordenação no pior caso. A wikipedia pode te ajudar
Facilitando a sua consulta. Veja artigos completos sobre o quicksort, mergesort e heapsort.
Observando que o quicksort no seu pior caso tem complexidade O(n²), podemos descartar todas as alternativas exceto a letra (c).
2) Analise o seguinte programa descrito na forma de pseudocódigo:
1. algoritmo
2. declare X[10], n, i, aux, flag numérico
3. para i ← 1 até 10 faça
4. leia X[i]
5. n ← 1
6. flag ← 1
7. enquanto (n ≤ 10 E flag = 1) faça
8. inicio
9. flag ← 0
10. para i ← 1 até 9 faça
11. inicio
12. se (X[i] < X[i+1]) então
13. inicio
14. flag ← 1
15. aux ← X[i]
16. X[i] ← X[i+1]
17. X[i+1] ← aux
18. fim_se
19. fim_para
20. n ← n + 1
21. fim_enquanto
22. para i ← 1 até 10 faça
23. escreva X[i]
24. fim_algoritmo
O programa escrito acima realiza a ordenação decrescente de um vetor de
números inteiros. O algoritmo implementado é de:
(A) ordenação rápida.
(B) ordenação por troca.
(C) ordenação por seleção.
(D) ordenação por inserção.
(E) ordenação por intercalação
Nesse exercício você precisa compreender como funciona o algoritmo de
troca (bubble sort). Nas linhas 12 até 17, percebemos que existe uma
operação de troca dos números e ela se repete até o fim do vetor. Saiba mais clicando aqui. Veja a seguir um exemplo visual desse algoritmo:
MERGESORT(V, i, j)
Se (i<j) então
m = (i+j)/2;
MERGESORT(v, i, m);
MERGESORT(v, m+1, j);
MESCLAR(v, i, m, j);
Fim;
a) O(log n)
b) O(n log n)
c) O(n2)
d) O(n3)
e) O(2n)
Resposta correta: Alternativa (B)
Como o algoritmo MergeSort usa a recursividade, há um alto consumo de memória e tempo de execução, tornando esta técnica não muito eficiente em alguns casos. Sua complexidade assintótica é O(n log n). Veja um exemplo visual do funcionamento desse método:
Veja uma explicação mais detalhada sobre a complexidade desse método clicando aqui.
4) Sobre a escolha adequada para um algoritmo de ordenação, considere as
afirmativas a seguir.
I. Quando os cenários de pior caso for a preocupação, o algoritmo ideal é o
Heap Sort.
II. Quando o vetor apresenta a maioria dos elementos ordenados, o algoritmo
ideal é o Insertion Sort.
III. Quando o interesse for um bom resultado para o médio caso, o algoritmo
ideal é o Quick Sort.
IV. Quando o interesse é o melhor caso e o pior caso de mesma complexidade,
o algoritmo ideal é o
Bubble Sort.
Assinale a alternativa correta:
a) Somente as afirmativas I e II são corretas.
b) Somente as afirmativas I e IV são corretas.
c) Somente as afirmativas III e IV são corretas.
d) Somente as afirmativas I, II e III são corretas.
e) Somente as afirmativas II, III e IV são corretas.
Resposta correta: Alternativa (D)
I) Para compreender sobre a complexidade dos algoritmos é preciso analisar sobre diversos aspectos, incluindo se os elementos estão ordenados. Veja uma tabela comparativa da complexidade de alguns algoritmos de ordenação:
O heapsort mencionado na opção I possui complexidade O log (n) em todas as situações (melhor, medio, pior caso)
O insertion sort possui seu melhor caso quando o array está ordenado. Veja uma referência aqui.
O quicksort possui em caso médio e pior caso a complexidade O log (n). Veja uma referência aqui.
Um tutorial muito legal você pode acessar aqui.
5) Seja V um vetor de n inteiros não negativos, tal que o maior valor
encontrado em V é m > 0.
Com relação à ordenação de V , considere as afirmativas a seguir.
I. O tempo de execução dos algoritmos Quicksort e Mergesort para ordenar V
é
(n lg n) para qualquer
valor de m.
II. Quando m = O(n), é possível ordenar V em tempo de execução O(n) no pior
caso.
III. O tempo de execução de pior caso do Quicksort para ordenar V é O(n lg
n) quando m = O(n).
IV. Para instâncias onde n = O(m), o algoritmo Countingsort é mais
eficiente que o Mergesort, em função
de n.
Assinale a alternativa correta.
a) Somente as afirmativas I e II são corretas.
b) Somente as afirmativas I e IV são corretas.
c) Somente as afirmativas III e IV são corretas.
d) Somente as afirmativas I, II e III são corretas.
e) Somente as afirmativas II, III e IV são corretas.
Para responder às questões 6 e 7, considere a seguinte variante do
algoritmo quicksort para ordenação de uma lista de inteiros x1, . . . ,
xn:
Algoritmo QS(x1,....xn)
Entrada: x1....xn inteiros
Saída: x1,....xn inteiros
Se n = 2 e x1 > x2, permutar x1 com x2.
Se n <= 2 retornar
i ← 2, j ← n,
Enquanto i < j,
Enquanto x1 >= xi e i < n + 1 incrementar i.
Enquanto x1 < xj, decrementar j.
Se i < j, permutar xi com xj.
Permutar x1 com xj.
QS(x1,....xj-1)
QS(xj+1, ... xn)
6) Seja Φ(x1, ..., xn) o número total de permutações de dois elementos durante a
execução do algoritmo
QS, inclusive durante as chamadas recursivas. Seja Φmax(n) o maior valor de Φ(x1, . . . , xn) para todas as listas possíveis de comprimento n.
Sabendo que
a) Φmax(n) = n − 1.
b) Φmax(n) está em o(n).
c) Φmax(n) está em O(n log(n)), mas não em O(n).
d) Φmax(n) está em O(n2), mas não em O(n log n).
e) Φmax(n) > 2n.
7) Assinale a alternativa correta.
a) O tempo de execução do algoritmo QS, no pior caso, para entradas de
tamanho n, é de Φ(n log2(n)).
b) O tempo de execução total do algoritmo para a entrada x1, . . . , xn é
sempre de O(Φ(x1, . . . , xn)).
c) O tempo de execução total do algoritmo QS para a entrada x1, . . . , xn
não é proporcional à soma das vezes que cada uma das linhas foi
executada.
d) O tempo de execução do algoritmo QS, no pior caso, para entradas de
tamanho n, é de Φ(n2).
e) O número total de comparações do algoritmo QS, incluindo as chamadas
recursivas, é de O(Φmax(n)) no pior caso.
8) Relacione as colunas
(I) Inserção
(II) Seleção
(III) QuickSort
(IV) ShellSort
(V) MergeSort (ou ordenação
por fusão)
(A) Encontra o menor elemento e o troca com a primeira posição, depois o
segundo menor com a segunda posição e assim sucessivamente (n-1 vezes).
(B) As comparações e trocas são feitas baseadas em uma distância
determinada (por exemplo: distância 4, onde o primeiro seria comparado com
o quinto elemento, o segundo com o sexto, e assim sucessivamente),
depois a distância é reduzida. Este processo se repete até que a distância seja 1
e as últimas comparações e trocas sejam efetuadas.
(C) A partir do segundo elemento, este deve ser colocado na sua posição
correspondente
(entre os elementos já analisados, como ao se organizarem as cartas de baralho na mão do jogador). Repete-se o procedimento até
o último elemento.
(D) Escolhe-se um ponto de referência (pivô) e separam-se os elementos em
2 partes: à esquerda, ficam os elementos menores que o pivô, e à direita,
os maiores. Repete-se este processo para os grupos de elementos
formados (esquerda e direita) até que todos os elementos estejam ordenados.
(E) Divide-se o grupo de elementos ao meio, repete-se a divisão para cada
um dos subgrupos, até que cada subgrupo tenha apenas 1 elemento.
Nesse ponto, faz-se o reagrupamento dos subgrupos comparando os
elementos e trocando, se necessário, para que eles fiquem ordenados. Repete-se
este procedimento até restar um só grupo de elementos.
Assinale a alternativa que contém a associação correta.
a) I-A, II-D, III-B, IV-C, V-E.
b) I-B, II-A, III-C, IV-E, V-D.
c) I-B, II-A, III-E, IV-D, V-C.
d) I-C, II-A, III-D, IV-B, V-E.
e) I-D, II-E, III-B, IV-A, V-C.
9) Considere o problema de ordenação onde os vetores a serem ordenados, de
tamanho n > 0, possuem [n/2] valores iguais a um número real x e [n=2]
valores iguais a um outro número real y. Considere que os números reais x e
y são conhecidos e fixos, porém estão distribuídos aleatoriamente no vetor a
ser ordenado.
Neste caso, é correto afirmar:
a) Podemos ordenar estes vetores a um custo O(n).
b) No caso médio, o Quicksort será o algoritmo mais eficiente para este
problema, com um custo O(n log n).
c) O algoritmo de ordenação por inserção sempre opera no melhor caso com um
custo O(n).
d) O limite inferior para esta classe de problema é Ω(n²) .
e) O limite inferior para esta classe de problema é Ω(n logn).
10) Os fragmentos de programas abaixo, enumerados 1, 2 e 3, são
implementações para o
problema de ordenação usando o algoritmo quicksort.
Programa 1
quicksort([],[]).
quicksort([Head|Tail],Sorted) :-
partition(Head, Tail, Left, Right), quicksort(Left,SortedL),
quicksort(Right,SortedR),
append(SortedL), [Head|Tail], [Head|Left], Right) :-
partition (Pivot, [], [] ,[]).
partition (Pivot, [Head|Tail],[Head|Left],Right) :-
Head <= Pivot, partition(Pivot,Tail,Left,Right).
Partition (Pivot, [Head|Tail],Left,Right).
Head > Pivot, partition(Pivot, Tail, Left, Right).
append([], List, List).
append ([Head|List1],List2,[Head|List3]) :-
append(List1,List2,List3).
Programa 2
quicksort [] = []
quicksort (head:tail) = let pivot = head
left = [x|x <- tail,x < pivot]
right = [x|x <- tail, x >= pivot]
in quicksort left ++ [pivot] ++ quicksort right
Programa 3
void quickSort( int a[], int l, int r){
int j;
if (l < r){
j = partition (a, l, r);
quickSort (a, l, j-1);
quickSort( a, j+1, r);
}
}
int partition( int a[], int l, int r){
int pivot, i, j, t;
pivot = a[l], i= l; j = r+1;
while(i < j) {
do ++i; while(a[i] <= pivot && i <= r);
do --j; while (a[j] < pivot);
if( i < j ) {
t = a[i]; a[i] = a[j]; a[j] = t;
}
}
t = a[l]; a[l] = a[j]; a[j] = t;
return j;
}
Assinale a alternativa que enumera os paradigmas das linguagens com as
quais os
programas 1, 2 e 3 foram respectivamente implementados.
A) Lógico, imperativo e funcional
B) Imperativo, funcional e lógico
C) Funcional, lógico e imperativo
D) Lógico, funcional e imperativo
E) Funcional, funcional e imperativo
Respostas:
1) C
2) B
3) B
4) D
5) A
6) C
7) D
8) D
9) A
10) D
Post a Comment