Banco de questões: Algoritmos e Problemas: Médio

Um algoritmo de ordenação muito eficiente, mas complexo, é o algoritmo QuickSort. Este algoritmo se baseia no método de divisão e conquista para ordenar uma lista de números. Para realizar a ordenação, o QuickSort escolhe um elemento da lista, chamado de pivô, e rearranja a lista de forma que todos os elementos menores que o pivô fiquem antes dele, e os maiores, depois. Em seguida, o algoritmo é aplicado recursivamente às sub-listas dos elementos menores e maiores. Considere a seguinte lista de números inteiros: L = [7, 2, 1, 6, 8, 5, 3, 4]. Utilize o QuickSort para ordenar a lista L em ordem crescente, mostrando os passos do algoritmo e explicando a escolha dos pivôs em cada iteração. Após a ordenação, discuta se a escolha de um pivô fixo, como o primeiro elemento da lista, poderia alterar a complexidade de tempo do algoritmo em relação a uma escolha mais otimizada de pivôs. Justifique sua resposta com base nos conceitos do método QuickSort e na teoria de complexidade de algoritmos.

Em um algoritmo para determinar se um número inteiro N é par, observamos que se o resto da divisão de N por 2 é igual a 0, então N é par. Se aplicarmos esse algoritmo ao número 10, obtemos o resultado desejado. No entanto, se aplicarmos o mesmo algoritmo ao número 17, o resultado não é o esperado. Explique por que o resultado é diferente e proponha uma modificação no algoritmo para que ele funcione corretamente para qualquer número inteiro positivo. Em seguida, justifique a validade da sua modificação.