Escreva o vetor resultante ao aplicar o algoritmo de particionamento em duas partes no vetor seguinte: 266545731018789370492322
Passo 1
O enunciado pede para aplicar o algoritmo de particionamento em duas partes (esquema de Lomuto) em um vetor de 24 elementos. Este conteúdo faz parte do passo de particionamento do Quicksort. Para resolver, vamos precisar entender como o algoritmo escolhe um pivô (último elemento do trecho) e desloca os elementos menores ou iguais a ele para a esquerda.
Passo 2
O algoritmo de particionamento de Lomuto funciona assim: dado o vetor
e o pivô
, inicializamos
. Em seguida, para cada
de
até
, se
então fazemos
e trocamos
com
. Ao final do loop, trocamos
com o pivô
, e o pivô fica na posição correta.
Passo 3
No nosso vetor inicial
Passo 4
Por fim, trocamos
com o pivô
. Isso move o pivô para a posição
, e o vetor particionado fica:
Resposta
[2,1,0,1,0,2,2,2,6,6,5,8,7,8,9,3,7,4,4,9,5,3,7,3]