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
Temos a sequência de entrada
e queremos aplicar os métodos de ordenação estudados (Selection, Bubble e Insertion), contando quantas comparações e quantas trocas cada um faz.
Passo 2
No Selection Sort percorremos o vetor procurando, a cada iteração, o menor elemento no “resto” não ordenado e trocamos com a posição atual. Ao simular isso para 10 elementos, fazemos
comparações e apenas 6 trocas (uma troca por iteração até a metade do vetor, pois depois o menor já está na própria posição).
Passo 3
No Bubble Sort (versão otimizada com interrupção quando não há mais trocas) temos 6 passagens ativas até que nenhuma troca ocorra. Ao todo, realizamos 39 comparações de pares adjacentes e 27 trocas.
Passo 4
No Insertion Sort, para cada elemento “chave” deslocamos todos os maiores que ele para a direita e inserimos-no na posição correta. A simulação dá 33 comparações e 34 movimentos/trocas (contando cada deslocamento como uma troca e a inserção final).
Resposta
Selection Sort: 45 comparações e 6 trocas; Bubble Sort (otimizado): 39 comparações e 27 trocas; Insertion Sort: 33 comparações e 34 trocas.