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:
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
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
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:
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:
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:
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)
Selection sort: 66 comparações e 10 trocas
Insertion sort: 46 comparações e 36 deslocamentos (trocas)