Correlacione os algoritmos internos de ordenação de listas d...
Correlacione os algoritmos internos de ordenação de listas da coluna à esquerda com sua descrição, na coluna à direita.
1) Bubblesort.
2) Ordenação por Seleção
3) Ordenação por Inserção
4) Shellsort
5) Quicksort
( ) Escolhe-se um pivot e particiona-se a lista em duas sublistas: uma com os elementos menores que ele e outra com os maiores, que, ao serem ordenadas e combinadas com o pivot, geram uma lista ordenada. O processo é aplicado às partições para ordená-las. Embora tenha uma complexidade de pior caso de O(n2 ), no caso médio é de O(n log n).
( ) Encontra-se o menor item do vetor. Troca-se com o item da primeira posição do vetor.
Repetem-se essas duas operações com os n − 1 itens restantes, depois com os n − 2
itens, até que reste apenas um elemento.
( ) Método preferido dos jogadores de cartas. A cada momento existem duas partes na lista:
uma ordenada (destino) e outra não ordenada (fonte). Inicialmente a lista destino tem
apenas o primeiro elemento, e a fonte os demais elementos. Em cada passo a partir de
i=2, seleciona-se o i-ésimo item da lista fonte. Deve-se colocá-lo no lugar apropriado na
lista destino, de acordo com o critério de ordenação.
( ) É uma extensão de um outro algoritmo de ordenação conhecido e permite trocas de elementos distantes um do outro, não necessariamente adjacentes. Os itens separados de h posições são rearranjados. Todo h-ésimo item leva a uma lista ordenada. Tal lista é dita estar h-ordenada.
( ) Varre-se a lista trocando-se de posição os elementos adjacentes fora de ordem. Varre-se a lista até que não haja mais trocas e, neste caso, a lista está ordenada.
A sequência correta, de cima para baixo, é:
Gabarito comentado
Confira o gabarito comentado por um dos nossos professores
Alternativa correta: B
Vamos entender o tema da questão. Ela aborda os algoritmos de ordenação, que são fundamentais em competências de programação e frequentemente cobrados em concursos públicos. Para responder corretamente, é necessário conhecer as características e o funcionamento de cada algoritmo de ordenação mencionado: Bubblesort, Ordenação por Seleção, Ordenação por Inserção, Shellsort e Quicksort.
Agora vou explicar cada algoritmo de acordo com a descrição fornecida:
(5) Quicksort: A descrição fala sobre escolher um pivot e particionar a lista em duas sublistas, uma com os elementos menores e outra com os maiores que o pivot. O processo é recursivo e tem complexidade de pior caso O(n²), mas no caso médio é O(n log n). Isso se refere claramente ao Quicksort.
(2) Ordenação por Seleção: A descrição menciona encontrar o menor item e trocá-lo com o primeiro, repetindo o processo com os itens restantes. Este é o algoritmo de Ordenação por Seleção, também conhecido como Selection Sort.
(3) Ordenação por Inserção: Esta descrição é bem ilustrativa ao mencionar o método dos jogadores de cartas, onde a lista é dividida em uma parte ordenada e outra não ordenada. A cada iteração, o próximo item da parte não ordenada é inserido na posição correta na parte ordenada. Este é o algoritmo de Inserção.
(4) Shellsort: A descrição fala sobre uma extensão de um outro algoritmo que permite trocas não necessariamente adjacentes, utilizando um conceito de h-ordenação. Trata-se claramente do Shellsort.
(1) Bubblesort: A última descrição menciona varrer a lista trocando elementos adjacentes que estão fora de ordem, repetindo o processo até que não haja mais trocas. Este é o algoritmo Bubblesort.
Com base nas descrições acima, a sequência correta é associada da seguinte forma:
5) Quicksort, 2) Ordenação por Seleção, 3) Ordenação por Inserção, 4) Shellsort, 1) Bubblesort
Portanto, a alternativa correta é a Alternativa B.
Agora, vamos analisar as alternativas incorretas:
Alternativa A: A sequência 1, 2, 3, 4, 5 está incorreta porque associa de forma errada as descrições aos algoritmos.
Alternativa C: A sequência 1, 4, 5, 3, 2 também não está correta, pois não corresponde às descrições dos algoritmos.
Alternativa D: A sequência 5, 4, 2, 3, 1 apresenta outra ordem incorreta, sem corresponder às características dos algoritmos.
Alternativa E: A sequência 1, 3, 2, 4, 5 está errada, pois a ordem dos algoritmos não corresponde às descrições fornecidas.
Gostou do comentário? Deixe sua avaliação aqui embaixo!
Clique para visualizar este gabarito
Visualize o gabarito desta questão clicando no botão abaixo
Comentários
Veja os comentários dos nossos alunos
Falou em pivot: quick sort
menor elemento, primeiro n-1 depois n-2: selection sort
preferido de jogadores de cartas: insertion sort
elementos distantes: gap do shell sort
varre trocando adjacentes: bubble sort
Excelente questão, serve até como revisão.
b-
tabela
https://d2m498l008ebpa.cloudfront.net/2016/12/compara--o-entre-os-m-todos-de-ordena--o.png
Força Guerreiro!!!!!!
Clique para visualizar este comentário
Visualize os comentários desta questão clicando no botão abaixo
Conheça nossos planos