Compartilhe
Ver o tópico anteriorIr em baixoVer o tópico seguinte
avatar
Admin
Admin
Mensagens : 5
Pontos : 17
Reputação : 2
Data de inscrição : 05/05/2017
Idade : 27
Localização : Bandeirantes
Ver perfil do usuário

QuickSort - Método de Ordenção

em 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:

Clique "Questionário" para responder \/ :
Questionário
Ver o tópico anteriorVoltar ao TopoVer o tópico seguinte
Permissão deste fórum:
Você não pode responder aos tópicos neste fórum