Resolvido: Algoritmos - Teoria e Prática - 3ª Ed. 2012 | Cap 7.1 Ex 1E
50
Algoritmos - Teoria e Prática - 3ª Ed. 2012

Exercícios resolvidos: Algoritmos - Teoria e Prática - 3ª Ed. 2012

Thomas Cormen IBSN: 9788535236996

Elaborado por professores e especialistas

Passo 1 de 17keyboard_arrow_downkeyboard_arrow_up

A operação PARTITION seleciona um elemento como um elemento pivô ao redor do qual o particionamento do arranjo será feito. Para qualquer índice de arranjo temos três condições:

- se então

- se então

- se então

Passo 2 de 17keyboard_arrow_downkeyboard_arrow_up

Consideremos o arranjo dado, . O arranjo tem 12 elementos. Então e . Segue abaixo o vetor inicial:

Passo 3 de 17keyboard_arrow_downkeyboard_arrow_up

Temos abaixo o elemento pivô e as variáveis e

.

Passo 4 de 17keyboard_arrow_downkeyboard_arrow_up

A variável não pode ser maior que , isto é, . Temos então o seguinte arranjo:

Passo 5 de 17keyboard_arrow_downkeyboard_arrow_up

A condição falha, pois e . Então o arranjo não é alterado. Incrementamos , que passa a valer 1. Temos então o arranjo abaixo:

Passo 6 de 17keyboard_arrow_downkeyboard_arrow_up

A condição falha novamente, pois e . Então o arranjo não é alterado. Incrementamos , que passa a valer 2.

Passo 7 de 17keyboard_arrow_downkeyboard_arrow_up

Agora condição é satisfeita, pois e . Então incrementamos que passa a valer 0. E o valor na posição é trocado pelo valor na posição . Depois incrementamos . Assim, temos o seguinte arranjo:

Passo 8 de 17keyboard_arrow_downkeyboard_arrow_up

A condição é satisfeita, pois e . Então incrementamos que passa a valer 1. E o valor na posição é trocado pelo valor na posição . Depois incrementamos . Assim, temos o seguinte arranjo:

Passo 9 de 17keyboard_arrow_downkeyboard_arrow_up

A condição falha, pois e . Então o arranjo não é alterado. Incrementamos , que passa a valer 5. Temos então o arranjo abaixo:

Passo 10 de 17keyboard_arrow_downkeyboard_arrow_up

A condição é satisfeita, pois e . Então incrementamos que passa a valer 2. E o valor na posição é trocado pelo valor na posição . Depois incrementamos . Assim, temos o seguinte arranjo:

Passo 11 de 17keyboard_arrow_downkeyboard_arrow_up

A condição é satisfeita novamente, pois e . Então incrementamos que passa a valer 3. E o valor na posição é trocado pelo valor na posição . Depois incrementamos . Assim, temos o seguinte arranjo:

Passo 12 de 17keyboard_arrow_downkeyboard_arrow_up

A condição é satisfeita, pois e . Então incrementamos que passa a valer 4. E o valor na posição é trocado pelo valor na posição . Depois incrementamos . Assim, temos o seguinte arranjo:

Passo 13 de 17keyboard_arrow_downkeyboard_arrow_up

A condição falha, pois e . Então o arranjo não é alterado. Incrementamos , que passa a valer 9. Temos então o arranjo abaixo:

Passo 14 de 17keyboard_arrow_downkeyboard_arrow_up

A condição agora é satisfeita, pois e . Então incrementamos que passa a valer 5. E o valor na posição é trocado pelo valor na posição . Depois incrementamos . Assim, temos o seguinte arranjo:

Passo 15 de 17keyboard_arrow_downkeyboard_arrow_up

A condição é satisfeita mais uma vez, pois e . Então incrementamos que passa a valer 6. E o valor na posição é trocado pelo valor na posição . Depois incrementamos . Assim, temos o seguinte arranjo:

Passo 16 de 17keyboard_arrow_downkeyboard_arrow_up

Ao incrementarmos , ela passa a ser 11. Assim e o laço se encerra. O valor da posição é trocado pelo valor da posição . Assim, temos o arranjo final após a primeira chamada ao procedimento PARTITION:

Passo 17 de 17keyboard_arrow_downkeyboard_arrow_up

Portanto, esse é o funcionamento do procedimento PARTITION no arranjo dado, retornando a posição do elemento pivô, que é .

Navegar por capítulo

Aprenda agora com os exercícios mais difíceis

R$29,90/mês

Assine o PremiumCancele quando quiser, sem multa

Aproveite também

  • check Todos os materiais compartilhados
  • check Biblioteca com 5.000 livros, escolha 5 por mês
  • check Videoaulas exclusivas
  • check Resumos por tópicos