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
O enunciado pede para ordenar a sequência 2,4,6,8,10,12,1,3,5,7,9,11 usando cada um dos métodos de ordenação vistos (bubble sort, insertion sort e selection sort) e contar quantas comparações e trocas cada um faz.
Passo 2
Aplicando o bubble sort (variante básica, sem “early exit”): em cada uma das 11 passadas fazemos um total de 11+10+⋯+1 = 66 comparações de pares adjacentes, e ao mover o 12 para frente na primeira metade e o 10,8,6,4,2 na segunda, obtemos 18 trocas.
Passo 3
Aplicando o insertion sort (contando cada deslocamento de elemento como uma troca/movimentação): nos primeiros 5 passos a sequência já está parcialmente ordenada, gerando 5 comparações e 0 trocas; ao inserir 1,3,5,7,9,11 no lugar certo temos respectivamente 6+6+5+4+3+2 = 26 comparações e 21 deslocamentos, totalizando 5+26 = 31 comparações e 21 trocas.
Passo 4
Aplicando o selection sort (toda passada varre o restante do vetor): em cada uma das 11 passadas fazemos 11+10+⋯+1 = 66 comparações para achar o mínimo e, como o mínimo nunca está na posição inicial, fazemos 1 troca por passada, totalizando 11 trocas.
Resposta
Bubble Sort: 66 comparações e 18 trocas; Insertion Sort: 31 comparações e 21 trocas; Selection Sort: 66 comparações e 11 trocas.