Questão 726943

• Banca: INSTITUTO CIDADES
• Órgão: TCM-GO
• Ano: 2012
• Provas: INSTITUTO CIDADES - 2012 - TCM-GO - Auditor de Controle Externo - Informática
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Algoritmos de Ordenação

São exemplos de algoritmos de ordenação, exceto:

• A. Bubble Sort
• B. Select Sort
• C. Shell Sort
• D. Busca Sequencial;
• E. Quick Sort;

Gabarito: D

Comentários

•  busca linear (ou busca sequêncial) para expressar um tipo de pesquisa em vetores ou listas de modo sequencial, i. e., elemento por elemento, de modo que a função do tempo em relação ao número de elementos é linear, ou seja, cresce proporcionalmente. Num vetor ordenado, essa não é a pesquisa mais eficiente, a pesquisa (ou busca) binária, por exemplo, é um tipo de pesquisa com o gráfico de tempo logarítmo.
• a) BUBBLE SORT: faz parte dos métodos simples de ordenação. A ideia é percorrer o vetor diversas vezes, a cada passagem fazendo flutuar para o topo o maior elemento da sequência.
  COMPLEXIDADE DE TEMPO: O(n²)
  
  b) SELECTION SORT e não "SELECT SORT": é um algoritmo de ordenação baseado em se passar sempre o menor valor para a primeira posição ( ou o maior valor, dependendo da ordem requerida - crescente ou decrescente), depois o segundo menor valor (supondo ordem crescente) para a segunda posição e assim sucessivamente para os N - 1 elementos restantes até os 2 últimos elementos.
  COMPLEXIDADE DE TEMPO: O(n²)
  
  c) SHELL SORT: é o mais eficiente algoritmo de classificação dentre os de ordem quadrática. É um refinamento do método INSERTION SORT. O algoritmo difere desse último pelo fato de, no lugar de considerar o ARRAY a ser ordenado como único segmento, ele considera vários segmentos, aplicando o método INSERTION SORT em cada um deles.
  A COMPLEXIDADE DO ALGORITMO NÃO PODE SER DETERMINADA PORQUE DEPENDE DA SEQUÊNCIA DE GAP(SALTO): pode ser tanto O(n²) quanto O(nlog₂n) ou O(n^3/2).
  
  d) BUSCA LINEAR OU SEQUENCIAL(ERRADA): não é um algoritmo de ordenação e sim um algoritmo de pesquisa: ele busca em vetores e listas através de uma forma sequencial, i.e. elemento por elemento, de modo que a função tempo em relação ao número de elementos é linear, ou seja, cresce proporcionalmente.
  
  e) QUICK SORT: método de ordenação rápido e eficiente; funciona por comparação NÃO-ESTÁVEL. Adota a estratégia de divisão e conquista. A estratégia consiste em rearranjar as chaves de modo que as chaves menores precedam as maiores. Em seguida, o QUICK SORT ordena as duas sublistas de chave menores e maiores recursivamente até que a lista completa se encontre ordenada.
  COMPLEXIDADE DE TEMPO:
  Melhor e médio casos: O(nlog₂n)
  Pior caso: O(n²)

• Essa questão com "Select Sort" era digna de anulação.

• Força Guerreiro!!!!!!