Faça um teste de mesa com cada método de ordenação estudado até o momento, utilizando as seguintes sequências de dados de entrada:
2,4,6,8,10,12,11,9,7,5,3,1
Em cada caso, mostre o número de comparações e trocas que realizam na ordenação de sequências.

Passo 1

Vamos ordenar a sequência 2,4,6,8,10,12,11,9,7,5,3,1 usando três métodos clássicos: bubble sort, selection sort e insertion sort, contando as comparações e as trocas (ou deslocamentos) em cada um.

Passo 2

No bubble sort a ideia é fazer várias passadas pelo vetor, comparando cada par de vizinhos e trocando-os se estiverem fora de ordem. A cada passada o maior elemento “borbulha” para o fim. Para n=12 elementos, temos 11 comparações na primeira passada, 10 na segunda, e assim por diante até 1 na última. Contando trocas em cada comparação, chegamos a um total de:
Comparaçõesbubb<==11+10+9+8+7+6+5+4+3+2+1=66,çõ Trocasbubb<==6+5+5+4+4+3+3+2+2+1+1=36

Passo 3

No selection sort a ideia é, a cada iteração, varrer o segmento não ordenado procurando o mínimo e, ao final, trocá-lo com o elemento da posição atual. Temos de comparar todos os pares remanescentes em cada passo, isto é, 11 comparações na primeira, 10 na segunda, etc., até 1 na última. As trocas só ocorrem se o mínimo achar-se em posição diferente de onde começa a passagem. Fazendo as contas:
Comparaçõessel=11+10+9+8+7+6+5+4+3+2+1=66,çõ Trocassel=1 (passo1)+1+1+1+1+1+1+1+1+0+1=10

Passo 4

No insertion sort construímos a parte esquerda já ordenada, inserindo cada novo elemento na posição certa. Contamos cada comparação no laço de busca da posição e cada deslocamento (shift) que move elementos para a direita. Ao final das 11 inserções temos:
Comparaçõesinsert=1+1+1+1+5+4+6+8+10+11=46,çõ Deslocamentosinsert=0+0+0+0+1+3+5+7+9+11=36

Resposta

Bubble sort: 66 comparações e 36 trocas
Selection sort: 66 comparações e 10 trocas
Insertion sort: 46 comparações e 36 deslocamentos (trocas)

Exercícios relacionados