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
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
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
(de 1 a 9) fazemos
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
). Somando as comparações
e trocando apenas quando necessário, temos 8 trocas.
Passo 4
No Insertion Sort, ao inserir o elemento chave em cada posição
a
, 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
Selection Sort: 45 comparações e 8 trocas
Insertion Sort: 32 comparações e 35 trocas