Ordenação com Quicksort

Prévia do material em texto

Ordenação 1
Ordenação
QUICKSORT
Conceito
A ideia é dividir para conquistar, um elemento é escolido como pivô
Funcionamento:
O funcionamento ocorre de forma recursiva até ordenar todo o vetor
pivô > valor valor colocado antes
pivô < valor valor colocado depois
pivô = valor não altera a ordem
Repartição:
A função divide o vetor em dois vetores, sendo o ponto de divisão o pivô;
Exemplo de código
void quickSort (int *V, int inicio, int fim)
{ 
 int pivo; 
 if(fim> inicio) 
 { 
 pivo = particiona (V, inicio, fim); 
 quickSort(V, inicio, pivo-1); 
 quickSort(V,pivo+1, fim); 
 }
}
int particiona(int *V, int inicio, int final)
{ 
 int esq, dir, pivo, aux; 
 
 esq = inicio; 
 dir = final; 
 pivo = V[inicio]; //pivo é a posição de inicio aqui 
 
 while(esq<dir) // isso acontece por enquanto a posição da esquerda for menor que a da di
reita 
 { 
 while(V[esq]<= pivo) // isso faz a esquerida andar, até que ache um valor que seja mai
or que pivo 
 esq ++; 
 while(V[dir]> pivo) //isso faz a direita andar até achar um valor que seja menor que p
ivo 
 dir --; 
 if(esq<dir) // caso a posição da direita for maior que a da esquerda 
 { 
 // troca esquerda por direita 
 aux = V[esq]; 
 V[esq] = V[dir]; 
 V[dir] = aux; 
 } 
 } 
Ordenação 2
 
 //essa parte faz com que todo mundo que esteja depois do "pivô" escolido inicialmente
 seja maior e todo mundo antes seja menor 
 
 //o pivô escolido primeiramente já está no local dele 
 
 V[inicio] = V[dir]; //trocando direita e inicio de lugar 
 V[dir] = pivo // tornando a direita em pivo 
 
 return dir;
}
Funcionamento da primeira ordenação
Funcionamento da Recursão
Ordenação 3
FUNÇÃO QSORT
Conceito
É um algoritmo quicksort que utiliza uma função de comparação para o seu 
funcionamento. Ele está implementado na biblioteca "stdlib.h".
Formato
qsort(array,tamanho do vetor,tamanho do tipo, função de comparação);
Funcionamento da Função de Comparação
É necessária definir dois valores do array que serão comparados.
Os valores definidos podem ser de qual quer tipo
Até mesmo um vetor, nesse caso um vai apontar para a posição inicial e o 
outro na posição final
Prótotipo:
int comp (const void* p1, const void* p2);
Os valores que essa função retorna são:
p1 < 0 p1 vem antes de p2
p1 = 0 p1 é igual a p2
p1 > 0 p1 vem depois de p2
Referências
As fotos colocadas nesse resumo foram tiradas do vídeo "ED Aula 49 - 
Ordenação - InsertionSort" do canal Linguagem C Programação Descomplicada.