PGINF591 – Algoritmos e Estruturas de Dados

Quick Sort

Prof. Dr. Rafael Giusti

rgiusti@[Link]
Apresentação

» O Quick Sort é um algoritmo de ordenação

baseado em divisão e conquista
» Possui complexidade temporal O(n logn) no
melhor caso e no caso médio
» E complexidade temporal O(n²) no pior caso
» Possui complexidade espacial O(log n) e O(n)
no melhor e no pior casos
» Embora seja quadrático no pior caso, o Quick
Sort é um algoritmo de ordenação com bastante
aplicação prática
Intuição

» Dado um vetor A com tamanho n, o Quick Sort

realiza os seguintes passos
» Divisão
~ Particiona o vetor A em dois subvetores, Ae e
Ad, tais que nenhum elemento de Ae é maior do
que os elementos em Ad e vice-versa
~ Ordena recursivamente Ae
~ Ordena recursivamente Ad
» Conquista
~ Concatena os vetores ordenados Ae e Ad
Intuição
1. Particionamento: os
7 3 6 4 1 2 5 elementos do vetor são
rearranjados em dois sub-
vetores

2 3 1 4 6 7 5
Intuição
1. Particionamento: os
7 3 6 4 1 2 5 elementos do vetor são
rearranjados em dois sub-
vetores

Ae → nenhum elemento maior que 4

2. Ordenação:
12 23 31 4 65 76 57
Ordena Ae recursivamente
Ad → nenhum elemento menor que 4 Ordena Ad recursivamente

3. Conquista: os vetores Ae e
Ad são concatenados
(desnecessário em Python
porque as listas são referências
compartilhadas na recursão)
Algoritmo de particionamento

» O ponto mais importante é o particionamento

» Precisamos de uma estratégia (algoritmo) de
particionamento apropriada (eficiente)
» Essa estratégia deve escolher um pivô e um
ponto de corte
» Um “ponto de sustentação”
» Os elementos à esquerda do ponto de corte
não são maiores que o pivô
» Os elementos à direita não são menores
Algoritmo de particionamento

» O algoritmo de particionamento deve ser

eficiente e também eficaz
» Deve tentar encontrar um ponto de corte tão
próximo do índice central quanto possível
» Deve fazer o menor número de trocas possível

» Duas estratégias relevantes

» Particionamento de Hoare
» Particionamento de Lomuto
Particionamento de Hoare

» Escolhe o valor do elemento central como pivô

» Percorre o vetor com dois índices
» i: o primeiro elemento mais à esquerda que
não é menor do que o pivô
» j: o primeiro elemento mais à direita que não é
maior do que o pivô

2 6 3 4 7 5 1
Particionamento de Hoare

» Escolhe o valor do elemento central como pivô

» Percorre o vetor com dois índices
» i: o primeiro elemento mais à esquerda que
não é menor do que o pivô
» j: o primeiro elemento mais à direita que não é
maior do que o pivô
pivô

2 6 3 4 7 5 1
Particionamento de Hoare

» Escolhe o valor do elemento central como pivô

» Percorre o vetor com dois índices
» i: o primeiro elemento mais à esquerda que
não é menor do que o pivô
» j: o primeiro elemento mais à direita que não é
maior do que o pivô
pivô

2 6 3 4 7 5 1

i
Particionamento de Hoare

» Escolhe o valor do elemento central como pivô

» Percorre o vetor com dois índices
» i: o primeiro elemento mais à esquerda que
não é menor do que o pivô
» j: o primeiro elemento mais à direita que não é
maior do que o pivô
pivô

2 61 3 4 7 5 16

i j

Esses elementos estão do lado errado do pivô… então vamos trocá-los.

Particionamento de Hoare

» Escolhe o valor do elemento central como pivô

» Percorre o vetor com dois índices
» A forma como o vetor é percorrido é importante
» i: começa em 0 (ou -1) e incrementa até
encontrar o elemento fora de posição
» j: começa em n + 1 (ou n) e decrementa até
encontrar o elemento fora de posição
» O particionamento termina quando i ≥ j
» O ponto de corte será o índice j
Particionamento de Hoare

j=8

3 6 5 4 1 7 2

i=0

Cheatsheet:
Variável i: começa em zero e incrementa até encontrar um valor que
não é menor do que o pivô
Variável j: começa em n + 1 e decrementa até encontrarmos um
valor não é maior do que o pivô

Troca:
Se i < j, então os elementos A[i] e A[j] são trocados

