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:
89,79,32,38,46,26,43,38,32,79
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 [89,79,32,38,46,26,43,38,32,79] usando os métodos de ordenação estudados (Bubble Sort, Selection Sort e Insertion Sort) e, em cada caso, contar o número de comparações e o número de trocas (ou movimentações de elementos).

Passo 2

No Bubble Sort, com n=10, sempre fazemos n-1 + n-2 + cdots + 1 = 45 comparações de pares adjacentes, trocando sempre que o par estiver fora de ordem. Ao detalhar cada passagem (sem otimização de parada antecipada), obtém-se 26 trocas no total.

Passo 3

No Selection Sort, em cada iteração i (de 1 a 9) fazemos n-i comparações para encontrar o mínimo e só executamos uma troca por iteração (quando o mínimo não está na posição i). Somando as comparações 9+8+cdots+1=45 e trocando apenas quando necessário, temos 8 trocas.

Passo 4

No Insertion Sort, ao inserir o elemento chave em cada posição i=2 a 10, comparamos até encontrar o ponto correto (total de 32 comparações) e fazemos um deslocamento por elemento maior que a chave mais uma atribuição final da chave, somando 35 movimentações (que aqui contamos como trocas).

Resposta

Bubble Sort: 45 comparações e 26 trocas
Selection Sort: 45 comparações e 8 trocas
Insertion Sort: 32 comparações e 35 trocas

Exercícios relacionados