Mostre o estado da lista após as 3 primeiras execuções do método Particiona do QuickSort no Vetor V=[9,2,7,5,16,12,-4] para ordenar em ordem crescente. Mostre a lista resultante após cada iteração. Considere que o pivô é o último elemento (direita).
Passo 1
Beleza, vamos resolver esse exercício juntos! A gente vai trabalhar com o algoritmo QuickSort, especificamente com o método Particiona. O objetivo é ordenar o vetor $ V = [9, 2, 7, 5, 16, 12, -4] $ em ordem crescente. Vamos usar o último elemento de cada sublista como pivô. Nossa missão é mostrar como o vetor fica depois das três primeiras execuções do método Particiona.
Passo 2
Primeiro, vamos entender o que o método Particiona faz. Ele escolhe um pivô (nossa escolha é o último elemento) e reorganiza a lista de forma que todos os elementos menores que o pivô fiquem à esquerda dele e os maiores à direita. Depois disso, o pivô fica na posição correta na lista ordenada.
Primeira execução do Particiona:
- Vetor inicial:
- Pivô escolhido:
Agora, vamos comparar cada elemento com o pivô:
- 9 é maior que
: fica do lado direito. - 2 é maior que
: fica do lado direito. - 7 é maior que
: fica do lado direito. - 5 é maior que
: fica do lado direito. - 16 é maior que
: fica do lado direito. - 12 é maior que
: fica do lado direito.
Nenhum elemento é menor que o pivô, então o pivô
fica na primeira posição.
- Vetor após a primeira Particiona:
Passo 3
Agora, vamos aplicar o Particiona na parte direita da lista, ou seja, na sublista
.
Segunda execução do Particiona:
- Vetor atual:
- Sublista para particionar:
- Pivô escolhido:
Vamos comparar:
- 2 é menor que
: fica à esquerda. - 7 é menor que
: fica à esquerda. - 5 é menor que
: fica à esquerda. - 16 é maior que
: fica à direita. - 12 é maior que
: fica à direita.
Rearranjando, os menores ficam antes do pivô e os maiores depois.
- Vetor após a segunda Particiona:
Passo 4
Vamos continuar particionando. Agora, focamos na sublista
.
Terceira execução do Particiona:
- Vetor atual:
- Sublista para particionar:
- Pivô escolhido:
Comparando:
- 2 é menor que
: fica à esquerda. - 7 é maior que
: fica à direita.
Após rearranjar:
- Vetor após a terceira Particiona:
Resposta
Depois das três primeiras execuções do método Particiona, o vetor fica assim: