Questão 33 Um algoritmo de ordenação é estável se a ordem relativa dos itens com chaves iguais mantém-se inalterada após a ordenação. Quais dos seguintes algoritmos de ordenação são estáveis?

(I) BubbleSort (ordenação por bolha);
(II) InsertionSort (ordenção por inserção);
(III) HeapSort;
(IV) QuickSort;

(a) Somente (II).
(b) Somente (I) e (II).
(c) Somente (I), (II) e (III).
(d) Somente (II), (III) e (IV).
(e) Somente (I), (III) e (IV).

Gabarito: b (Selecione o texto a esquerda para ver a resposta ou consulte o fim do post).

Explicação: Esta questão exige que saibamos como os algoritmos enumerados funcionam e específicamente o que eles fazem quando encontram elementos iguais. Eles invertem a posição dos mesmos ou as mantém?
Se mantiver é um algoritmo estável, caso contrário não.

Creio que não cabe explicar aqui como funciona cada um desses, mas basta mostrar uma lista de algoritmos estáveis e algoritmos não-estáveis (instáveis). Vale lembrar que dos algoritmos com tempo no pior caso O (n lg n) o único estável é o MergeSort.

Algoritmos estáveis
Bubble sort (Item I)
Cocktail sort
Insertion sort (Item II)
Merge sort
Bucket sort
Counting sort

Algoritmos instáveis
Alguns algoritmos de ordenação instáveis:
Quicksort
Heapsort
Selection sort
Shell sort

Logo, alternativa b é a correta!

Mais informações sobre Ordenação Estável.

Não concorda? 
Comente, opine e demonstre seu conhecimento!

Gabarito: d