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: [9, 2, 7, 5, 16, 12, -4]
  • Pivô escolhido: -4
Agora, vamos comparar cada elemento com o pivô:
  1. 9 é maior que -4: fica do lado direito.
  2. 2 é maior que -4: fica do lado direito.
  3. 7 é maior que -4: fica do lado direito.
  4. 5 é maior que -4: fica do lado direito.
  5. 16 é maior que -4: fica do lado direito.
  6. 12 é maior que -4: fica do lado direito.
Nenhum elemento é menor que o pivô, então o pivô -4 fica na primeira posição.
  • Vetor após a primeira Particiona: [-4, 2, 7, 5, 16, 12, 9]

Passo 3

Agora, vamos aplicar o Particiona na parte direita da lista, ou seja, na sublista [2, 7, 5, 16, 12, 9].
Segunda execução do Particiona:
  • Vetor atual: [-4, 2, 7, 5, 16, 12, 9]
  • Sublista para particionar: [2, 7, 5, 16, 12, 9]
  • Pivô escolhido: 9
Vamos comparar:
  1. 2 é menor que 9: fica à esquerda.
  2. 7 é menor que 9: fica à esquerda.
  3. 5 é menor que 9: fica à esquerda.
  4. 16 é maior que 9: fica à direita.
  5. 12 é maior que 9: fica à direita.
Rearranjando, os menores ficam antes do pivô e os maiores depois.
  • Vetor após a segunda Particiona: [-4, 2, 7, 5, 9, 12, 16]

Passo 4

Vamos continuar particionando. Agora, focamos na sublista [2, 7, 5].
Terceira execução do Particiona:
  • Vetor atual: [-4, 2, 7, 5, 9, 12, 16]
  • Sublista para particionar: [2, 7, 5]
  • Pivô escolhido: 5
Comparando:
  1. 2 é menor que 5: fica à esquerda.
  2. 7 é maior que 5: fica à direita.
Após rearranjar:
  • Vetor após a terceira Particiona: [-4, 2, 5, 7, 9, 12, 16]

Resposta

Depois das três primeiras execuções do método Particiona, o vetor fica assim:
[-4, 2, 5, 7, 9, 12, 16]

Exercícios relacionados