Projete um algoritmo in-place, em pseudocódigo, que receba um vetor A de n números distintos e um inteiro k (1…

Questão

Projete um algoritmo in-place, em pseudocódigo, que receba um vetor A de n números distintos e um inteiro k (1 = k = n) e retorne o k-ésimo menor elemento usando a estratégia de partição (Quickselect). Explique passo a passo, com complexidade média e pior caso, e indique como escolher pivô para melhorar desempenho.

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

Resposta esperada

Resposta modelo (pseudocódigo e justificativa): Função Quickselect(A, esquerda, direita, k): se esquerda == direita: retornar A[esquerda] escolher pivô_index entre [esquerda,direita] (por exemplo, aleatório ou mediana de três) pivô_index ? Partition(A, esquerda, direita, pivô_index) rank ? pivô_index - esquerda + 1 // posição do pivô na partição se k == rank: retornar A[pivô_index] senão se k < rank: retornar Quickselect(A, esquerda, pivô_index-1, k) senão: retornar Quickselect(A, pivô_index+1, direita, k-rank) Função Partition(A, l, r, p): trocar A[p] com A[r] storeIndex ? l para i de l até r-1: se A[i] < A[r]: trocar A[storeIndex] com A[i]; storeIndex ? storeIndex+1 trocar A[storeIndex] com A[r] retornar storeIndex Descrição e análise: - O algoritmo é in-place: a partição rearranja elementos dentro do próprio vetor sem estruturas auxiliares significativas. - Em cada chamada, Partition coloca o pivô em sua posição correta; elementos menores vão à esquerda e maiores à direita. - Dependendo do rank do pivô, o algoritmo recorre apenas a uma das subpartes, portanto o trabalho médio T(n)=T(n/2)+O(n) ? O(n) médio. - Pior caso (pivô sempre extremo) gera T(n)=T(n-1)+O(n) ? O(n^2). Para garantir pior caso linear, usar seleção de pivô pelo algoritmo mediana-de-medianas (determinístico), que escolhe um pivô aproximado à mediana em O(n), resultando em O(n) no pior caso. Observações práticas: - Escolha de pivô aleatório ou mediana de três reduz muito a probabilidade do pior caso em instâncias reais. - Quickselect é eficiente e usa pouca memória; para garantir robustez em entradas adversas, preferir mediana-de-medianas quando a garantia de tempo linear é necessária.

Explicação

O algoritmo Quickselect é eficiente na busca do k-ésimo menor elemento, utilizando a técnica de partição para reduzir o espaço de busca em cada iteração. A escolha do pivô, seja aleatória ou pela mediana de três, é crucial para evitar o pior caso e garantir desempenho médio linear. A abordagem in-place economiza memória, tornando o algoritmo prático para grandes conjuntos de dados.

Raio-X da questão

Questões parecidas com resolução

• Projete um algoritmo em pseudocódigo que, dado um vetor A[1..n] de inteiros e um inteiro k (1 = k = n), calcule a maior…
• Apresente, em pseudocódigo resumido, o algoritmo in-place que rotaciona à direita um vetor A[0..n-1] por k posições…
• Projete em pseudocódigo uma função recursiva quicksort(L) que ordena uma lista L de inteiros em ordem não crescente…
• Projete em pseudocódigo um algoritmo que remova, in-place, todas as ocorrências de um valor v em um vetor A de…
• Projete um algoritmo em pseudocódigo que, dado um vetor V de n inteiros e um inteiro k, determine se existem índices i <…
• Proponha um algoritmo em pseudocódigo que, dada uma lista A de n inteiros e um inteiro k>0, determine o comprimento do…

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