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.
Índice
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
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
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.
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.
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; } }
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); } }
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); } }
Referências
- [1] CORMEN, T. H. et al. Algoritmos: teoria e prática. 3 ed. Rio de Janeiro: Elsevier, 2012.
Nenhum comentário:
Postar um comentário