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:
5,7,2,8,1,6
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 5, 7, 2, 8, 1, 6 usando cada método de ordenação visto (Bubble Sort, Selection Sort e Insertion Sort) e contar o número de comparações e trocas feitas em cada caso. Vamos trabalhar com o conceito de percorrer a lista, comparar elementos e, quando o algoritmo mandar, trocar ou deslocar esses elementos.

Passo 2

Aplicando o Bubble Sort (troca de vizinhos):
– Passamos várias vezes pela lista, em cada passo comparamos pares adjacentes e, se o da esquerda for maior, trocamos.
– Na primeira passagem fazemos 5 comparações (n–1), com 3 trocas; na segunda, 4 comparações, 3 trocas; terceira, 3 comparações, 1 troca; quarta, 2 comparações, 1 troca; quinta, 1 comparação, 0 trocas.
– Totalizamos 5+4+3+2+1 = 15 comparações e 3+3+1+1+0 = 8 trocas.

Passo 3

Aplicando o Selection Sort (seleciona mínimo e troca com a posição i):
– Em cada iteração i de 0 a 4, buscamos o menor elemento no trecho i…5, contando comparações, e ao final trocamos o mínimo de posição (se for diferente de i).
– Fazemos sempre 5+4+3+2+1 = 15 comparações. Como o mínimo só coincide com a posição i em uma das 5 iterações, realizamos 4 trocas.

Passo 4

Aplicando o Insertion Sort (insere cada elemento no lugar certo deslocando os maiores):
– Para i de 1 a 5, pegamos a chave e vamos comparando com os anteriores até achar a posição certa. Cada comparação chave < A[j] conta, e cada deslocamento A[j+1] = A[j] conta como troca.
– No total foram 12 comparações (incluindo a que pára o while) e 8 deslocamentos (trocas).

Resposta

Bubble Sort: 15 comparações e 8 trocas; Selection Sort: 15 comparações e 4 trocas; Insertion Sort: 12 comparações e 8 trocas.

Exercícios relacionados