Projete em pseudocódigo uma função recursiva quicksort(L) que ordena uma lista L de inteiros em ordem não…

Questão

Projete em pseudocódigo uma função recursiva quicksort(L) que ordena uma lista L de inteiros em ordem não crescente. Explique a escolha do pivô, o caso base, o passo recursivo e por que a recursão termina.

✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.

Resposta esperada

Pseudocódigo: funcao quicksort(L): se tamanho(L) <= 1 entao retorne L fimse pivot := L[0] // escolher o primeiro elemento como pivô maiores := [x em L[1..] se x >= pivot] menores := [x em L[1..] se x < pivot] return concatenar(quicksort(maiores), [pivot], quicksort(menores)) Explicação modelo: - Escolha do pivô: usar L[0] é simples; qualquer elemento pode ser pivô, mas escolhas heurísticas (mediana) podem melhorar desempenho médio. - Caso base: listas com tamanho 0 ou 1 já estão ordenadas; retornam sem novas chamadas. - Passo recursivo: particionar L em duas sublistas menores conforme pivô e ordenar recursivamente cada parte; então concatenar maior, pivô e menor para ordem não crescente. - Terminação: em cada chamada o pivô é removido da sublista original, de modo que as sublistas têm tamanho estritamente menor, garantindo que as chamadas recursivas alcancem o caso base em profundidade finita. - Observação: algoritmo tem corretude pela divisão em elementos >= e < pivô; estabilidade não é garantida com esta partição simples.

Explicação

A escolha do pivô como o primeiro elemento simplifica a implementação e permite a divisão da lista em duas partes, facilitando a ordenação. O caso base assegura que listas pequenas não gerem chamadas recursivas desnecessárias, enquanto o passo recursivo garante que a lista seja dividida em sublistas menores, aproximando-se do caso base. A recursão termina porque cada chamada reduz o tamanho das sublistas, levando eventualmente a listas de tamanho 0 ou 1, que são trivialmente ordenadas.

Raio-X da questão

Questões parecidas com resolução

• Uma equipe precisa gerar cem relatórios com a mesma estrutura, mudando apenas os valores das turmas e das notas. — Qual…
• No fim de semana da feira de ciências do bairro, a equipe de organização percebeu um problema repetido: dezenas de…
• Projete um algoritmo guloso em pseudocódigo que, dado um vetor de n intervalos [inicio, fim], selecione o maior conjunto…
• Projete uma função recursiva em pseudocódigo flatten(L) que recebe uma lista L que pode conter inteiros e sublistas…
• Em um algoritmo, uma função recebe um vetor chamado dados que não deve ser alterado. Para garantir que a variável…
• Descreva um algoritmo em pseudocódigo que, dada uma matriz quadrada A[n][n] de inteiros e um inteiro k>0, percorra os…

Todas as questões de Estratégias de solução de problemas - Decomposição