Quicksort com pivô aleatório

Por
| 

A escolha do pivô é um dos grandes desafios ao implementar o Quicksort. Podemos escolher o elemento inicial, o elemento final ou até mesmo a mediana de três valores como pivô.

As possibilidades são numerosas. Uma delas consiste em escolher um elemento aleatório do vetor como pivô, que é o que veremos nos próximos parágrafos.

Além do algoritmo, também mostrarei as implementações em Java, C e em JavaScript dessa versão inusitada do Quicksort.

Quicksort com pivô aleatório

Sugiro que o leitor leia o artigo Quicksort (análise e implementações) para melhor compreensão, caso não conheça o Quicksort.

Se quiser informações sobre outros algoritmos de ordenação, acesse o tópico Algoritmos de Ordenação.

Índice

Pivô aleatório

Para escrever o algoritmo do Quicksort com pivô aleatório, precisamos basicamente de um gerador de números aleatórios e algum algoritmo pronto do Quicksort.

Em geral, as linguagens de programação possuem funções ou métodos para gerar números aleatórios em suas bibliotecas, portanto isso não é um problema.

Em relação ao algoritmo pronto do Quicksort, podemos reaproveitar o algoritmo do livro Algoritmos: teoria e prática [1], assim como fizemos no Quicksort mediana de três.

A lógica é: sorteie um elemento aleatório, troque-o com o elemento da última posição do vetor e execute o algoritmo normalmente. Em pseudocódigo

01. quicksortAleatorizado(A[0...n - 1], inicio, fim)
02. |   se(inicio < fim)
03. |   |   q = particao(A, inicio, fim) //realiza a partição
04. |   |   quicksortAleatorizado(A, inicio, q - 1) /ordena a partição esquerda
05. |   |   quicksortAleatorizado(A, q + 1, fim) //ordena a partição direita
06. |   fim_se
07. fim_quicksort

Algoritmo de partição:

01. particao(A[0...n - 1], inicio, fim)
02. |   //sorteia um índice aleatório entre inicio e fim
03. |   indiceAleatório ← número aletório entre inicio e fim (inclusivo)
04. |   //coloca o pivô aleatório no fim para aplicar a partição de Cormen
05. |   trocar(A, indiceAleatório, fim)
06. |
07. |   //*******************ALGORITMO DE PARTIÇÃO DE CORMEN*********************
08. |   //o pivo é o elemento final
09. |   pivo ← A[fim]
10. |   i ← inicio - 1
11. |   /*
12. |    * Este laço irá varrer os vetores da esquerda para direira
13. |    * procurando os elementos que são menores ou iguais ao pivô.
14. |    * Esses elementos são colocados na partição esquerda.
15. |    */
16. |   para j ← inicio até fim - 1
17. |   |   se(A[j] <= pivo)
18. |   |   |   i ← i + 1
19. |   |   |   trocar(A, i, j)
20. |   |   fim_se
21. |   fim_para
22. |   trocar(A, i + 1, fim) //coloca o pivô na posição de ordenação
23. |   retorne i + 1 //retorna a posição do pivô
24. fim_particao

Ir para o índice

Códigos

Você pode baixar o Quicksort com pivô aleatório em Java, C e em JavaScipt nos links abaixo ou pode simplesmente copiar os códigos incorporados no artigo.

Ir para o índice

Java

//GitHub: HenriqueIni
//https://www.blogcyberini.com/
import java.util.Random;

//Quicksort com pivô aleatório (utiliza a partição de Cormen como base)
public class QuicksortAleatorizado {
    //Facilita a vida: só pede o array como argumento
    public static void quicksortAleatorizado(int[] A){        
        quicksortAleatorizado(A, 0, A.length - 1);
    }

    private static void quicksortAleatorizado(int[] A, int inicio, int fim){        
        if(inicio < fim){
            //realiza a partição
            int q = partition(A, inicio, fim);
            //ordena a partição esquerda
            quicksortAleatorizado(A, inicio, q - 1);
            //ordena a partição direita
            quicksortAleatorizado(A, q + 1, fim);            
        }
    }
    
    //Método de partição
    private static int partition(int[] A, int inicio, int fim){
        //sorteia um índice aleatório entre inicio e fim
        Random rnd = new Random();
        int randomIndex = rnd.nextInt(fim - inicio + 1) + inicio;
        //coloca o pivô aleatório no fim para aplicar a partição de Cormen
        swap(A, randomIndex, fim);
        
        //*******************ALGORITMO DE PARTIÇÃO DE CORMEN*********************
        //o pivô é o elemento final
        int pivo = A[fim];
        int i = inicio - 1;
        /*
         * Este laço irá varrer os vetores da esquerda para direira
         * procurando os elementos que são menores ou iguais ao pivô.
         * Esses elementos são colocados na partição esquerda.         
         */
        for(int j = inicio; j <= fim - 1; j++){
            if(A[j] <= pivo){
                i = i + 1;
                swap(A, i, j);
            }
        }
        //coloca o pivô na posição de ordenação
        swap(A, i + 1, fim);
        return i + 1; //retorna a posição do pivô
    }
    
    //método auxiliar para realizar as trocas de elementos
    private static void swap(int[] A, int i, int j){
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }    
}

Ir para o índice

C

Este código em C utiliza a função rand() para gerar os números aleatórios, entretanto essa não é a melhor maneira de se fazer isso.

//GitHub: HenriqueIni
//https://www.blogcyberini.com/

#include <stdio.h>
#include <stdlib.h>

//função auxiliar para realizar as trocas de elementos
void swap(int A[], int i, int j){
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}
//algoritmo de partição
int partition(int A[], int inicio, int fim) {
    //esse gerador de números aleatório foi retirado de:
    //https://www.ime.usp.br/~pf/algoritmos/aulas/random.html
    
    //sorteia um índice aleatório entre inicio e fim
    int k;
    double d;
    //Observação: rand() é uma função fraca para gerar números aleatórios
    d = (double) rand () / ((double) RAND_MAX + 1);
    k = d * (fim - inicio + 1);
    int randomIndex = inicio + k;
    
    //coloca o pivô aleatório no fim para aplicar a partição de Cormen
    swap(A, randomIndex, fim);
        
    //*******************ALGORITMO DE PARTIÇÃO DE CORMEN*********************
    //o pivo é o elemento final
    int pivo = A[fim];
    int i = inicio - 1;
    int j;
    /*
     * Este laço irá varrer os vetores da esquerda para direira
     * procurando os elementos que são menores ou iguais ao pivô.
     * Esses elementos são colocados na partição esquerda.         
     */
    for (j = inicio; j <= fim - 1; j++) {
        if (A[j] <= pivo) {
            i = i + 1;
            swap(A, i, j);
        }
    }
    //coloca o pivô na posição de ordenação
    swap(A, i + 1, fim);
    return i + 1; //retorna a posição do pivô
}
//Quicksort de Cormen
void quicksortAleatorizado(int A[], int inicio, int fim) {
    if (inicio < fim) {
        //realiza a partição
        int q = partition(A, inicio, fim);
        //ordena a partição esquerda
        quicksortAleatorizado(A, inicio, q - 1);
        //ordena a partição direita
        quicksortAleatorizado(A, q + 1, fim);
    }
}

Ir para o índice

JavaScript

//GitHub: HenriqueIni
//https://www.blogcyberini.com/

//método auxiliar: troca os elementos i e j em A
function swap(A, i, j) {
    var temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}
function partition(A, inicio, fim) {
    //sorteia um índice aleatório entre inicio e fim
    var randomIndex = Math.floor(Math.random() * (fim - inicio + 1)) + inicio;
    
    //coloca o pivô aleatório no fim para aplicar a partição de Cormen
    swap(A, randomIndex, fim);
    
    //*******************ALGORITMO DE PARTIÇÃO DE CORMEN*********************
    //o pivo é o elemento final
    var pivo = A[fim];
    var i = inicio - 1;
    var j;
    /*
     * Este laço irá varrer os vetores da esquerda para direira
     * procurando os elementos que são menores ou iguais ao pivô.
     * Esses elementos são colocados na partição esquerda.
     */
    for (j = inicio; j <= fim - 1; j++) {
        if (A[j] <= pivo) {
            i = i + 1;
            swap(A, i, j);
        }
    }
    //coloca o pivô na posição de ordenação
    swap(A, i + 1, fim);
    return i + 1; //retorna a posição do pivô
}
//Quicksort com pivô aleatório
function quicksortAleatorizado(A, inicio, fim) {
    if (inicio < fim) {
        //realiza a partição
        var q = partition(A, inicio, fim);
        //ordena a partição esquerda
        quicksortAleatorizado(A, inicio, q - 1);
        //ordena a partição direita
        quicksortAleatorizado(A, q + 1, fim);
    }
}

Ir para o índice

Considerações finais

Não utilize esse algoritmo em situações práticas. Ele é útil apenas para fins acadêmicos, pois o seu comportamento é imprevisível.

Em relação à complexidade, espera-se que esta seja $O(n\log n)$, entretanto podemos ter o raro azar (isso mesmo, azar!) de cairmos no caso $O(n^2)$.

Por fim, enfatizo que quando utilizamos um computador determinístico, não é possível gerar números que sejam de fato aleatórios. Máquinas determinísticas geram números pseudoaleatórios através de cálculos complexos envolvendo o tempo. Isso gera a ilusão de que eles são aleatórios.

Ir para o índice

Referências

Siga o blog

Redes sociais: Facebook, Twitter, Google+, YouTube, Pinterest, Instagram

Receba notificações de novas postagens e novidades do blog por e-mail.

Importante: utilize o bom senso na hora de comentar. Acesse a política de privacidade para maiores informações sobre comentários.

Nenhum comentário:

Postar um comentário