TRABALHO AED

História
1 QUICKSORT
Entre os mais importantes algoritmos de ordenação, temos o QuickSort que foi desenvolvido em 1960 pelo cientista da computação britânico Charles Antony Richard Hoare, também conhecido como Tony Hoare.
No período em que desenvolveu o algoritmo, Hoare estava participando em um projeto de tradução de máquina para o National Physical Loboratory(É a maior instituição de física aplicada na GB, e tem um papel similar ao do Inmetro do Brasil e do NIST dos Estados Unidos.). 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 possam ser resolvidos de forma mais fácil e rápida. Após uma série de refinamentos o algoritmo foi publicado em 1962.

2 ESTRATÉGIA DE ORDENAÇÃO

O QuickSort é um algoritmo de comparação que emprega a estratégia da solução de problemas “dividir para conquistar”. Na prática é mais eficiente que os seus concorrentes porque o seu loop interno pode ser implementado de forma muito eficiente na maioria das arquiteturas, além de ser possível fazer muitas otimizações casos específicos.
A forma como o algoritmo funciona pode ser resumida na seguinte estratégia: O QuickSort divide sua lista de entrada em duas sub-listas a partir de um pivô, em seguida realiza o mesmo procedimento nas duas listas menores até o caso trivial, onde terá uma lista unitária.
1. Verifica se não é um caso base: lista unitária ou vazia, nestes casos a entrada já está trivialmente ordenada.
2. Escolhe um elemento da lista chamado pivô, geralmente é o primeiro elemento da sequência a ser ordenada.
3. Reorganiza a lista de forma que os elementos menores que o pivô fiquem de um lado, e os maiores fiquem do outro. Esta operação é chamada de “particionamento”.
4. Recursivamente ordena a sub-lista abaixo do pivô e acima do pivô.
5. Combine as listas ordenadas e o pivô.

Esta técnica consiste em dividir um