Dada a sequência de números: 349258217462985 1, ordene-a em ordem não decrescente segundo os seguintes algoritmos, apresentando a sequência obtida após cada passo do algoritmo:
QuickSort

Passo 1

Temos a sequência a ser ordenada em ordem não decrescente: [3,4,9,2,5,8,2,1,7,4,6,2,9,8,5,1]. O conteúdo é o algoritmo QuickSort, que resolve ordenação através de partições recursivas. Vamos usar o pivô como o primeiro elemento de cada subvetor e aplicar a partição de Lomuto, movendo elementos menores que o pivô para a esquerda.

Passo 2

Aplicando QuickSort ao subvetor completo (índices 1 a 16): pivô = A[1] = 3. Após a partição de Lomuto a sequência fica [1,2,2,1,2,3,9,4,7,4,6,5,9,8,5,8]. O pivô 3 ficou na posição correta (índice 6).
Agora recursão na parte esquerda (índices 1 a 5): pivô = A[1] = 1. Ao particionar, não há elementos menores que 1, então a sequência permanece [1,2,2,1,2,3,9,4,7,4,6,5,9,8,5,8]. O pivô 1 fixa-se na posição 1.
Recursão em (2 a 5): pivô = A[2] = 2. Após partição obtemos [1,1,2,2,2,3,9,4,7,4,6,5,9,8,5,8]. O pivô 2 foi colocado na posição 3.
Recursão em (4 a 5): pivô = A[4] = 2. Não há elementos menores que 2, sequência inalterada [1,1,2,2,2,3,9,4,7,4,6,5,9,8,5,8]. Pivô 2 fixa-se na posição 4 e essa parte já está ordenada.

Passo 3

Voltando à recursão inicial e aplicando em (7 a 16): pivô = A[7] = 9. Após partição a sequência fica [1,1,2,2,2,3,8,4,7,4,6,5,8,5,9,9]. O pivô 9 ficou na posição 15.
Recursão em (7 a 14): pivô = A[7] = 8. Particionando, obtemos [1,1,2,2,2,3,5,4,7,4,6,5,8,8,9,9]. O pivô 8 fixa-se na posição 13.
Recursão em (7 a 12): pivô = A[7] = 5. Após partição surge [1,1,2,2,2,3,4,4,5,7,6,5,8,8,9,9]. O pivô 5 vai para a posição 9.
Recursão em (7 a 8): pivô = A[7] = 4. Não há menores que 4, sequência inalterada [1,1,2,2,2,3,4,4,5,7,6,5,8,8,9,9].
Recursão em (9 a 12): pivô = A[9] = 5. Aplica partição e fica [1,1,2,2,2,3,4,4,5,5,6,7,8,8,9,9]. A partir daí as chamadas em subvetores triviais não alteram mais a sequência.

Resposta

[1,1,2,2,2,3,4,4,5,5,6,7,8,8,9,9]

Exercícios relacionados