QuickSort

No QuickSort, escolhemos um elemento arbitrá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 (reorganização) dos elementos do arranjo em torno do pivô.

  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:

Tabela 1. Mergesort versus Quicksort
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, para fazer isso, criaremos duas variáveis, i e j, que serão usadas para percorrer o arranjo de entrada, da seguinte forma:

  • Percorremos cada posição i do arranjo, da esquerda para a direita, até encontrarmos um elemento maior que o pivô.

  • Percorremos cada posição j do arranjo, da direita para a esquerda, até encontrarmos um elemento menor que o pivô.

  • Trocamos os elementos nas posições i e j do arranjo.

  • Quando as variáveis i e j se cruzarem, colocamos o pivô na posição j do arranjo, pois essa será a posição correta dele.

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].
    pivo = A[esquerda]
    # Particionamento do arranjo.
    i = esquerda
    j = direita
    while i <= j:
        # Encontra elemento maior que o pivo.
        while A[i] <= pivo:
            i += 1
            if i == direita:
                break

        # Encontra elemento menor que o pivo.
        while pivo <= 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.
    pivo, A[j] = A[j], pivo

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

O procedimento acima executa em $O(n)$ 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.

Note que os elementos não precisam ser colocados na ordem correta nesta etapa da execução do algoritmo. Isso será feito posteriormente. Tudo que precisamos fazer é elementos menor que o pivô à esquerda dele e colocar elementos maiores que o pivô à direita dele.

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 $O(n^2)$, ao invés de $O(n \log n)$ 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 $O(n^2)$ no número de elementos do vetor de entrada, complexidade $O(n \log n)$ 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.

Na verdade, esta é a grande vantagem do Quicksort sobre o Mergesort: ambos executam em $O(n log n)$, mas o Quicksort executa in-place, ao passo que o Mergesort usa um vetor auxiliar do tamanho do vetor de entrada.

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

Agora que já explicamos como funciona o Quicksort, gostaríamos de fornecer uma versão simples (porém ineficiente) deste algoritmo. É interessante ter essa versão em mente se você precisa implementar o Quicksort rapidamente.

def quicksort(A):
    if len(A) == 0: return A
    pivot = A[0]
    frente = quicksort([menor for menor in A[1:] if menor <= pivo])
    tras   = quicksort([maior for maior in A[1:] if maior > pivo])
    return frente + [pivo] + tras

Esta implementação é ineficiente por dois motivos.

Primeiro, ela gera novas listas de forma desnecessária. E ela faz isso em três pontos: quando está gerando as listas frente, tras e quando está recriando a lista de entrada A a partir de frente e tras. Em outras palavras, o procedimento de partição não é in-place.

Segundo, esta implementação é ineficiente porque ela passa duas vezes pelo arranjo de entrada, uma para gerar a lista frente e outra para gerar a lista tras, o que é descenessário.

Entretanto, como dissemos, se você precisa de uma implementação simples do Quicksort, é interessante ter essa versão que acabamos de mostrar em mente.

Playground

# Use este espaço para praticar o que você aprendeu nesta seção. # Basta digitar o código no espaço abaixo e clicar 'run'.
Anterior Início Próximo