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

• Projete em pseudocódigo uma função recursiva maximo(L) que recebe uma lista não vazia de inteiros e retorna o maior…
• Projete em pseudocódigo um algoritmo recursivo max_recursive(L) que recebe uma lista não vazia L de inteiros e retorna o…
• Projete em pseudocódigo uma função recursiva que verifica se uma lista de inteiros L está estritamente crescente (cada…
• Projete em pseudocódigo uma função recursiva permutar(L) que recebe uma lista L com n elementos distintos e retorna uma…
• Projete em pseudocódigo uma função recursiva separar_indices(L) que recebe uma lista L e retorna duas listas: elementos…
• Projete um algoritmo em pseudocódigo que receba uma lista L de n inteiros e retorne uma nova lista em que todos os…

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