QuicksortQuicksortProfa. Dra. Ana Paula Appel

HistóriaHistória• Quicksort é um algoritmo recursivo atribuído a Sir

Charles Antony Richard Hoare,• C.A.R. Hoare nasceu em Colombo no Ceilão (hoje

Sri Lanka), de pais britânicos.• Graduou-se na Universidade de Oxford em 1956.• Estudou tradução computacional de linguagens

humanas em visita à Universidade de Moscou, URSS.

• durante os estudos, foi preciso realizar a ordenação de palavras a serem traduzidas. o quicksort foi o algoritmo desenvolvido por Hoare para ordenar as palavras, em 1960, aos 26 anos.

2

HistóricoHistórico• Recebeu o Prêmio Turing da ACM de 1980, por “suas

contribuições fundamentais para a definição e projeto de linguagens de programação”.

• Em 2009, desculpou-se por ter inventado a referência nula.

• É atualmente pesquisador sênior da Microsoft Research em Cambridge, England e professor emérito da Universidade de Oxford.

• There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies.

• The first method is far more dificult.

3

Características e Características e estratégiaestratégia

• Quicksort é um algoritmo recursivo que utiliza a estratégia da divisão e conquista

• Não estável.• Considerada a mais rápida ordenação baseada em

comparações em arranjos.• Na prática, se bem implementado, executa quase

sempre em Θ(n log n). No pior caso pode executar em tempo Θ(n2).

• O núcleo do método está na partição realizada em uma lista a ser ordenada.

• Essa partição rearranja os elementos de uma lista A[p..r] e devolve um índice i em p..r tal que A[p..i-1] < A[i] < A[i+1..r]. O elemento v = A[i] é chamado de pivô.

4

AlgoritmoAlgoritmo1. Iniciar com uma lista L de n itens 2. Escolher um item pivô v, de L3. Particionar L em duas listas não ordenadas, L1 e

L2 1. L1: conterá todas as chaves menores que v2. L2: conterá todas as chaves maiores que v 3. Itens com a mesma chave que v podem fazer parte de L1 ou L24. O pivô v não faz parte de nenhuma das duas listas

4. Ordenar: 1. L1 recursivamente, obtendo a lista ordenada S1 2. L2 recursivamente, obtendo a lista ordenada S2

5. Concatenar S1, v, S2 – produzindo a lista ordenada S

5

AlgoritmoAlgoritmo• O pivô será sempre o primeiro elemento da lista. • Na fase de partição, formaremos duas sub-listas,

L1 e L2• L1 será ordenada recursivamente. • Como foi alcançado o caso base, as listas serão

concatenadas• L2 será ordenada recursivamente. • Como foi alcançado o caso base, as listas serão

concatenadas

6

ParticionamentoParticionamento

7

ParticionamentoParticionamento• O passo principal do algoritmo Quicksort é o

particionamento do vetor. o Um número qualquer pode ser escolhido para pivo, geralmente é o elemento

inicial;o O vetor é dividido em 3 partes:

8

p

Números menores que p

Números maiores ou iguais a p

p

ParticionamentoParticionamento• To partition a[left...right]:

1. Set pivot = a[left], l = left + 1, r = right;2. while l < r, do

2.1. while l < right & a[l] < pivot , set l = l + 12.2. while r > left & a[r] >= pivot , set r = r - 12.3. if l < r, swap a[l] and a[r]

3. Set a[left] = a[r], a[r] = pivot 4. Terminate

9

ParticionamentoParticionamento• Escolha um valor para ser usado como pivo, digamos o

primeiro

• Começe da esquerda para o final e encontre o elemento que é maior ou igual ao pivo

• Faça uma busca de traz para a frente do vetor (direita para o começo) encontre o primeiro elemento que seja menor que o pivo

• Troque os dois elementos

• Repita o processo até não ter mais elemento

10

ExemplosExemplos• Embaralhado• Ordenado• Inverso

12

Escolha PivoEscolha Pivo• É crucial para o bom desempenho do método, já

que a fase de partição é a parte crítica do algoritmo..

• Há várias estratégias possíveis.• Há outras opções como a escolha do elemento

correspondente à mediana da lista, ou ainda o mais próximo da média.

• Para o caso em que se conhece a distribuição dos dados, podemos utilizar a estratégia de escolha do pivô mais adequada àquela distribuição.

• Quando não há conhecimento...

13

Escolha PivoEscolha Pivo• Escolha aleatória• Escolher aleatoriamente um item da lista L como

pivô• Na média teremos uma partição da lista na

proporção: 1/4 e 3/4• É possível provar que, se a partição da lista

ocorrer pelo menos metade das vezes nessa proporção, o tempo de execução esperado é O(nlogn).

14

Escolha PivoEscolha Pivo• Mediana de três• Escolher três elementos aleatoriamente, • Utilizar como pivô o elemento correspondente à

mediana dos três.o Essa estratégia aumenta ainda mais as chances de se obter caso

esperado de O(n log n). o Como há um maior custo em se obter três elementos aleatórios e obter

a mediana, essa estratégia é utilizada apenas em listas grandes. o Quando a lista a ser ordenada tem tamanhos menores, utiliza-se a

escolha aleatória simples.

15

CódigoCódigo

16

Complexidade – Complexidade – Melhor casoMelhor caso

• Se a escolha do pivô divide o arquivo em partes iguais (~meio)

• O vetor de tamanho n é dividido ao meio, cada metade é dividida ao meio, ..., m vezes => m≈O(n log2n)

• Cada parte do vetor realiza n comparações (com n = tamanho da partição atual do vetor)

• Pelo método da árvore de recorrência, tem-se que

• T(n)=O(nlog2n), no melhor caso

17

Pior CasoPior Caso• Se vetor já ordenado com escolha do pivô como

um dos extremos (elemento 0 ou n-1)• Subvetores desiguais, com n chamadas

recursivas da função partição, eliminando-se 1 elemento em cada chamada

• Cada chamada recursiva faz n comparações• T(n)=O(n2), no pior caso• Igual ao bubble-sort

18

Particionamento – Pior CasoParticionamento – Pior Caso

19

Caso MédioCaso Médio• Caso médio (Sedgewick e Flajelot, 1996)• T(n) ≈ 1,386n log2 n – 0,846n = O(n log2 n)

• Um dos algoritmos mais rápidos para uma variedade de situações, sendo provavelmente mais utilizado do que qualquer outro algoritmo

20

DicasDicas• Quase qualquer coisa que você tentar para

"melhorar" Quicksort pode retardá-lo.• Uma boa dica é mudar para um método de

classificação diferentes quando um subvetor for pequeno

• Quicksort tem overhead demais para tamanhos pequenos

• Para vetores de grandes dimensões, pode ser uma boa ideia para verificar com antecedência se o vetor já está classificado

21

Comentários FinaisComentários Finais• Algoritmo mais rápido conhecido

• Para eficiência ótima, o pivo deve ser escolhida cuidadosamente

• A média de três é uma boa técnica para escolher o pivo

• Contudo não importa o que se faça o Quicksort muitas vezes será O(n2)

22