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:
8,9,7,9,3,2,3,8,4,6
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 8,9,7,9,3,2,3,8,4,6 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 9+8+cdots+1=45 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.

Exercícios relacionados