Ordenação é o processo de arranjar um conjunto de informações semelhantes em ordem crescente ou decrescente. Ou seja, é o ato de se colocar os elementos de uma sequência de informações, ou dados, em uma relação de ordem predefinida.
Dado uma seqüência de n dados:
O problema de ordenação é uma permutação dessa seqüência:
Tal que se estebeleça a seguinte ordem:
Algumas ordens são facilmente definidas. Por exemplo, a ordem numérica, ou a ordem alfabética. Contudo, existem ordens, especialmente de dados compostos, que podem ser não triviais de se estabelecer.
Os algoritmos que ordenam um conjunto, geralmente representada num vetor, são chamados de algoritmos de ordenação. A função desses algoritmos é promover a ordenação completa ou parcial dos elementos presentes no vetor. Existem várias razões para se ordenar uma sequência. Uma delas é a possibilidade se acessar seus dados de modo mais eficiente.
Entre os mais importantes algoritmos de ordenação, podemos citar o bubble sort (ou ordenação por flutuação), heap sort (ou ordenação por heap), insertion sort (ou ordenação por inserção), merge sort (ou ordenação por mistura) e o quicksort. Nessa edição iremos abordar a história do QuickSort.
O QuickSort foi desenvolvido em 1960 pelo cientista da computação britânico Charles Antony Richard Hoare, também conhecido como Tony Hoare ou C. A. R. Hoare, que também desenvolveu a Lógica de Hoare e a linguagem formal CSP, usada para especificar interações entre processos concorrentes e que serviu de inspiração para a linguagem de programação Occam.
No período em que desenvolveu o algoritmo, Hoare estava participando em um projeto de tradução de máquina para o National Physical Laboratory. 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.
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ô.
Uma forma mais divertida de ver o funcionamento do QuickSort é através do vídeo abaixo, que mostra uma dança húngara baseada nas regras desse algoritmo de ordenação.
O QuickSort é um dos algoritmos com melhor desempenho. Apesar de no pior caso – quando o número de elementos da sequencia são muito grandes – possuir execução lenta, o QuickSort é muitas vezes a melhor opção na prática, pois é eficiente nos casos médios e possui, nesses casos, execução satisfatória.
Referências:
- CORMEN, T. H. Introduction The Algorithms, 2ª edição. 2002.
- http://www2.dcc.ufmg.br/disciplinas/aeds2_turmaA1/aeds2.html
Grupo PET Computação UFCG, 2013. All rights reserved.
