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.
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
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.
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; } }
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); } }
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); } }
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.
Referências
- [1] CORMEN, T. H. et al. Algoritmos: teoria e prática. 3 ed. Rio de Janeiro: Elsevier, 2012.
Obrigada! ótimo artigo
ResponderExcluirObrigado!
Excluir