Término:
Quando i ≥j, o índice j será o ponto de corte
Particionamento de Hoare

4 j=8

pivô
3 6 5 4 1 7 2

i=0

Cheatsheet:
Variável i: começa em zero e incrementa até encontrar um valor que
não é menor do que o pivô
Variável j: começa em n + 1 e decrementa até encontrarmos um
valor não é maior do que o pivô

Troca:
Se i < j, então os elementos A[i] e A[j] são trocados

Término:
Quando i ≥j, o índice j será o ponto de corte
Particionamento de Hoare

4 j=8

pivô
3 6 5 4 1 7 2

i=1

Cheatsheet:
Variável i: começa em zero e incrementa até encontrar um valor que
não é menor do que o pivô
Variável j: começa em n + 1 e decrementa até encontrarmos um
valor não é maior do que o pivô

Troca:
Se i < j, então os elementos A[i] e A[j] são trocados

Término:
Quando i ≥j, o índice j será o ponto de corte
Particionamento de Hoare

4 j=8

pivô
3 6 5 4 1 7 2

i=2

Cheatsheet:
Variável i: começa em zero e incrementa até encontrar um valor que
não é menor do que o pivô
Variável j: começa em n + 1 e decrementa até encontrarmos um
valor não é maior do que o pivô

Troca:
Se i < j, então os elementos A[i] e A[j] são trocados

Término:
Quando i ≥j, o índice j será o ponto de corte
Particionamento de Hoare

4 j=7

pivô
3 62 5 4 1 7 26

i=2

Cheatsheet:
Variável i: começa em zero e incrementa até encontrar um valor que
não é menor do que o pivô
Variável j: começa em n + 1 e decrementa até encontrarmos um
valor não é maior do que o pivô

Troca:
Se i < j, então os elementos A[i] e A[j] são trocados

Término:
Quando i ≥j, o índice j será o ponto de corte
Particionamento de Hoare

4 j=7

pivô
3 2 5 4 1 7 6

i=3

Cheatsheet:
Variável i: começa em zero e incrementa até encontrar um valor que
não é menor do que o pivô
Variável j: começa em n + 1 e decrementa até encontrarmos um
valor não é maior do que o pivô

Troca:
Se i < j, então os elementos A[i] e A[j] são trocados

Término:
Quando i ≥j, o índice j será o ponto de corte
Particionamento de Hoare

4 j=6

pivô
3 2 5 4 1 7 6

i=3

Cheatsheet:
Variável i: começa em zero e incrementa até encontrar um valor que
não é menor do que o pivô
Variável j: começa em n + 1 e decrementa até encontrarmos um
valor não é maior do que o pivô

Troca:
Se i < j, então os elementos A[i] e A[j] são trocados

Término:
Quando i ≥j, o índice j será o ponto de corte
Particionamento de Hoare

4 j=5

pivô
3 2 15 4 51 7 6

i=3

Cheatsheet:
Variável i: começa em zero e incrementa até encontrar um valor que
não é menor do que o pivô
Variável j: começa em n + 1 e decrementa até encontrarmos um
valor não é maior do que o pivô

Troca:
Se i < j, então os elementos A[i] e A[j] são trocados

Término:
Quando i ≥j, o índice j será o ponto de corte
Particionamento de Hoare

4 j=5

pivô
3 2 1 4 5 7 6

i=4

Cheatsheet:
Variável i: começa em zero e incrementa até encontrar um valor que
não é menor do que o pivô
Variável j: começa em n + 1 e decrementa até encontrarmos um
valor não é maior do que o pivô

Troca:
Se i < j, então os elementos A[i] e A[j] são trocados

Término:
Quando i ≥j, o índice j será o ponto de corte
Particionamento de Hoare

4 j=4

pivô
3 2 1 4 5 7 6

i=4

Cheatsheet:
Variável i: começa em zero e incrementa até encontrar um valor que
não é menor do que o pivô
Variável j: começa em n + 1 e decrementa até encontrarmos um
valor não é maior do que o pivô

Troca:
Se i < j, então os elementos A[i] e A[j] são trocados

Término:
Quando i ≥j, o índice j será o ponto de corte
Particionamento de Hoare

4 j=4

pivô
3 2 1 4 5 7 6

j = 4 é o ponto de corte
i=4

Cheatsheet:
Variável i: começa em zero e incrementa até encontrar um valor que
não é menor do que o pivô
Variável j: começa em n + 1 e decrementa até encontrarmos um
valor não é maior do que o pivô

