GabaritoC — Merge Sort
Gabarito: letra C. O Merge Sort é o único entre os listados que, por padrão, é implementado de forma recursiva, baseando-se no paradigma de divisão e conquista. As demais opções (Bubble Sort, Shell Sort, Insertion Sort, Selection Sort) são tipicamente implementadas de forma iterativa.
A banca testa o conhecimento sobre a natureza dos algoritmos de ordenação. O Merge Sort divide repetidamente o vetor ao meio recursivamente até que cada subproblema tenha um único elemento e depois os combina ordenando. Essa abordagem recursiva é inerente ao algoritmo.
Algoritmo | Implementação Padrão | Paradigma | Característica Principal |
|---|---|---|---|
Bubble Sort | Iterativa | Comparação de pares adjacentes | Percorre o vetor trocando elementos fora de ordem |
Shell Sort | Iterativa | Inserção com gaps | Compara elementos distantes, reduzindo intervalo |
Merge Sort | Recursiva | Divisão e conquista | Divide o vetor ao meio recursivamente e intercala |
Insertion Sort | Iterativa | Inserção direta | Insere cada elemento na posição correta |
Selection Sort | Iterativa | Seleção do mínimo | Seleciona o menor elemento a cada iteração |
Bubble Sort é um algoritmo que percorre o vetor diversas vezes comparando pares adjacentes e trocando se estiverem na ordem errada. Sua implementação padrão é iterativa (laços aninhados). Embora seja possível escrevê-lo recursivamente, não é a forma usual.
Shell Sort é uma extensão do Insertion Sort que compara elementos distantes e reduz o intervalo gradualmente. Sua implementação típica é iterativa, com laços aninhados controlando os gaps.
O Merge Sort é o algoritmo de ordenação que por excelência é implementado de forma recursiva, aplicando o método de divisão e conquista. Conforme mencionado no conteúdo de apoio, ele é um exemplo de algoritmo que "reduzem repetidamente o problema em subproblemas, geralmente de forma recursiva" (classificação por paradigma). A cada chamada recursiva, o vetor é dividido ao meio até restar um elemento, e depois as metades são intercaladas de volta.
Insertion Sort constrói a ordenação inserindo cada elemento na posição correta entre os já ordenados. Sua implementação padrão é iterativa, percorrendo o vetor da esquerda para a direita.
Selection Sort seleciona o menor elemento a cada iteração e o coloca na posição correta. Também é implementado iterativamente, com dois laços aninhados.
Para identificar qual algoritmo é tipicamente recursivo, lembre-se dos que usam divisão e conquista: Merge Sort e Quick Sort (não listado). Os demais (Bubble, Insertion, Selection, Shell) são iterativos naturalmente. Grave essa associação.
Gabarito: letra C.
Link permanente: /questoes/qg570595