Algoritmo de pesquisa e ordenação

Question 1

Quais os algoritmos de pesquisa?

Answer 1

• Pesquisa Linear (Linear Search)
  
  • Descrição: A pesquisa linear verifica cada elemento de uma lista sequencialmente até encontrar o item desejado.
  • Complexidade: O(n), onde n é o número de elementos na lista.
  • Vantagem: Simples e não requer a lista estar ordenada.
  • Desvantagem: Lento para listas grandes.
• Pesquisa Binária (Binary Search)
  
  • Descrição: A pesquisa binária divide a lista ordenada em dois subgrupos a cada iteração, comparando o item com o valor central.
  • Complexidade: O(log n), onde n é o número de elementos.
  • Vantagem: Muito mais eficiente que a pesquisa linear, mas requer a lista estar ordenada.
  • Desvantagem: Só funciona em listas ordenadas.

Question 2

Selection Sort

Answer 2

• Ordenação por Seleção (Selection Sort)
  • Descrição: A cada iteração, encontra-se o menor (ou maior) elemento da lista e o coloca na posição correta.
  • Complexidade: O(n²), onde n é o número de elementos.
  • Vantagem: Simples de entender e implementar.
  • Desvantagem: Ineficiente para grandes listas.

Question 3

Insertion Sort

Answer 3

• Ordenação por Inserção (Insertion Sort)
  • Descrição: O algoritmo pega um elemento e o insere na posição correta de uma lista já ordenada.
  • Complexidade: O(n²) no pior caso, mas O(n) no melhor caso (quando a lista já está ordenada).
  • Vantagem: Muito eficiente para listas pequenas ou quase ordenadas.
  • Desvantagem: Ineficiente para listas grandes.

Question 4

Bubble Sort

Answer 4

• Bubble Sort
  • Descrição: A cada iteração, compara elementos adjacentes e os troca se estiverem na ordem errada, repetindo o processo até a lista estar ordenada.
  • Complexidade: O(n²) no pior caso.
  • Vantagem: Simples de entender e implementar.
  • Desvantagem: Lento para listas grandes e repetidas comparações são ineficientes.

Question 5

Quick Sort

Answer 5

• Ordenação Rápida (Quick Sort)
  • Descrição: O algoritmo escolhe um “pivô” e particiona a lista em torno desse pivô, ordenando recursivamente as sublistas.
  • Complexidade: O(n log n) no caso médio, O(n²) no pior caso.
  • Vantagem: Muito eficiente na prática, especialmente para grandes listas.
  • Desvantagem: O pior caso pode ser ruim, mas isso pode ser mitigado com escolhas inteligentes de pivôs.

Question 6

Merge Sort

Answer 6

• Ordenação por Mesclagem (Merge Sort)
  • Descrição: Divide recursivamente a lista ao meio e depois mescla as sublistas de forma ordenada.
  • Complexidade: O(n log n), sempre.
  • Vantagem: Estável e eficiente, com desempenho previsível.
  • Desvantagem: Requer espaço adicional para a mesclagem.

Question 7

Counting Sort

Answer 7

• Ordenação por Contagem (Counting Sort)
  • Descrição: Conta o número de ocorrências de cada elemento em uma lista e usa essas contagens para ordenar os elementos.
  • Complexidade: O(n + k), onde n é o número de elementos e k é o valor máximo no conjunto.
  • Vantagem: Extremamente eficiente quando o intervalo de números é pequeno.
  • Desvantagem: Não é útil para conjuntos de dados com grande variação de valores.

Question 8

Radix Sort

Answer 8

• Ordenação Radix (Radix Sort)
  • Descrição: Ordena os números digitando-os por cada posição de dígito, de menor para maior.
  • Complexidade: O(nk), onde n é o número de elementos e k é o número de dígitos.
  • Vantagem: Muito eficiente quando o número de dígitos (ou caracteres) é pequeno.
  • Desvantagem: Não é comparativo e requer espaço extra.

Question 9

Cocktail Sort

Answer 9

• Ordenação por Bolha Bidirecional (Cocktail Sort)
  • Descrição: Uma variação do Bubble Sort que vai e volta pela lista, ordenando em ambas as direções.
  • Complexidade: O(n²), similar ao Bubble Sort.
  • Vantagem: Pode ser ligeiramente mais eficiente que o Bubble Sort em alguns casos.
  • Desvantagem: Ainda ineficiente para listas grandes.

Question 10

Qual a ordem de complexidade de Big-O?

Answer 10

O(1) < O(N) < O(logN) < O(2^n) < O(N ^ X)