Sua ideia é escolher um elemento aleatório dentro do array (chamado pivô), jogar todos os elementos menor que ele para a esquerda e todos os maiores para a direita, depois repetir o processo com os arrays da esquerda e direita dele, até que o array esteja ordenado totalmente.
Existem várias formas de escolher o pivô, mas aqui estaremos usando o pivô como sendo o elemento do meio do array, em breve explicarei o motivo.
Primeiro, criamos dois apontadores para os elementos das extremidades do array.
A cada iteração:
Se o elemento da extremidade esquerda for menor que o pivô, ele pode ficar lá, então aponta para o próximo elemento.
Repete isso até achar um elemento maior, e pára nele.
Se o elemento da extremidade direita for maior que o pivô, ele pode ficar lá, então aponta para o elemento anterior.
Repete isso até achar um elemento menor, e pára nele.
No momento em que o apontador da extremidade esquerda apontar para um elemento maior que o pivô e o apontador da extremidade direita apontar para um elemento menor que o pivô, trocamos os elementos, de forma que ambos vão ficar em lugares possíveis para eles.
Vamos representar o apontador da esquerda com azul e o da direita com verde.
Vejamos a um exemplo na prática:
5 9 4 2 1 8 7 6 0 3
Escolhemos o elemento do meio como pivô:
PIVÔ = 1
Para que o pivô não atrapalhe nas comparações, podemos jogar ele para o fim por enquanto:
5 9 4 2 3 8 7 6 0 1
O 5 é maior que o pivô, segura ele.
O 0 é menor que o pivô, segura ele.
Trocamos os dois elementos e andamos com os dois apontadores.
0 9 4 2 3 8 7 6 5 1
0 9 4 2 3 8 7 6 5 1
Não há mais ninguém menor que o pivô, o apontador direito vai voltar até encontrar o esquerdo:
0 9 4 2 3 8 7 6 5 1
0 9 4 2 3 8 7 6 5 1
0 9 4 2 3 8 7 6 5 1
0 9 4 2 3 8 7 6 5 1
0 9 4 2 3 8 7 6 5 1
0 9 4 2 3 8 7 6 5 1
Podemos notar que, como não tinha mais ninguém menor que o pivô para ser trocado pelo 9, ele permaneceu no lugar até os apontadores se encontrarem.
Como todos os menores que o pivô estão antes do 9, a posição correta do pivô é no lugar no 9.
Dito isso, fazemos a troca do 9 com o pivô (que estava na última posição)
0 1 4 2 3 8 7 6 5 9
Como nenhum dos subarrays à esquerda e à direita do pivô são nulos, chamamos recursivamente o QuickSort para ordenar ambos.
Do lado esquerdo, ignoremos o QuickSort no 0 (nada vai acontecer).
Do lado direito, fazemos o QuickSort novamente:
PIVÔ = 8
4 2 3 8 7 6 5 9
Jogamos o pivô para o final e ordenamos:
4 2 3 9 7 6 5 8 anda o azul até 9
4 2 3 9 7 6 5 8 o verde já é menor que pivô, troca e anda
4 2 3 5 7 6 9 8 anda o azul até o 9
4 2 3 5 7 6 9 8 se passaram, encerra aqui
Como todos os menores que o pivô estão antes do 9, a posição correta do pivô é no lugar no 9.
4 2 3 5 7 6 8 9
Chamamos recursivamente o QuickSort para os subarrays da esquerda e da direita.
Novamente, ignoremos o 9, pois nada acontece.
4 2 3 5 7 6
PIVÔ = 3
Movemos o pivô pro fim:
4 2 6 5 7 3 o azul fica parado, verde vai até o 2
4 2 6 5 7 3 troca e anda
2 4 6 5 7 3 se passaram, encerra aqui
Como todos os menores que o pivô estão antes do 4, a posição correta do pivô é no lugar no 4.
2 3 6 5 7 4
Ignoramos o 2, QuickSort no subarray da direita:
6 5 7 4
PIVÔ = 5
Movemos o pivô pro fim:
6 4 7 5 o azul fica parado, verde vai até o 4
6 4 7 5 troca e anda
4 6 7 5 se passaram, encerra aqui
Como todos os menores que o pivô estão antes do 6, a posição correta do pivô é no lugar no 6.
4 5 7 6
Ignoramos o 4, QuickSort no subarray da direita:
7 6
PIVÔ = 7
Movemos o pivô pro fim:
6 7 azul anda até o 7, verde fica parado
6 7 se passaram, encerra aqui
Como todos os menores que o pivô estão antes do 7, a posição correta do pivô é no lugar no 7 (e ele já está lá).
6 7
Só para demonstrar, vamos fazer o QuickSort do subarray da esquerda do 7:
6
PIVÔ = 6
6 apontador esquerdo fixa no 6 (pois 6 não é menor que o pivô)
6 apontador direito não pode andar mais para não passar do esquerdo
6 os dois se encontraram, encerra.
Não chama os QuickSorts pois os subarrays tem tamanho vazio.
Realizando a volta de todas as recursões:
6
6 7
4 6 7
4 5 6 7
2 4 5 6 7
2 3 4 5 6 7
2 3 4 5 6 7 9
2 3 4 5 6 7 8 9
0 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
Finalmente temos:
0 1 2 3 4 5 6 7 8 9
Eis uma implementação resumida do QuickSort:
void QuickSort(int arr[], int ini, int fim){ int pos = (ini + fim)/2; //pega posicao do meio do array int pivo = arr[pos]; //salva valor do pivo swap(arr[pos], arr[fim]); //coloca pivo no fim int i = ini, j = fim - 1; //cria apontadores while(i <= j){ while(arr[i] < pivo) i++; //move esquerda while(arr[j] >= pivo && j >= i) j--; //move direita if(i < j) swap(arr[i++], arr[j--]); //troca (e anda) se possível } swap(arr[i], arr[fim]); //retorna pivo para posicao certa if(i - ini) QuickSort(arr, ini, i - 1); //se subarray esquerdo não é vazio if(fim - i) QuickSort(arr, i + 1, fim); //se subarray direito não é vazio } int main(){ int a[] = {5, 9, 4, 2, 1, 8, 7, 6, 0, 3}; QuickSort(a, 0, 9); for(int i = 0; i < 10; i++){ printf("%d ", a[i]); } }
Pergunta: por que não usar o pivô como sendo sempre o primeiro elemento do array que se vai ordenar?
Resposta: imagine um array ordenado {1, 2, 3, 4, 5, 6, 7, 8}.
Escolhemos 1 como pivô e mudamos ele para o lugar do último.
{8, 2, 3, 4, 5, 6, 7, 1}
O apontador da esquerda fixa (pois já é maior que o pivô) e o da direita vai até o da esquerda e páara (pois não há ninguém menor que o pivô para ser fixado).
n-1 operações. Pivô volta para o lugar
QuickSort em {2, 3, 4, 5, 6, 7, 8}
Mesma lógica.
n-2 operações. Pivô volta para o lugar.
...
QuickSort em {8}
Mesma lógica.
1 operação e encerra o QuickSort.
Total de operações = $\sum_{i=1}^{n-1} i = ( (n-1) + 1) * \frac{n-1}{2} = n * \frac{n-1}{2} = \frac{n^2 - n}{2}$
Então temos que:
$O(\frac{n^2 - n}{2}) = $
$O(\frac{1}{2} (n^2 - n)) = $
$O(n^2 - n) = $
$O(n^2) $
Complexidade do QuickSort no pior caso: O(n²) Complexidade média do QuickSort: O(n lg(n))
Outros algoritmos conhecidos são o MergeSort, BubbleSort, InsertionSort, HeapSort, etc...
Dois algoritmos eficientes e pouco conhecidos são o TimSort e o SmoothSort.
Nenhum comentário:
Postar um comentário