Quick sorte

Disponível somente no TrabalhosFeitos
  • Páginas : 2 (323 palavras )
  • Download(s) : 0
  • Publicado : 20 de novembro de 2012
Ler documento completo
Amostra do texto
Fontes de consulta:
http://pt.wikipedia.org/wiki/Quicksort
http://www.knoow.net/ciencinformtelec/informatica/quicksort.htm
Conceito de Quicksort
O Quicksort ou classificação rápida, designaum 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 aotentar 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 Foipublicado 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égiabá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 opivô 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, nofinal, 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 otamanho 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] =...
tracking img