Algoritmos de Particionamento

Algortimos de particionamento dividem uma lista de dados de acordo com um critério estabelecido. Normalmente, este critério é um valor, chamado de pivot, e a divisão é realizada entre os valores menores que o pivot e os maiores. O resultado destes algoritmos é a lista original modificada (pela reorganização dos elementos) e um (ou mais) índice(s) que representam a posição onde a lista de dados foi dividida. Variações do algoritmo podem incluir a criação de listas independentes, ao invés do indíce e da lista reorganizada.

Particionamento de Lomuto

Este esquema de particionamento, atribuído a Nico Lomuto, normalmente, escolhe o último elemento da lista de elementos como pivot, e mantém o controle sobre o elemento que irá dividir a lista em elementos maiores e menores que o pivot.

No algoritmo apresentado (Algoritmo 1) índice retornado marca o início dos valores maiores que o pivot. Outra característica deste particionamento é que o pivot utilizado para dividir a lista estará na posição indicada pelo índice retornado.

Esquema de particionamento de Lomuto

lomuto_partition(data, start, end)
    pivot = data[end]
    i = start
    for j = start to end-1
        if data[j] <= pivot
            swap(data[i], data[j])
            i = i + 1
    swap(data[i],data[end])
    return i

Este esquema de particionamento é o mais simples de implementar e pode ser alterado para qe o pivot seja fornecido e não obtido a partir dos dados.

Particionamento de Hoare

O Particionamento de Hoare (Algoritmo 2) varre a lista a ser dividida a partir dos dois extremos, comparando cada valor com o pivot. Quando encontra valores que deveriam estar na metade oposta (um valor maior que o pivot na lista dos menores e um valor menor que o pivot na lista dos maiores) o algoritmo troca os elementos de lugar e reinicia o processo. Ao final o algoritmo retorna a posição que marca o final da sub-lista de elementos menores que o pivot.

Apesar de um pouco mais complexo, o particionamento de Hoare tende a ser mais eficiente que o particionamento de Lomuto, executando, na média, três vezes menos trocas, e realiza um particionamento mais equilibrado quando existem valores iguais ao pivot.

Esquema de particionamento de Hoare

hoare_partition(data, start, end)
    pivot = data[start]
    i = start - 1
    j = end + 1
    while true
        do
            i = i + 1
        while data[i] < pivot
        do
            j = j - 1
        while data[j] > pivot
        if i >= j then
            return j
        swap(data[i],data[j])

Em sua versão original, na presença de valores iguais ao pivot, estes podem estar em qualquer uma das listas (dos menores ou dos maiores). Por exemplo, utilizando-se a lista \(\langle 4,3,2,3,2,5,5,4 \rangle\), que ao ser particionada com o pivot 4, gerará as listas \(\langle 4,3,2,3,2 \rangle\) e \(\langle 5,5,4 \rangle\). Note que nenhum valor na lista dos menores é maior que o pivot, e nenhum valor na lista dos maiores é menor que o pivot.

Existem diversas variações do particionamento de Hoare. Uma variação comum é utilizar um valor de pivot provido externamente, uma vez que este valor pode ser calculado de forma a criar listas de tamanho mais equilibradas, o que melhora a eficiência de algoritmos que esperam que a divisão da lista crie listas com aproximadamente a metade do tamanho original, como os algoritmos Quicksort e o Quickselect.

Particionamento de Dijkstra

O Problema da Bandeira Holandesa é um problema proposto por Edsger Dijkstra, que consiste em organizar um conjunto de elementos que podem ter três valores (vermelho, branco e azul), organizados em uma lista e distribuídos randômicamente, de forma que os elementos com o mesmo valor fiquem agrupados e na ordem correta.A solução deste problema pode ser aplicada ao particionamento de elementos em maiores, menores e iguais a um pivot, e o resultado deste particionamento utilizado em algoritmos de ordenação.

A vantagem em utilizar este tipo de particionamento é que na presença de diversos valores iguais ao pivot, eles ficarão agrupados, não sendo necessários ordená-los novamente.

Existem diversas soluções para o problema proposto, e a apresentada aqui (Algoritmo 3), assume vetores com indexamento de base 0 (zero), e utiliza três índices (\(i\), \(j\) e \(n\)). O índice \(i\) marca o último elemento menor que o pivot, o índice \(n\), o primeiro elemento maior que o pivot, e o índice \(j\) marca a posição do elemento sendo analizado.

Particionamento de Dijkstra

tree-way-partition (data, start, end, pivot)
    i = j = start
    n = end;

    while j <= n
        if data[j] < pivot
            swap(data[i],data[j])
            i = i + 1
            j = j + 1
        else if data[j] > pivot
            swap(data[j],data[n])
            n = n - 1
        else
            j++;
    return i, n