QuickSort

No QuickSort, escolhemos um elemento aleatório (que chamamos de pivô), e particionamos o arranjo de entrada de modo que todos os elementos menores que o pivô apareçam antes dele no arranjo e os elementos maiores que ele apareçam depois dele no arranjo. Assim, o Quicksort pode ser dividida em três etapas:

  1. Seleção do pivô.
  2. Particionamento do arranjo.
  3. Ordenação recursiva das partes obtidas no passo anterior.

Os passos acima podem ser traduzidos para código da seguinte forma:

def particao(A, esquerda, direita):
    # 1. Seleção do pivô.
    # 2. Particionamento do arranjo.

def quicksort(A, esquerda, direita):
    if esquerda < direita:
        indice_pivo = particao(A, esquerda, direita)
        # 3. Ordenação recursiva das partes do arranjo.
        quicksort(A, esquerda, indice_pivo - 1)
        quicksort(A, indice_pivo + 1, direita)

No código acima, não mostramos como o pivô é selecionado nem como a partição é feita. Explicaremos essas coisas depois. Nosso objetivo com o código acima é mostrar que o procedimento do Quicksort em si é muito simples: ele simplesmente invoca o procedimento particao e realiza chamadas recursivas de si mesmo em arranjos de tamanhos menores. Ao analisar o código, é possível perceber que o trabalho duro do Quicksort é realizado pelo procedimento particao. Essa situação é semelhante ao caso do Mergesort, em que o trabalho maior do algoritmo é realizado no procedimento que faz o merge de dois arranjos ordenados. Entretanto, no Mergesort, primeiro dividimos o arranjo recursivamente e depois realizamos o trabalho maior de combinar (procedimento merge) dos sub-arranjos, ao passo que no Quicksort primeiro realizamos o trabalho maior (no procedimento particao) e depois dividimos o arranjo original em sub-arranjos. Resumindo:

Mergesort   Quicksort
Trabalho maior: merge   Trabalho maior: particao
Recursão é feita antes   Recursão é feita depois

Antes de explicar como o pivô pode ser escolhido e como sua escolha afeta o desempenho do Quicksort, explicaremos como o procedimento particao funciona.

O procedimento particao é responsável por organizar os elementos do arranjo de entrada de modo que todos os elementos menores que o pivô apareçam antes dele no arranjo e os elementos maiores que ele apareçam depois dele no arranjo. Mais especificamente, criaremos duas variáveis, i e j, que serão usadas para percorrer o arranjo de entrada, da seguinte forma:

Para simplificar as coisas, vamos assumir que o pivô será o primeiro elemento do arranjo. Mostramos abaixo uma implementação dessa ideia.

def particao(A, esquerda, direita):
    # 1. Seleção do pivô. O pivô será o elemento A[esquerda].

    # Particionamento do arranjo.
    i = esquerda
    j = direita
    while i <= j:
        # Encontra elemento maior que o pivo.
        while A[i] <= A[esquerda]:
            i += 1
            if i == direita:
                break

        # Encontra elemento menor que o pivo.
        while A[esquerda] <= A[j]:
            j -= 1
            if j == esquerda:
                break
        
        # Ponteiros i e j se cruzaram.
        if i >= j:
            break
        
        # Troca elementos encontrados acima de lugar.
        A[i], A[j] = A[j], A[i]
    
    # Coloca o pivo no lugar certo.
    A[esquerda], A[j] = A[j], A[esquerda]

    # j é o índice em que o pivo agora está.
    return j

O procedimento acima executa em e particiona o arranjo de entrada de modo que elementos menores que o pivô fiquem à esquerda dele e elemento maiores que o pivô fiquem à direita dele.

Entretanto, ao analisarmos com cuidado a implementação do procedimento particao, vemos que ele é extremamente sensível à escolha do pivô. Por exemplo, suponha que o pivô escolhido seja o menor elemento do arranjo. Neste caso, ao aplicar o procedimento particao, todos os elementos serão maiores que o pivô, e portanto serão movidos para a direita dele. Na verdade, esse problema afeta a complexidade do Quicksort como um todo. Para esse pior caso da escolha do pivô, a complexidade assintótica do Quicksort acaba sendo , ao invés de se escolhermos melhor o pivô.

Uma forma de se reduzir as chances de cair no pior caso da escolha do pivô é simplesmente embaralhar os elementos do arranjo de entrada antes de escolher o pivô. Outra alternativa é selecionar três elementos aleatórios do arranjo, computar a mediana desses elementos, e selecionar essa mediana como pivô. Na prática, computamos a mediana do primeiro elemento do arranjo, do elemento do meio, e do último elemento do arranjo. Uma implementação do Quicksort usando essa técnica seria como a mostrada abaixo:

def quicksort(A, esquerda, direita):
    if esquerda >= direita:
        return
    
    # Calcula a mediana de três elementos.
    m = mediana_de_tres(A, esquerda, (direita - esquerda) / 2, direita)
    # Usa a mediana calculada como pivô.
    A[esquerda], A[m] = A[m], A[esquerda]
    
    indice_pivo = particao(A, esquerda, direita)
    quicksort(A, esquerda, indice_pivo - 1)
    quicksort(A, indice_pivo + 1, direita)

No pior caso, o Quicksort possui complexidade no número de elementos do vetor de entrada, complexidade no caso médio. Ele não é um algoritmo estável, mas é in-place, pois não usa um vetor auxiliar durante sua execução.

Se você quiser acompanhar visualmente a execução do Quicksort, veja o excelente vídeo abaixo, feito pelo pessoal do site Algo-rythmics: