Quicksort mediana de três

O algoritmo clássico do Quicksort tem complexidade quadrática quando aplicado em vetores ordenados em ordem crescente ou decrescente, que é algo catastrófico.

Isso é uma consequência da má escolha do pivô. Uma forma de eliminar o problema é escolhendo a mediana de três elementos do vetor como pivô.

O objetivo deste artigo é mostrar o funcionamento dessa versão do Quicksort e suas implementações em Java, C e em JavaScript.

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.

O que é mediana?

A mediana é o valor que está no meio de um conjunto de dados. Por exemplo, a mediana entre 10, 15, 1, 0, 3 é o 3, pois se colocarmos esses números em ordem, o 3 ocupará a posição central

0, 1, 3, 10, 15

Ir para o índice

O pivô como a mediana de três valores

A ideia do Quicksort mediana de três é escolher três elementos do vetor e tomar como pivô a mediana desses três elementos. Usualmente, os elementos do início, do meio e do final do vetor são os escolhidos no cálculo da mediana.

Podemos implementar essa lógica reaproveitando alguma versão pronta do Quicksort. Vamos reaproveitar a versão do Cormen [1], que sempre escolhe o último elemento do vetor como pivô.

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

01. quicksortMedianaDeTres(A[0...n - 1], inicio, fim)
02. |   se(inicio < fim)
03. |   |   q = particao(A, inicio, fim) //realiza a partição
04. |   |   quicksortMedianaDeTres(A, inicio, q - 1) /ordena a partição esquerda
05. |   |   quicksortMedianaDeTres(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. |   //procura a mediana entre inicio, meio e fim
03. |   meio ← (inicio + fim) / 2
04. |   a ← A[inicio]
05. |   b ← A[meio]
06. |   c ← A[fim]
07. |   medianaIndice ← 0 //índice da mediana (o zero é só para inicializar a variável)
08. |   //A sequência de if...else a seguir verifica qual é a mediana
09. |   se(a < b)
10. |   |   se(b < c)
11. |   |   |   //a < b && b < c
12. |   |   |   medianaIndice ← meio
13. |   |   senão
14. |   |   |   se(a < c)
15. |   |   |   |   //a < c && c <= b
16. |   |   |   |   medianaIndice ← fim
17. |   |   |   senão
18. |   |   |   |   //c <= a && a < b
19. |   |   |   |   medianaIndice ← inicio
20. |   |   |   fim_se
21. |   |   fim_se
22. |   senão
23. |   |   se(c < b)
24. |   |   |   //c < b && b <= a
25. |   |   |   medianaIndice ← meio
26. |   |   senão
27. |   |   |   se(c < a)
28. |   |   |   |   //b <= c && c < a
29. |   |   |   |   medianaIndice ← fim
30. |   |   |   senão
31. |   |   |   |   //b <= a && a <= c
32. |   |   |   |   medianaIndice ← inicio
33. |   |   |   fim_se
34. |   |   fim_se
35. |   fim_se
36. |   //coloca o elemento da mediana no fim para poder usar o Quicksort de Cormen
37. |   trocar(A, medianaIndice, fim)
38. |
39. |   //*******************ALGORITMO DE PARTIÇÃO DE CORMEN*********************
40. |   //o pivo é o elemento final
41. |   pivo ← A[fim]
42. |   i ← inicio - 1
43. |   /*
44. |    * Este laço irá varrer os vetores da esquerda para direira
45. |    * procurando os elementos que são menores ou iguais ao pivô.
46. |    * Esses elementos são colocados na partição esquerda.
47. |    */
48. |   para j ← inicio até fim - 1
49. |   |   se(A[j] <= pivo)
50. |   |   |   i ← i + 1
51. |   |   |   trocar(A, i, j)
52. |   |   fim_se
53. |   fim_para
54. |   trocar(A, i + 1, fim) //coloca o pivô na posição de ordenação
55. |   retorne i + 1 //retorna a posição do pivô
56. fim_particao

Ir para o índice

Qual é a vantagem?

A principal vantagem de utilizar a mediana como pivô é que o particionamento será balanceado mesmo quando o vetor estiver ordenado em ordem crescente ou decrescente.

Entretanto, sempre é possível encontrar um caso no qual a complexidade é $O(n^2)$. É a "maldição" que o Quicksort carrega.

Ir para o índice

Códigos

Você pode baixar o Quicksort mediana de três 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/

//Quicksort Mediana de Três (utiliza a partição de Cormen como base)
public class QuicksortMedianaDeTres {
    //Facilita a vida: só pede o array como argumento
    public static void quicksortMedianaDeTres(int[] A){        
        quicksortMedianaDeTres(A, 0, A.length - 1);
    }

    private static void quicksortMedianaDeTres(int[] A, int inicio, int fim){        
        if(inicio < fim){
            //realiza a partição
            int q = partition(A, inicio, fim);
            //ordena a partição esquerda
            quicksortMedianaDeTres(A, inicio, q - 1);
            //ordena a partição direita
            quicksortMedianaDeTres(A, q + 1, fim);            
        }
    }
    
    //Método de partição
    private static int partition(int[] A, int inicio, int fim){
        //procura a mediana entre inicio, meio e fim
        int meio = (inicio + fim)/2;
        int a = A[inicio];
        int b = A[meio];
        int c = A[fim];
        int medianaIndice; //índice da mediana
        //A sequência de if...else a seguir verifica qual é a mediana
        if(a < b){
            if(b < c){
                //a < b && b < c
                medianaIndice = meio;
            }else{                
                if(a < c){
                    //a < c && c <= b
                    medianaIndice = fim;
                }else{
                    //c <= a && a < b
                    medianaIndice = inicio;
                }
            }
        }else{
            if(c < b){
                //c < b && b <= a
                medianaIndice = meio;
            }else{
                if(c < a){
                    //b <= c && c < a
                    medianaIndice = fim;
                }else{
                    //b <= a && a <= c
                    medianaIndice = inicio;
                }
            }
        }
        //coloca o elemento da mediana no fim para poder usar o Quicksort de Cormen
        swap(A, medianaIndice, fim);
        
        //*******************ALGORITMO DE PARTIÇÃO DE CORMEN*********************
        //o pivo é 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

//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;
}

int partition(int A[], int inicio, int fim) {
    //procura a mediana entre inicio, meio e fim
    int meio = (inicio + fim) / 2;
    int a = A[inicio];
    int b = A[meio];
    int c = A[fim];
    int medianaIndice; //índice da mediana
    //A sequência de if...else a seguir verifica qual é a mediana
    if (a < b) {
        if (b < c) {
            //a < b && b < c
            medianaIndice = meio;
        } else {
            if (a < c) {
                //a < c && c <= b
                medianaIndice = fim;
            } else {
                //c <= a && a < b
                medianaIndice = inicio;
            }
        }
    } else {
        if (c < b) {
            //c < b && b <= a
            medianaIndice = meio;
        } else {
            if (c < a) {
                //b <= c && c < a
                medianaIndice = fim;
            } else {
                //b <= a && a <= c
                medianaIndice = inicio;
            }
        }
    }
    //coloca o elemento da mediana no fim para poder usar o Quicksort de Cormen
    swap(A, medianaIndice, 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 mediana de três
void quicksortMedianaDeTres(int A[], int inicio, int fim) {
    if (inicio < fim) {
        //realiza a partição
        int q = partition(A, inicio, fim);
        //ordena a partição esquerda
        quicksortMedianaDeTres(A, inicio, q - 1);
        //ordena a partição direita
        quicksortMedianaDeTres(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) {
    //procura a mediana entre inicio, meio e fim
    var meio = Math.floor((inicio + fim) / 2);
    var a = A[inicio];
    var b = A[meio];
    var c = A[fim];
    var medianaIndice; //índice da mediana
    //A sequência de if...else a seguir verifica qual é a mediana
    if (a < b) {
        if (b < c) {
            //a < b && b < c
            medianaIndice = meio;
        } else {
            if (a < c) {
                //a < c && c <= b
                medianaIndice = fim;
            } else {
                //c <= a && a < b
                medianaIndice = inicio;
            }
        }
    } else {
        if (c < b) {
            //c < b && b <= a
            medianaIndice = meio;
        } else {
            if (c < a) {
                //b <= c && c < a
                medianaIndice = fim;
            } else {
                //b <= a && a <= c
                medianaIndice = inicio;
            }
        }
    }
    //coloca o elemento da mediana no fim para poder usar o Quicksort de Cormen
    swap(A, medianaIndice, 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 mediana de três
function quicksortMedianaDeTres(A, inicio, fim) {
    if (inicio < fim) {
        //realiza a partição
        var q = partition(A, inicio, fim);
        //ordena a partição esquerda
        quicksortMedianaDeTres(A, inicio, q - 1);
        //ordena a partição direita
        quicksortMedianaDeTres(A, q + 1, fim);
    }
}

Ir para o índice

Referências

[1] CORMEN, T. H. et al. Algoritmos: teoria e prática. 3 ed. Rio de Janeiro: Elsevier, 2012.

Quicksort mediana de três

Índice

O que é mediana?

O pivô como a mediana de três valores

Qual é a vantagem?

Códigos

Java

C

JavaScript

Referências

Siga o blog

Nenhum comentário:

Postar um comentário

Potenciação de Matrizes

Como obter o ID de um canal do YouTube?

Questões Resolvidas do ENADE 2017 de Ciência da Computação

Teorema Mestre e Exemplos Resolvidos

Quicksort (análise e implementações)

Algoritmo para calcular o MMC