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

• Escreva um algoritmo em linguagem descritiva que, recebendo uma lista de arestas (edge list) de um grafo com V vértices…
• Ao decompor um algoritmo complexo, que documentação técnica mínima deve acompanhar cada função para permitir integração…
• Qual vantagem direta de transformar uma variável global em parâmetro de função ao decompor um algoritmo que manipula…
• Projete a decomposição de alto nível de um algoritmo que gera relatórios mensais de presença por aluno a partir de dados…
• Quais são, em ordem, as três etapas essenciais ao decompor um algoritmo complexo para facilitar sua resolução?
• Ao decompor um algoritmo que calcula estatísticas de temperatura, qual subtarefa trata de identificar e excluir outliers…

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