Troca:
Se i < j, então os elementos A[i] e A[j] são trocados

Término:
Quando i ≥j, o índice j será o ponto de corte
Particionamento de Hoare

4
pivô
3 2 1 4 5 7 6

j = 4 é o ponto de corte

Cheatsheet:
Variável i: começa em zero e incrementa até encontrar um valor que
não é menor do que o pivô
Variável j: começa em n + 1 e decrementa até encontrarmos um
valor não é maior do que o pivô

Troca:
Se i < j, então os elementos A[i] e A[j] são trocados

Término:
Quando i ≥j, o índice j será o ponto de corte
Particionamento de Hoare

E na metade direita
também
4
pivô
3 2 1 4 5 7 6

j = 4 é o ponto de corte
QuickSort na metade
esquerda!
Particionamento de Hoare

» Algoritmo Hoare(A)

meio ← ⌈|A|/2⌉, pivô ← A[meio]

i ← 0, j ← |A| + 1

repita incondicionalmente

faça i ← i + 1 enquanto A[i] < pivô

faça j ← j - 1 enquanto A[j] > pivô

se i < j

troque A[i] ↔ A[j]

senão

retorne j
Ordenação com QuickSort e particionamento de Hoare

» Algoritmo QuickSort(A)

se |A| > 1

pontoCorte ← Hoare(A)

esq ← QuickSort(A[1..pontoCorte])

dir ← QuickSort(A[pontoCorte+1..|A|])

A ← concatena(esq, dir)

retorna A
Complexidade do Quick Sort

» O melhor caso acontece quando o ponto de corte

sempre termina no meio do vetor

8 2 1 4 5 7 3
Complexidade do Quick Sort

» O melhor caso acontece quando o ponto de corte

sempre termina no meio do vetor

8 2 1 4 5 7 3

3 2 1 4 5 7 8
Complexidade do Quick Sort

» O melhor caso acontece quando o ponto de corte

sempre termina no meio do vetor

8 2 1 4 5 7 3

3 2 1 4 5 7 8

1 2 3 4
Complexidade do Quick Sort

» O melhor caso acontece quando o ponto de corte

sempre termina no meio do vetor

8 2 1 4 5 7 3

3 2 1 4 5 7 8

1 2 3 4

1 2
Complexidade do Quick Sort

» O melhor caso acontece quando o ponto de corte

sempre termina no meio do vetor

8 2 1 4 5 7 3

3 2 1 4 5 7 8

1 2 3 4

1 2 3 4
Complexidade do Quick Sort

» O melhor caso acontece quando o ponto de corte

sempre termina no meio do vetor

8 2 1 4 5 7 3

3 2 1 4 5 7 8

1 2 3 4 5 7 8

1 2 3 4
Complexidade do Quick Sort

» O melhor caso acontece quando o ponto de corte

sempre termina no meio do vetor

8 2 1 4 5 7 3

3 2 1 4 5 7 8

1 2 3 4 5 7 8

1 2 3 4 7 8
Complexidade do Quick Sort

» O pior caso acontece quando o ponto de corte

sempre termina no primeiro ou no último índice

8 7 3 1 5 6 2
Complexidade do Quick Sort

» O pior caso acontece quando o ponto de corte

sempre termina no primeiro ou no último índice

8 7 3 1 5 6 2

1 7 3 8 5 6 2
Complexidade do Quick Sort

» O pior caso acontece quando o ponto de corte

sempre termina no primeiro ou no último índice

8 7 3 1 5 6 2

1 7 3 8 5 6 2

7 3 2 5 6 8
Complexidade do Quick Sort

» O pior caso acontece quando o ponto de corte

sempre termina no primeiro ou no último índice

8 7 3 1 5 6 2

1 7 3 8 5 6 2

7 3 2 5 6 8

2 3 7 5 6
Complexidade do Quick Sort

» O pior caso acontece quando o ponto de corte

sempre termina no primeiro ou no último índice

8 7 3 1 5 6 2

1 7 3 8 5 6 2

7 3 2 5 6 8

2 3 7 5 6
Complexidade do Quick Sort

» QuickSort: melhor caso e pior caso

» No melhor caso, a entrada é divida em dois sub-
-problemas de tamanhos [quase] iguais
» No pior caso, a entrada é divida em um sub-problema
com tamanho 1 e um sub-problema com tamanho n-1
» Para fazer:
» Monte a relação de recorrência do QuickSort no melhor
e no pior casos
» Analise, pelo método da árvore, as complexidades