QuickSort - Método de Ordenção

Seg Nov 13, 2017 1:32 pm

Definição

O Quicksort (comumente conhecido como classificação rápida) designa um algoritmo extremamente eficiente e rápido de classificação de dados desenvolvido por Charles Antony Richard Hoare em 1960.
A estratégia básica do quicksort é a de “dividir para conquistar”. O Quicksort é o algoritmo mais eficiente na ordenação por comparação. Nele se escolhe um elemento chamado de pivô, a partir disto é organizada a lista para que todos os números anteriores a ele sejam menores que ele, e todos os números posteriores a ele sejam maiores que ele. Ao final desse processo o número pivô já está em sua posição final. Os dois grupos desordenados recursivamente sofreram o mesmo processo até que a lista esteja ordenada.
Performances
Melhor caso: O(N log N)
Pior caso (raro): O(n2)
Desvantagem: Como escolher o pivô?

Figura 1. Esquema de funcionamento do Quick Sort

O número 3 foi escolhido como pivô, nesse passo é procurado à sua direita um número menor que ele para ser passado para a sua esquerda. O primeiro número menor encontrado foi o 1, então eles trocam de lugar.
Agora é procurado um número à sua esquerda que seja maior que ele, o primeiro número maior encontrado foi o 5, portanto eles trocam de lugar.
O mesmo processo do passo 1 acontece, o número 2 foi o menor número encontrado, eles trocam de lugar.
O mesmo processo do passo 2 acontece, o número 4 é o maior número encontrado, eles trocam de lugar.
O vetor desse exemplo é um vetor pequeno, portanto ele já foi ordenado, mas se fosse um vetor grande, ele seria dividido e recursivamente aconteceria o mesmo processo de escolha de um pivô e comparações.

Operações do Algoritmo

Função Troca

Código:: void troca(int *v, int i, int j){ int aux; aux=v[i]; v[i]=v[j]; v[j]=aux; }

Função Partição

Código:: int particao(int *x, int p, int r){ int pivo, i, j; i=p-1; j=r+1; pivo=x[(int)floor((p+r)/2)]; while(i<j){ do{ j--; }while((!(x[j]<=pivo)) && j>=0); do{ i++; }while((!(x[i]>=pivo)) && i<=r); if(i<j) troca(x, i, j); } return j; }

Função de Ordenação

Código:: void quicksort(int *x, int p, int r){ int q; if(p<r){ q = particao(x, p, r); quicksort(x, p, q); quicksort(x, q+1, r); } }

Main

Código:: int main(){ int i=0; int vetor[]={13, 25, 9, 48, 10, 18, 10, 3, 90, 8}; printf("\nAntes da ordenacao\n"); for(i=0; i<10; i++) printf(" %d", vetor[i]); quicksort(&vetor[0], 0, 9);//********************** printf("\n\n\nDepois da ordenacao\n"); for(i=0; i<10; i++) printf(" %d", vetor[i]); return 0; }

Videos para reforços ( ABRA OS SPOILERS )

QuickSort Método de Ordenação:

ATIVIDADE DE FIXAÇÃO ( ABRA O SPOILER )

Spoiler: