a) Bubble Sort
b) Select Sort
c) Shell Sort
d) Busca Sequencial;
e) Quick Sort;
Conforme vimos em aula, a Busca Sequencial não é um algoritmo de ordenação! Na verdade, ele é um método de pesquisa sobre estruturas de dados.
Gabarito: D
Conforme vimos em aula, está perfeito! Sendo um algoritmo do tipo Dividir Para Conquistar, ele reparte o conjunto de dados em conjuntos menores, que são ordenados independentemente e depois combinados em uma solução maior.
Gabarito: C
Inicialmente, insere-se os elementos da lista em um heap.
Em seguida, fazemos sucessivas remoções do
menor elemento do heap, colocando os elementos removidos do heap de volta na lista – a lista estará então em ordem crescente.
O heapsort é um algoritmo de ordenação em que a sua estrutura auxiliar de armazenamento fora do arranjo de entrada é constante durante toda a sua execução.
Essa questão é polêmica. O arranjo tem tamanho constante, mas a quantidade de elementos é variável.
Diferente de outros algoritmos de ordenação que tem uma estrutura auxiliar de tamanho variável (assim como seus elementos), o Heap Sort tem uma estrutura auxiliar de tamanho fixo (porém a quantidade de elementos é variável).
Como é dito por Neil Dale: “A heapsort is just as efficient in terms of space; only one array is used to store the data. The heap sort requires only constante extra space”. No entanto, a questão foi dada como correta!
Gabarito: C
Alguns autores consideram a divisão em três subconjuntos, sendo o terceiro contendo valores iguais ao pivô.
O Melhor Caso ocorre quando o conjunto é dividido em subconjuntos de mesmo tamanho;
o Pior Caso ocorre quando o pivô corresponde a um dos extremos (menor ou maior valor). Alguns o consideram um algoritmo frágil e não-estável, com baixa tolerância a erros.
Conforme vimos em aula, a questão se refere ao pior caso!
Gabarito: E
A estabilidade de um método de ordenação é importante quando o conjunto de dados já está parcialmente ordenado.
Na imagem acima, foi colocado um sinal de aspas simples e duplas apenas para diferenciá-los, mas trata-se do mesmo número.
Um algoritmo estável ordena todo o restante e não perde tempo trocando as posições de elementos que possuam chaves idênticas.
Já um algoritmo instável ordena todos os elementos, inclusive aqueles que possuem chaves idênticas (sob algum outro critério).
Conforme vimos em aula, a estabilidade é irrelevante com dados parcialmente ordenados ou não!
A estabilidade é importante quando se deseja ordenar um conjunto de dados por mais de um critério (Ex: primeiro pelas chaves e segundo por índices). Se esse não for o caso (e a questão não disse que era!), a estabilidade “não fede nem cheira”. O fato de os dados estarem parcialmente ordenados não fará diferença em termos de ordenação – ambos serão ordenados da mesma maneira.
Gabarito: E
A classificação interna por inserção é um método que realiza a ordenação de um vetor por meio da inserção de cada elemento em sua posição correta dentro de um subvetor classificado.
Conforme vimos em aula, trata-se do InsertionSort!
Gabarito: C
a) SelectionSort e InsertionSort.
b) MergeSort e BubbleSort.
c) QuickSort e SelectionSort.
d) BubbleSort e QuickSort.
e) InsertionSort e MergeSort.
Gabarito: D
O tempo de pior caso do algoritmo QuickSort é de ordem menor que o tempo médio do algoritmo Bubblesort.
Tempo: O(n) < O(n log n) < O(n²)
Métodos Estáveis: BIM - Bub, Ins e Mer
São iguais: O(n²).
Gabarito: E
O tempo médio do QuickSort é O(nlog2n), pois ele usa como estrutura básica uma árvore de prioridades.
Tempo: O(n) < O(n log n) < O(n²)
Métodos Estáveis: BIM - Bub, Ins e Mer
Conforme vimos em aula, de fato, ele tem tempo médio O(n log n), mas ele usa como estrutura básica uma lista ou um vetor!
Gabarito: E
O tempo médio do QuickSort é de ordem
igual ao tempo médio do MergeSort.
Tempo: O(n) < O(n log n) < O(n²)
Métodos Estáveis: BIM - Bub, Ins e Mer
Conforme vimos em aula, ambos têm tempo O(n log n).
Gabarito: C
Em uma reunião de análise de desempenho de um sistema WEB, um programador apontou corretamente que a complexidade de tempo do algoritmo bubblesort, no pior caso, é:
a) O(1)
b) O(log n)
c) O(n)
d) O(n log n)
e) O(n2)
Tempo: O(n) < O(n log n) < O(n²)
Métodos Estáveis: BIM - Bub, Ins e Mer
Conforme vimos em aula, trata-se de O(n²)!
Gabarito: E
Assinale a opção que apresenta somente algoritmos que possuem complexidade assintótica quando f(n) = O(n log n).
a) HeapSort e BubbleSort
b) QuickSort e InsertionSort
c) MergeSort e BubbleSort
d) InsertionSort
e) HeapSort, QuickSort e MergeSort
Tempo: O(n) < O(n log n) < O(n²)
Métodos Estáveis: BIM - Bub, Ins e Mer
Conforme vimos em aula, trata-se da última opção. Vejam que ele não utilizou, nessa questão, o Pior Caso.
Gabarito: E
a) Selectionsort (seleção)
b) Insertionsort (inserção)
c) Merge sort
d) Quicksort
e) Heapsort
Tempo: O(n) < O(n log n) < O(n²)
Métodos Estáveis: BIM - Bub, Ins e Mer
Conforme vimos em aula, trata-se da segunda opção.
Gabarito: B
Uma fábrica de software foi contratada para desenvolver um produto de análise de riscos. Em determinada funcionalidade desse software, é necessário realizar a ordenação de um conjunto formado por muitos números inteiros.
Que algoritmo de ordenação oferece melhor complexidade de tempo (Big O notation) no pior caso?
a) Merge sort
b) Insertion sort
c) Bubble sort
d) Quick sort
e) Selection sort
Tempo: O(n) < O(n log n) < O(n²)
Métodos Estáveis: BIM - Bub, Ins e Mer
Conforme vimos em aula, trata-se da primeira opção!
Gabarito: A
Alguns métodos eficientes como shellsort ou quicksort não são estáveis, enquanto alguns métodos pouco eficientes, como o método da bolha, são estáveis.
Tempo: O(n) < O(n log n) < O(n²)
Métodos Estáveis: BIM - Bub, Ins e Mer
Métodos Instáveis: SelectionSort, QuickSort,
HeapSort e ShellSort.
Portanto, item perfeito!
Gabarito: C
Tempo: O(n) < O(n log n) < O(n²)
Métodos Estáveis: BIM - Bub, Ins e Mer
Não há correlação direta entre complexidade de custo e complexidade temporal, logo eu não posso usar a função de um para calcular o outro.
Gabarito: E
Tempo: O(n) < O(n log n) < O(n²)
Métodos Estáveis: BIM - Bub, Ins e Mer
QuickSort é instável e não possui complexidade temporal linear!
Gabarito: E
No método de ordenamento denominado shellsort, as comparações e as trocas são feitas conforme determinada distância entre dois elementos, de modo que, uma distância igual a 6 seria a comparação entre o primeiro elemento e o sétimo, ou entre o segundo elemento e o oitavo, e assim sucessivamente, repetindo-se esse processo até que as últimas
comparações e trocas tenham sido efetuadas e a distância tenha diminuído até chegar a 1.
É o algoritmo mais eficiente dentre os de ordem quadrática. Nesse método, as comparações e as trocas são feitas conforme determinada distância (gap) entre dois elementos, de modo que, se gap = 6, há comparação entre o 1º e 7º elementos ou entre o 2º e 8º elementos e assim sucessivamente, repetindo até que as últimas
comparações e trocas tenham sido efetuadas e o gap tenha chegado a 1.
Conforme vimos em aula, a questão descreveu perfeitamente o mecanismo de ordenação do Shellsort.
Gabarito: C
a) Utiliza ordenação por árvore de decisão, ao invés de ordenação por comparação.
b) A estrutura de dados que utiliza, chamada heap, pode ser interpretada como uma árvore binária.
c) Seu desempenho de pior caso é pior do que o do algoritmo quicksort.
d) Seu desempenho de pior caso é o mesmo da ordenação por inserção.
e) Seu desempenho de pior caso é menor do que o da ordenação por intercalação.
Tempo: O(n) < O(n log n) < O(n²)
Métodos Estáveis: BIM - Bub, Ins e Mer
(a) Utiliza ordenação por seleção;
(b) Perfeito;
(c) Não, é melhor que o QuickSort;
(d) Não, é melhor que o InsertionSort;
(e) Não, é idêntico ao MergeSort.
Gabarito: B
Com relação aos algoritmos quicksort e mergesort, o tempo de execução para o:
a) pior caso do quicksort é (n lg n).
b) pior caso do mergesort é (n2).
c) pior caso do mergesort é (n lg n).
d) caso médio do mergesort é O(lg n).
e) caso médio do quicksort é O(n2).
Tempo: O(n) < O(n log n) < O(n²)
Métodos Estáveis: BIM - Bub, Ins e Mer
Conforme vimos em aula, trata-se da terceira opção. Gabarito: C
O algoritmo quicksort, que divide uma instrução em quatro blocos diferentes de busca, é um exemplo de estrutura de ordenação de dados.
Conforme vimos em aula, são dois blocos diferentes de busca.
Gabarito: E
No algoritmo de ordenação denominado quicksort, escolhe-se um ponto de referência, denominado pivô, e separam-se os elementos em dois grupos: à esquerda, ficam os elementos menores que o pivô, e à direita ficam os maiores. Repete-se esse processo para os grupos de elementos formados (esquerda e direita) até que todos os elementos estejam ordenados.
Esse algoritmo divide um conjunto de itens em conjuntos menores, que são ordenados de forma independente, e depois os resultados são combinados para produzir a solução de ordenação do conjunto maior.
Trata-se, portanto, de um algoritmo do tipo Divisão-e-Conquista, i.e., repartindo os dados em subgrupos, dependendo de um elemento chamado pivô.
Neste método, a lista é dividida em parte esquerda e parte direita, sendo que os elementos da parte esquerda são todos menores que os elementos da parte direita. Essa fase do processo é chamada de
partição.
Em seguida, as duas partes são ordenadas recursivamente (usando o próprio QuickSort). A lista está, portanto, ordenada corretamente!
Conforme vimos em aula, é exatamente assim!
Gabarito: C
Entre os algoritmos de ordenação e pesquisa bubble sort, quicksort e heapsort, o quicksort é considerado o mais eficiente, pois se caracteriza como um algoritmo de dividir-para-conquistar, utilizando operações de particionamento.
Conforme vimos em aula, o HeapSort é o mais eficiente no pior caso!
Gabarito: E
No método Quicksort, o pivô é responsável pelo número de partições em que o vetor é dividido. Como o pivô não pode ser um elemento que esteja repetido no vetor, o Quicksort não funciona quando há elementos repetidos.
O pivô não é responsável pelo número de partições em que o vetor é dividido. Ademais, ele pode sim ser um elemento que esteja repetido no vetor!
Gabarito: E