Considere um processo de ordenação dos elementos do array [16,8,6,14,12,4] em ordem crescente. Supõe-se um algoritmo que percorra o array repetidamente até que esteja ordenado, sem utilização de memória auxiliar para os elementos do array (in place). A lista a seguir mostra a disposição dos elementos no array após cada ciclo de iteração. [8, 6, 14, 12, 4, 16] [6, 8, 12, 4, 14, 16] [6, 8, 4, 12, 14, 16] [6, 4, 8, 12, 14, 16] [4, 6, 8, 12, 14, 16] Nesse caso, é correto concluir que foi utilizado o algoritmo:
- A)Bubble Sort;
Correta, pois o processo mostrado faz comparações entre elementos vizinhos e leva os maiores para o fim a cada ciclo, exatamente como no Bubble Sort.
- B)Insertion Sort;
Incorreta, porque o Insertion Sort insere cada elemento na posição certa da parte já ordenada, e não realiza essa sequência de trocas adjacentes.
- C)QuickSort;
Incorreta, pois o QuickSort divide o array em partições com pivô, em vez de fazer varreduras sucessivas trocando vizinhos.
- D)Selection Sort;
Incorreta, porque o Selection Sort seleciona o menor elemento da parte não ordenada para colocá-lo na frente, o que não corresponde à evolução apresentada.
- E)Shellsort.
Incorreta, já que o Shellsort usa incrementos e sublistas distantes, não esse padrão de deslocamento gradual dos maiores elementos para o final.
Gabarito: A
A questão descreve um algoritmo que varre o array repetidamente, fazendo trocas entre elementos vizinhos e “empurrando” os maiores para o fim a cada passada. Isso é a cara do Bubble Sort: ele compara pares adjacentes e vai formando, ciclo após ciclo, a parte final já ordenada. Repare que, após a primeira passada, o 16 já foi parar no último lugar; depois, o 14 também “encosta” no final, e assim por diante. É exatamente esse comportamento que aparece na sequência dada. No Bubble Sort, a ordenação acontece por passagens sucessivas sobre o array, sem precisar de memória auxiliar para guardar outro vetor, portanto é um algoritmo in place. A lógica é simples e bem conhecida em prova: se o elemento da esquerda é maior que o da direita, troca-se; caso contrário, segue adiante. Ao final de cada ciclo, o maior elemento do trecho analisado fica na posição correta. O Insertion Sort, por outro lado, trabalha inserindo cada elemento na posição adequada dentro da parte já ordenada, o que gera uma dinâmica diferente da mostrada no enunciado. Selection Sort procura o menor elemento da parte não ordenada e o coloca na frente, também com comportamento distinto. Já QuickSort e Shellsort seguem estratégias bem diferentes e não produzem essa sequência de “borbulhamento” dos maiores valores para o final. Por isso, o gabarito A está correto: a evolução do array bate com o mecanismo clássico do Bubble Sort. Em prova, quando aparecer a ideia de repetidas passagens com trocas de vizinhos até ordenar tudo, pode acender o alerta de Bubble Sort na sua cabeça.