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
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
sumi=1^5(6-i)=5+4+3+2+1=15
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:
sumi=1^5(6-i)=15
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.

Exercícios relacionados