Questão 238309

• Banca: CESPE / CEBRASPE
• Órgão: ABIN
• Ano: 2010
• Provas: CESPE - 2010 - ABIN - Oficial Técnico de Inteligência - Área de Suporte a Rede de Dados
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Algoritmos de Ordenação; Estrutura de Dados; Hashing

A respeito dos métodos de ordenação, pesquisa e hashing, julgue
os seguintes itens.

A estabilidade de um método de ordenação é importante quando o conjunto de dados já está parcialmente ordenado.

• C. Certo
• E. Errado

Gabarito: E

Comentários

• A estabilidade de um método de ordenação é importante quando você quer preservar a associação entre chaves e valores em uma estrutura de dados.

   

  Exemplo, temos o vetor:

  [0] -> 666

  [1] -> 7

  [2] -> 14

   

  Por ordenação instável:

  [0] -> 7

  [1] ->14

  [2] -> 666

   

  Por ordenação estável:

  [1] -> 7

  [2] ->14

  [0] -> 666

   

  Por exemplo, em PHP usa-se sort ( $array ) para ordenação instável, e asort ($array) para ordenação estável.

   

  Algoritmos Estáveis incluem Bubblesort, Mergesort e Insertsort.

  Algoritmos Instáveis incluem o Quicksort, Heapsort, Selectionsort e Shellsort

   

• Discordo do gabarito.
  Um método de ordenação é dito estável se ele preserva a ordem relativa dos itens com chaves duplicadas/iguais.
  
  Assim, se temos um conjunto de dados parcialmente ordenado como [1, 1, 2, 4, 4, 3, 5, 5, 5], o numero de trocas realizadas por um método instável deve ser maior. Então podemos concluir que o fato de um método ser estável é relavante quando o conjunto está parcialmente ordenado.
  
  Gostaria que alguém comentasse a respeito.
• Concordo com o gabarito. O fato do algoritmo ser estável ou não é irrelevante para melhorar sua performance na ordenação de um conjunto de dados já parcialmente ordenado. Como o colega expos, um algorimo é estável se ele preserva a ordem relativa dos itens comchaves duplicadas/iguais. Veja que o fato do algoritmo não preservar a ordem dos itens com chaves duplicadas/iguais não afetará a performance da ordenação. Um exemplo: nas três primeiras posições temos [1,1,1,...]. Ora, não importa (para uma ordenação) se o 1 que está na primeira posição se manterá lá. Na primeira posição pode estar o segundo ou o terceiro 1, desde que seja um 1. 
  
  []'s, espero ter ajudado!
• Prezados,
  
  Um método de ordenação se diz estável se preserva a ordem de registros de chaves iguais, ou seja, os registros aparecem na sequência ordenada na mesma ordem que estão na sequência inicial. Isso só é importante quando há dados associados as chaves de ordenação, sendo indiferente se o conjunto de dados já está parcialmente ordenado ou não.
  
  Portanto a questão está errada.
  
  

• 2011

  Os métodos de ordenação podem ser classificados como estáveis ou não estáveis. O método é estável se preserva a ordem relativa de dois valores idênticos. 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.

  Certa

   

   

  O Bubble é o pior algoritmo (menos eficiente) e é estável