O quicksort foi inventado por C.A.R. Hoare em 1960 e é muito rápido em geral, mas é lento em algumas raras instâncias especiais. O algoritmo tem complexidade de ordem em média e a no pior caso.
Vamos começar com a análise da seguinte versão.
Quick-Sort
Quicksort Dado um vetor A de números inteiros Devolve os elementos de A em ordem não decrescente. 1 se (|A|= 1) então devolva(A) 2 senão 3 seja x o primeiro elemento em A 4 para cada (y diferente de x em A) 5 se (y < x) então coloque y em 6 senão se (y > x)coloque y em 7 senão coloque y em 8 ordene, recursivamente, e 9 devolva (,,)
O custo para ordenar o vetor é o custo para a criação dos subvetores , que é proporcional ao número de comparações das linhas 6 e 7 do algoritmo, ou seja , mais o custo para ordenar os subvetores , que é . Notemos que não há nenhuma garantia a respeito dos tamanhos dos subvetores, por isso começaremos analisando dois casos extremos: (1) e e (2) .
No primeiro caso,
para aluma
de modo que obtemos (verifique usando indução). Por outro lado, se então
de modo que obtemos (verifique).
De fato, se pensamos na árvore de recursão do quicksort percebemos que para garantir tempo é suficiente garantir que as subsequências geradas no pivotamento (linhas 3–7) tenham sempre uma fração constante do tamanho da sequência que as origina; nesse caso o número de instruções executadas em cada nível da recursão é , que é o custo do pivotamento em cada subvetor, e a árvore tem altura , portanto, o custo final é . De fato, a recorrência para o número de intruções executadas é
que é uma função limitada assintoticamente superiomente por . Por exemplo, se sempre tem 10% do tamanho de então o tempo gasto pelo quicksort numa instância de tamanho é cuja solução é assintoticamente limitada por .
Exercício 1 Prove que é .
Abaixo significa que para todo vale .
— Pivotamento —
O processamento feito nas linhas 3 até 7 é chamado de pivotamento e é chamado de pivô. O problema do pivotamento é
Dado um vetor de inteiros com Devolve e os elementos de rearranjados de modo que
No final do pivotamento o pivô está na sua posição correta (a posição no vetor com os elementos já ordenados) os elementos de são todos menores ou iguais a e o de maiores ou iguais a .
Usamos para denotar troca do conteúdo das posições do vetor e usamos // comentário // para comentários no pseudocógido (texto que não é instrução do algoritmo), e os comentários no algoritmo abaixo são proposições que são verdadeiras naquele momento da execução.
Partição
Partição (A,i,f) Dado um vetor de inteiros, com Devolve e uma permutação de tal que 1 e <- i; d <- f+1; x<- A[e] 2 Repita { 3 // // 4 Repita d <- d-1 Até que (A[d] <= x) //// 5 Repita e <- e+1 Até que (A[e] >= x) //// 6 Se ( e < d ) A[e] <-> A[d] 7 Senão devolva(d) }
Na última rodada do laço da linha 2 pode terminar de duas maneiras: ou . De fato, na última rodada
- e em não ocorre ; nesse caso o conteúdo desse subvetor, , é uma sequência de números seguida de uma sequência de números . Nessa condição a variável é decrementada até encontrar um elemento do vetor e, em seguida, a variável é incrementada até encontrar um elemento do vetor o qual está a direita de , isto é, ;
- e em ocorre um único ; nesse caso é decrementada até encontrar e, em seguida, é incrementada até que encontre , assim o laço termina com .
Se então, no pior caso, e o número total de vezes que as linhas 4 e 5 são executadas é : se todas as posições do vetor, exceto e foram comparadas 1 vez com nas linhas 4 e 5, as posições foram comparadas 2 vezes; se todas as posições do vetor, exceto foram comparadas 1 vez com nas linhas 4 e 5 e a posição foi comparada 2 vezes.
No pior caso são executadas as instruções iniciais da linha 1, a linha 2 é executada vezes, essas duas linhas contribuem com instuções. A linhas 4 e 5 são compostas por 3 instruções executadas num total de vezes, portanto, essas linhas contribuem com instruções. A comparação da linha 6 é executada do máximo vezes e as trocas no máximo vezes, sendo que cada troca é composta por 3 instruções, a linha 7 é executada 1 vez, portanto, são instruções.
Teorema 1 O número de instruções executadas no pior caso pelo Partição para um vetor com itens é .
Exercício 2 Mostre que durante toda a execução do algoritmo acima as propriedades nos cometários (entre // //) valem no momento em que o fluxo de instrução passa por elas.
Exercício 3 Prove que ao final da execução do algoritmo de pivotamento vale que .
— Quicksort —
O algoritmo de ordenação está descrito a seguir, nele assumimos que cada instância tem dois sentinelas nos seus extremos e .
QuickSort (A,i,f)
QuickSort (A,i,f) Dado um vetor de inteiros. Devolve com seus elementos ordenados. 1 Se ( i < f ) 2 { q <- Partição (A,i,f) 3 Quicksort (A,i,q-1) 4 Quicksort (A,q+1,f) }
Para ordenar o vetor a chamada inicial se dá como Quicksort(A,1,n).
Exercício 4 Submeta um vetor crescente com itens ao Quicksort. Mostre que o algoritmo consome tempo proporcional a .
— Análise de pior caso —
Vimos acima que o número de instruções para Partição com uma entrada de tamanho é no máximo em que é o número máximo de comparações feitas entre elementos do vetor . No que segue usaremos o número de comparações efetuadas entre elementos da entrada como parâmetro para estimar o custo do Quicksort.
A complexidade de tempo de pior caso é proporcional ao número de comparações entre elementos de executadas que, no pior caso, é
Lembremos que se supormos o caso da árvore de recursão longa então temos uma árvore de altura aproximadamente em que cada nível são executados aproximadamente instruções, portanto, a complexidade de pior caso é . Alternativamente, iterando a recorrência (1) vemos , pois podemos assumir , ou seja, .
Vamos provar usando indução que para alguma constante positiva e todo suficientemente grande. Tomamos e .
Temos , . Assumamos, para a hipótese da indução, que para todo , . Dessa forma, para e todo
Portanto, o Quicksort tem complexidade de pior caso . Pelo exercício 4, para todo há uma instância com complexidade , logo o pior caso é .
Teorema 2 O número de instruções executadas no pior caso pelo Quicksort para ordenar um vetor com itens é .
Exercício 5 Verifique que para todo .
— Análise de caso médio —
Para análise do caso médio assumiremos que as entradas de tamanho são todas as permutações de , assim na primeira etapa qualquer um dos elementos é o pivô com probabilidade , e assim sucessivamente nas próximas etapas, de modo que para
Pra resolver essa recorrência consideramos para todo
subtraindo a segunda da primeira temos
que é equivalente a
então
e reescrevemos (2) como
que itera como
Deixaremos como exercício mostrar que . Assumindo esse fato temos, por (3)
Um defeito dessa análise é que ela não revela a distribuição de , ou seja, embora a média seja não sabemos dizer o quando o comportamento típico desvia da média. Para dar um exemplo simplificado desse fato, uma loteria que com probabilidade dá um prêmio de e com probabilidade dá um prêmio de tem ganho médio de aproximadamente mas um prêmio típico é de .
— Quicksort probabilístico —
Quicksort probabilístico Dado um vetor de números Devolve os elementos de ordem crescente. 1 se () devolva() 2 senão 3 seja um elemento escolhido ao acaso em 4 para cada , , 5 se () então coloque em 6 senão se () coloque em 7 senão coloque em 8 ordene, recursivamente, e 9 devolva ().
O pivotamento de nas linhas 3, 4, 5 e 6 do algoritmo acima, é considerado um sucesso se , caso contrário, dizemos que o particionamento foi um fracasso. Não há nada de especial na escolha de . Discutimos acima que se uma proporção for mantida no particionamento, digamos que a menor parte tem uma fração da entrada, então a recorrência para constantes tem solução .
Assim, cada particionamento é um experimento de Bernoulli com parametro . Um sucesso ocorre se não é um elemento dentre os 10% maiores elementos de nem um dos elementos dentre os 10% menores, ou seja, 80% dos elementos de são boos escolhas para , portanto, a probabilidade de sucesso é de .
Exercício 6 Mostre que um elemento da entrada participa de no máximo particionamentos com sucesso.
Consideremos uma execução do quicksort com entrada . Seja o número de comparações entre o elemento da entrada e algum pivô durante toda uma execução do algoritmo. Em cada particionamento é comparado uma única vez (com o pivô); notemos que se é escolhido pivô então ele nunca mais participará de um particionamento e nunca mais será comparado com outro elemento de . Assim, o número total de comparações durante toda execução é .
Fixemos . Se é o número de particionamentos ocorridos entre o -ésimo particionamento com sucesso (exclusive) do qual participa e o próximo particionamento com sucesso (inclusive) do qual participa, então
em que , logo . Ainda, pelo exercício 2 um elemento da entrada participa de no máximo particionamentos com sucesso, logo
Com isso, provamos o seguinte.
Lema 1 O número esperado de comparações numa execução do quicksort aleatorizado sobre uma entrada com elementos é .
É sabido, da Análise de Algoritmos [CLR] que todo algoritmo de ordenação baseado em comparação faz no mínimo da ordem de comparações para ordenar elementos, ou seja, em média o quicksort aleatorizado é o melhor possível. Porém, saber que um algoritmo é bom em média, não nos garante que ele é bom quase-sempre. Vamos mostrar que com alta probabilidade o desempenho do algoritmo está próximo da média, isto é, para quase-toda instância o número de comparações está próximo da média (e bem longe do pior caso). Vamos provar o seguinte resultado.
Teorema 3 O número de comparações numa execução do quicksort aleatorizado com uma entrada de tamanho é com probabilidade
Demonstração: Definimos
e consideramos o evento , ou seja, segundo (4) foi comparado mais do que quatro vezes o valor esperado para o número de comparações realizadas pelo algoritmo entre e os pivôs. Teremos se em particionamentos ocorrem menos que sucessos, ou seja, o número de fracassos em particionamentos é pelo menos
Seja o número de particionamentos com fracasso pelos quais passa em particionamentos. Então, com . Vamos estimar a probabilidade do evento , com isso, teremos uma estimativa para a probabilidade de . A probabilidade de ocorrerem fracassos em experimentos é , portanto,
mas
assim,
Portanto, a probabilidade de existir com é
logo, com probabilidade vale que para todo e que, com essa probabilidade, quicksort aleatorizado executa comparações entre elementos da entrada.