Quick sorte

323 palavras 2 páginas
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, 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] =

Relacionados

  • Danças
    2077 palavras | 9 páginas
  • Comparação Empírica de Algoritmos de Ordenação
    1816 palavras | 8 páginas
  • Trabalho Aps
    3828 palavras | 16 páginas
  • Resenha
    1058 palavras | 5 páginas
  • Métodos de Ordenação
    396 palavras | 2 páginas
  • O Lado Bom da Vida
    2849 palavras | 12 páginas
  • classificação e pesquisa
    1349 palavras | 6 páginas
  • dsf sss
    6656 palavras | 27 páginas
  • paças
    1328 palavras | 6 páginas
  • algoritmo e criptografia
    5849 palavras | 24 páginas