Métodos de Ordenação Flashcards
A complexidade do Bubble Sort no melhor caso é:
a) O(n)
b) O(n²)
c) O(log n)
d) O(1)
a) O(n)
Qual algoritmo de ordenação tem complexidade O(n log n) no pior caso?
a) Merge Sort
b) Bubble Sort
c) Insertion Sort
d) Selection Sort
a) Merge Sort
Qual algoritmo de ordenação é mais eficiente para listas quase ordenadas?
a) Merge Sort
b) Insertion Sort
c) Selection Sort
d) Quick Sort
b) Insertion Sort
O que é um algoritmo de ordenação?
É um algoritmo usado para organizar os elementos de uma lista ou array em uma ordem específica, como crescente ou decrescente.
Quais são os dois tipos principais de algoritmos de ordenação?
Ordenação baseada em comparação (em que os elementos a serem ordenados são diretamente comparados) e não-baseada em comparação (em que os elementos são ordenados sem ser diretamente comparados)
O que é estabilidade em um algoritmo de ordenação?
Um algoritmo de ordenação é estável se ele mantém a ordem relativa dos elementos com valores iguais.
Dê um exemplo de um algoritmo de ordenação estável.
Merge Sort e Insertion Sort são exemplos de algoritmos estáveis.
Dê um exemplo de um algoritmo de ordenação instável.
Selection Sort é geralmente instável
Qual é a complexidade de tempo do Bubble Sort no pior caso?
O(n²).
Qual é a complexidade de tempo do Quick Sort no melhor caso?
O(n log n).
Dê um exemplo de algoritmo de ordenação que não usa comparação.
Counting Sort, Bucket Sort e Radix Sort são exemplos de algoritmos que não usam comparação.
O que significa “particionar” em Quick Sort?
Dividir a lista em duas partes com base em um pivô, onde os elementos menores que o pivô ficam à esquerda e os maiores à direita.
Quando o Quick Sort tem desempenho ruim? O que acontece com a complexidade nesse caso?
Quando o pivô escolhido é sempre o menor ou maior elemento, resultando em O(n²).
Qual é o principal fator que torna o Heap Sort eficiente?
Ele usa a estrutura de dados heap para garantir que o maior ou menor elemento seja sempre removido primeiro.
Qual algoritmo de ordenação tem o pior caso O(n²)?
a) Merge Sort
b) Quick Sort
c) Heap Sort
d) Bubble Sort
d) Bubble Sort
O Heap Sort é baseado em qual estrutura de dados?
a) Lista ligada
b) Árvore binária
c) Heap binário
d) Fila de prioridade
c) Heap binário
Qual é a complexidade de tempo do Radix Sort?
a) O(n)
b) O(n2)
c) O(d⋅(n+k))
d) O(logn)
De maneira geral, qual a diferença entre a complexidade dos algoritmos baseados em comparação e a complexidade dos algoritmos não baseados em comparação?
A complexidade dos algoritmos baseados em comparação depende apenas do tamanho da entrada. Já em algoritmos não baseados em comparação, pode depender de fatores como maior valor ou quantidade de elementos distintos.
Qual algoritmo usa divisão e conquista?
a) Merge Sort
b) Heap Sort
c) Counting Sort
d) Insertion Sort
a) Merge Sort
Qual é a complexidade de tempo do Quick Sort no pior caso?
a) O(n)
b) O(n²)
c) O(log n)
d) O(1)
b) O(n²)
O que acontece com o desempenho do Bubble Sort em uma lista já ordenada?
a) Continua sendo O(n²)
b) Torna-se O(n)
c) Torna-se O(n log n)
d) Torna-se O(n²)
b) Torna-se O(n)
O que acontece com o desempenho do Quick Sort em uma lista já ordenada? Considere que nessa implementação, o algoritmo escolherá sempre o primeiro elemento como pivô.
a) Continua sendo O(n log n)
b) Torna-se O(n)
c) Torna-se O(log n)
d) Torna-se O(n²)
d) Torna-se O(n²)
O que acontece com o desempenho do Merge Sort em uma lista já ordenada?
a) Continua sendo O(n log n)
b) Torna-se O(n)
c) Torna-se O(log n)
d) Torna-se O(n²)
a) Continua sendo O (n log n)
Qual algoritmo é geralmente estável e tem complexidade O(n log n)?
a) Merge Sort
b) Quick Sort
c) Heap Sort
d) Bubble Sort
a) Merge Sort
Qual algoritmo de ordenação sempre usa O(n log n) no pior caso?
a) Quick Sort
b) Merge Sort
c) Bubble Sort
d) Selection Sort
b) Merge Sort
O que ocorre no passo de “intercalação” do Merge Sort?
a) Elementos são combinados em ordem crescente
b) Subarrays são divididos em partes menores
c) Um pivô é selecionado
d) Nenhuma das opções acima
a) Elementos são combinados em ordem crescente
Qual é a principal desvantagem do Merge Sort?
a) É lento para entradas pequenas
b) Usa muita memória adicional
c) É instável
d) Não funciona para listas ordenadas
b) Usa muita memória adicional
Qual algoritmo é mais eficiente para listas com muitos valores repetidos?
a) Quick Sort
b) Merge Sort
c) Counting Sort
d) Heap Sort
c) Counting Sort
