Quick sorte
Conceito de Quicksort
O Quicksort ou 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 durante uma visita a Universidade de Moscou , Ele criou o 'Quicksort ao tentar traduzir um dicionário de inglês para russo, ordenando as palavras, tendo como objetivo reduzir o problema original em subproblemas que podiam ser resolvidos mais fácil e rapidamente Foi publicado em 1962 após uma série de refinamentos. Sendo considerado um algoritmo de ordenação por comparação não-estável, ou seja preserva a ordem de registros de chaves iguais
Funcionamento: A estratégia básica do quicksort é a de "dividir para conquistar". Inicia-se com a escolha de um elemento da lista, designado pivô; a lista é então rearranjada de forma que todos os elementos maiores do que o pivô fiquem de um dos lados do pivô e todos os elementos menores fiquem do outro lado (ficando assim o pivô na sua posição definitiva); recursivamente, repete-se este processo para cada sub-lista e, no final, o resultado é uma lista ordenada.
Aplicação: Implementação em C++ Vamos considerar um Array de números inteiros, também vamos considerar que a variável tam, do tipo numérica inteira, com o tamanho de nosso Array.
void quick(int Q[50], int inicio, int fim)
{
int meio; comparacoes[4]++; if (inicio<fim) { atribuicoes[4]++; meio = particiona(Q, inicio, fim); quick(Q, inicio, meio-1); quick(Q, meio+1, fim); }
}
int particiona(int Q[50], int inicio, int fim)
{
int pivo, ultbaixo, temp, i; atribuicoes[4]++; pivo = Q[inicio]; ultbaixo = inicio; for(i=inicio+1; i<=fim; i++) { comparacoes[4]++; if (Q[i]<=pivo) { ultbaixo++; atribuicoes[4]+=3; temp = Q[i]; Q[i] =