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 A[0dots n-1] e o pivô p = A[n-1], inicializamos i = -1. Em seguida, para cada j de 0 até n-2), se A[j] <= p então fazemos i i+1 e trocamos A[i] com A[j]. Ao final do loop, trocamos A[i+1] com o pivô A[n-1], e o pivô fica na posição correta.

Passo 3

No nosso vetor inicial
A = [2,6,6,5,4,5,7,3,1,0,1,8,7,8,9,3,7,0,4,9,2,3,2,2] o pivô é p = 2. Percorremos de j=0 até 22 e, sempre que A[j]<=2, incrementamos i e trocamos. Os índices j que satisfazem A[j]<=2 são 0 (2), 8 (1), 9 (0), 10 (1), 17 (0), 20 (2) e 22 (2). Após cada troca, os primeiros 7 elementos ficam sendo os que são <=2. Ao final do loop temos i = 6.

Passo 4

Por fim, trocamos A[i+1] = A[7] com o pivô A[23]. Isso move o pivô para a posição 7, e o vetor particionado fica:
[2,1,0,1,0,2,2,2,6,6,5,8,7,8,9,3,7,4,4,9,5,3,7,3]

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]

Exercícios relacionados