O algoritmo QuickSort é um método de ordenação muito rápido e eficiente. Ele baseia-se na técnica "dividir e conquistar", onde a ideia é reduzir um problema em problemas menores, resolver cada um destes subproblemas e combinar as soluções parciais para obter a solução do problema original. A recursividade é uma forma interessante de se implementar este algoritmo.
Em resumo, o algoritmo QuickSort é composto dos seguintes passos:
1. Rearranjo da lista de modo eu todos os elementos anteriores ao pivô sejam menores que ele, e todos os elementos posteriores ao pivô sejam maiores que ele.2. Recursivamente ocorre a ordenação da sublista dos elementos menores e sublista dos elementos maiores.3. Escolha de um elemento da lista, denominado pivô.
Assinale a alternativa que apresenta a ordem correta dos passos do algoritmo QuickSort.
Alternativas:
a)
1 – 2 – 3.
b)
2 – 1 – 3
Soluções para a tarefa
O quicksort adota a estratégia de divisão e conquista. A estratégia consiste em rearranjar as chaves de modo que as chaves "menores" precedam as chaves "maiores". Em seguida o quicksort ordena as duas sublistas de chaves menores e maiores recursivamente até que a lista completa se encontre ordenada. Os passos são:
Escolha um elemento da lista, denominado pivô;
Particiona: rearranje a lista de forma que todos os elementos anteriores ao pivô sejam menores que ele, e todos os elementos posteriores ao pivô sejam maiores que ele. Ao fim do processo o pivô estará em sua posição final e haverá duas sub listas não ordenadas. Essa operação é denominada partição;
Recursivamente ordene a sub lista dos elementos menores e a sub lista dos elementos maiores;
O caso base da recursão são as listas de tamanho zero ou um, que estão sempre ordenadas. O processo é finito, pois a cada iteração pelo menos um elemento é posto em sua posição final e não será mais manipulado na iteração seguinte.
A escolha do pivô e os passos do Particiona podem ser feitos de diferentes formas e a escolha de uma implementação específica afeta fortemente a performance do algoritmo.
Então creio eu que falta algumas alternativas ai..
Resposta:
Corrigido pelo AVA 3 - 1 - 2
Explicação: