Estrutura de dados e o Quick Sort

Como o Quick Sort pode lhe ajudar de forma eficiente a organizar vetores com ordenação e tamanho completamente desconhecidos.

Funcionamento do Quick Sort.

   Dando continuidade a nossa sequência de matérias sobre desenvolvimento, mais propriamente falando de estrutura de dados, seguiremos agora com um algoritmo realmente interessante, fácil de se implementar e de grande valia para organizar vetores uni dimensionais organizados de qualquer forma, tendo ou não conhecimento do valor do mesmo.

Demonstração de funcionamento do Quick Sort.

   Falando sobre o Quick Sort, o mesmo é um algoritmo de ordenação de vetores de ordem O(n²) para o pior caso e de ordem O(log₂n) para o melhor caso e para o caso médio. O Quick Sort funciona da seguinte maneira. É determinado um pivô dentre os valores do vetor. Todos os valores a esquerda deste pivô, através de uma função de partição, deverão ser menores que ele e por conseguinte todos os valores a direita do pivô deverão ser maiores ou iguais a ele. Após a partição deste vetor em pré-pivô e pós-pivô, teremos o mesmo na posição final e dois sub vetores desordenados. De forma recursiva ordenam-se os sub vetores gerados e com isso teremos o vetor já completamente ordenado. O código comentado abaixo demonstra de  forma simples o uso do algoritmo.

#include<stdlib.h>;
#include<stdio.h>;

#define MAX 10

int particao(int [], int, int);
int quickSort(int [], int, int);
void troca(int *, int *);

main(){
 int vet[MAX] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 4}
 int i;

 //impressao dos valores do algoritmo antes da ordenacao
 printf("Algoritimo antes da ordenacao.\n");
 for(i = 0; i < MAX; i++) printf("Vetor[%d]: %d\n", i, vet[i]);

 //metodo de eleicao de pivo e ordenacao recursiva
 quickSort(vet, 0, MAX - 1);

 //impressao dos valores do algoritmo depois da ordenacao
 printf("Algoritimo depois da ordenacao.\n");
 for(i = 0; i < MAX; i++) printf("Vetor[%d]: %d\n", i, vet[i]);
}

 /*metodo de particao do vetor em subvetores recebendo
 como parametro o vetor ja dividido da funcao recursiva
 quickSort, o valor maximo (esq) e o valor minimo (dir)
 deste vetor*/
 int particao(int vet[], int esq, int dir){
 int x = vet[dir];
 int i = esq - 1;
 int j;

 /*loop de ordenacao dos sub vetores, levando tudo menor que
 o pivo para esquerda e o que e maior para a direita*/
 for(j = esq; j < dir; j++){

  /*se o valor da direita for maior que o da esquerda
  chama-se a funcao troca, para fazer a inversao dos 
  valores dentro do vetor, caso contrario, nada acontece.
  Isso ira funcionar porque como e chamada por uma funcao
  recursiva, a primeira vez que for executada tera apenas
  dois valores e conforme for avancando os valores ja
  estarao ordenados. Se nao estiverem, caimos no pior caso*/
  if(vet[j] < x){
   i++;
   troca(&vet[i], &vet[j]);
  }
 }

 /*ao termino do processo, o valor que foi denominado como pivo
 sera levado para a ultima posicao do mesmo, deixando os elementos
 anteriores ordenados e ele sera o proximo pivo, ja que os sub
 vetores sao do mesmo tamanho*/
 troca(&vet[i + 1], &vet[dir]);
 return i + 1;
}

//simples metodo de troca utilizando ponteiros
void troca(int * pVetA, int * pVetB){
    int temp = * pVetA;
    * pVetA = * pVetB;
    * pVetB = temp;
}

 //metodo principal. Aqui realmente e onde o quick sort acontece
 int quickSort(int vet[], int esq, int dir){

 //valor que sera o ponteiro
 int r;

 /*essa e a funcao de parada da recursividade, quando dir e esq
 forem iguais, significando que o vetor nao pode mais ser
 subdividido*/
 if(dir > esq){

  //esse metodo retornara o primeiro valor de pivo
  r = Particao(vet, esq, dir);

  /*esse metodo sera chamado diversas vezes para o lado
  esquerda, subdividindo o vetor sempre ao meio e o
  ordenando. O metodo sera chamado enquanto o vetor ainda
  puder ser subdividido, assumindo (dir > esq)*/
  QuickSort(vet, esq, r - 1);

  /*esse metodo sera chamado diversas vezes para o lado
  direito, subdividindo o vetor sempre ao meio e o
  ordenando. O metodo sera chamado enquanto o vetor ainda
  puder ser subdividido, assumindo (dir > esq)*/
  QuickSort(vet, r + 1, dir);
 }
}

   Espero que tenham gostado da matéria nobres leitores e nerds que sempre nos acompanham. Assinem o feed e acompanhem o blog para ficar por dentro das tecnologias e inteirados de todas as novidades do mundo nerd!

Nerds Attack!