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 11,9,7,5,3,1 em ordem crescente usando cada método de ordenação visto (bubble sort, selection sort e insertion sort) e, em cada caso, contar quantas comparações e quantas trocas são feitas.
Passo 2
No bubble sort a gente faz sucessivas passagens comparando cada par de vizinhos e trocando-os se estiverem fora de ordem. Para uma lista de 6 elementos fazemos (6−1)+(6−2)+…+1 = 15 comparações. Como a lista vem completamente invertida, em cada comparação encontramos um par fora de ordem, logo ocorrem 15 trocas.
Passo 3
No selection sort a gente, a cada iteração i, procura o menor elemento entre as posições i…5 com (6−i−1) comparações e depois troca esse menor elemento com o da posição i (se não estiverem já trocados). Isso dá também 5+4+3+2+1 = 15 comparações. Mas como a cada uma das 5 iterações o menor não está na posição i, fazemos exatamente 5 trocas.
Passo 4
No insertion sort implementado trocando elemento a elemento (ou seja, cada inversão é um swap adjacente), cada nova chave precisa “subir” até sua posição certa. Em cada inserção i fazemos i comparações e i trocas, resultando em 1+2+3+4+5 = 15 comparações e 15 trocas no total.
Resposta
Bubble sort: 15 comparações, 15 trocas; Selection sort: 15 comparações, 5 trocas; Insertion sort: 15 comparações, 15 trocas.