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 simular, em sequência já ordenada (2,4,6,8,10,12), três métodos de ordenação (Bubble, Selection, Insertion) e contar quantas comparações e trocas cada um faz.
Passo 2
No Bubble Sort, cada passagem i de 1 até n−1 faz n−i comparações. Para n=6, temos
comparações e, como a sequência já está ordenada, nenhuma troca ocorre, totalizando 0 trocas.
Passo 3
No Selection Sort, para cada posição i de 1 até n−1 fazemos n−i comparações para encontrar o mínimo. Para n=6:
comparações. Se só trocamos quando o índice do mínimo difere de i, em sequência já ordenada não há trocas, logo 0 trocas.
Passo 4
No Insertion Sort, para cada chave na posição i de 2 até n há uma comparação para decidir se desloca elementos maiores. Como a sequência já está ordenada, em cada i essa comparação falha imediatamente. São n−1=5 comparações e nenhum deslocamento (troca), totalizando 0 trocas.
Resposta
Bubble Sort: 15 comparações e 0 trocas; Selection Sort: 15 comparações e 0 trocas; Insertion Sort: 5 comparações e 0 trocas.