Projete em pseudocódigo uma função recursiva merge_sorted(L1,L2) que recebe duas listas ordenadas não…

Questão

Projete em pseudocódigo uma função recursiva merge_sorted(L1,L2) que recebe duas listas ordenadas não decrescentes de inteiros e retorna uma lista ordenada não decrescente contendo todos os elementos; não use estruturas iterativas e preserve a ordem relativa (estabilidade).

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

Resposta esperada

funcao merge_sorted(L1, L2): se L1 == [] entao retorne L2 se L2 == [] entao retorne L1 se L1[0] <= L2[0] entao retorne concatenar([L1[0]], merge_sorted(L1[1:], L2)) senao retorne concatenar([L2[0]], merge_sorted(L1, L2[1:])) Observações: - A comparação com <= preserva estabilidade (elementos iguais de L1 mantêm-se antes dos de L2). - Complexidade de tempo: O(n+m), onde n e m são os tamanhos de L1 e L2; cada elemento é processado uma vez. - Espaço: O(n+m) para a lista resultante e profundidade de recursão O(n+m) no pior caso.

Explicação

A solução apresentada utiliza recursão para combinar duas listas ordenadas, garantindo que a ordem relativa dos elementos seja preservada ao comparar os primeiros elementos de cada lista. A função retorna a lista resultante de forma eficiente, processando cada elemento uma única vez, o que resulta em uma complexidade de tempo linear. Além disso, a abordagem recursiva permite que a profundidade da pilha de chamadas se mantenha dentro dos limites, evitando iterações que poderiam complicar a implementação.

Raio-X da questão

Questões parecidas com resolução

• Projete um algoritmo em pseudocódigo que mescle duas listas ordenadas (A e B) em uma única lista ordenada crescente…
• 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 uma função recursiva que verifica se uma lista de inteiros L está estritamente crescente (cada…
• Escreva em pseudocódigo um algoritmo que una duas listas ordenadas de números (listaA e listaB) em uma única lista…
• 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 uma função recursiva separar_indices(L) que recebe uma lista L e retorna duas listas: elementos…

Todas as questões de Programação - Programação com listas e recursão