Algoritmos de Ordenação e Busca: Bubble Sort e Insertion Sort
Algoritmos de Ordenação e Busca
Convém entender diferentes métodos para resolver o mesmo problema, como ordenar registros e, depois, buscar com eficiência. A aula apresenta fundamentos de ordenação, tipos de ordenação e dois algoritmos clássicos: Bubble Sort e Insertion Sort.
Visão geral das técnicas
5. Questões sobre o assunto
Questão 1 (média) - Qual é a ideia principal do Bubble Sort?
Resposta correta: C) Percorrer pares adjacentes e trocar se fora de ordem
O Bubble Sort faz várias passadas, comparando pares adjacentes e trocando quando o esquerdo é maior que o direito, enviando o maior elemento para o fim na primeira passagem, repetindo até ordenar.
Questão 2 (difícil) - Qual é a complexidade de tempo típica do Bubble Sort no pior caso?
Resposta correta: A) O(n^2)
Sem otimizações, Bubble Sort efetua cerca de n(n-1)/2 comparações no pior caso, resultando em tempo quadrático.
Questão 3 (difícil) - Qual descreve corretamente o Insertion Sort?
Resposta correta: C) insere cada elemento na posição correta dentro de uma sublista já ordenada
OInsertion Sort mantém uma porção ordenada à esquerda e, ao iterar, insere o elemento atual deslocando os elementos maiores para a direita até encontrar a posição correta.
Questão 4 (extrema) - Sobre ordenação externa, qual afirmação é verdadeira?
Resposta correta: B) Divide dados em blocos menores, ordena cada bloco e depois combina
Ordenação externa é usada quando o conjunto de dados não cabe na memória; usa blocos ordenados combinados para formar o total ordenado.
