Conceito de Quicksort
Nas ciências da computação, Quicksort (em português, ‘classificação rápida’) designa um algoritmo extremamente eficiente e rápido de classificação de dados. O algoritmo foi desenvolvido inicialmente por Charles Antony Richard Hoare (conhecido por Tony Hoare ou ainda por C.A.R. Hoare) em 1960 quando ainda era estudante, e após uma visita que fez à Universidade de Moscovo. Ao tentar traduzir um dicionário de inglês para russo, e para a ordenação das palavras, Hoare desenvolveu uma estratégia em que reduzia o problema original em diversos subproblemas que pudessem ser resolvidos de forma mais fácil e rápida.
Assim, 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.
Além do quicksort, existem outras metodologias de classificação, entre as quais a bubble sort (classificação de bolhas), insertion sort (classificação por inserção) e merge sort (classificação por intercalação).
