Você sabe programar um QuickSort? #002
Você sabe programar um QuickSort?
Enquanto estou a procura de um novo emprego estou reavivando um antigo projeto pessoal meu que basicamente consiste em estudar a nuance de multiplas linguagens de programação e seu desempenho na solução de diversos problemas.
A vantagem desse projeto é de aprender novas linguagens ao mesmo tempo em que eu reforço conceitos antigos e crio novos habitos, tais como Orientação a objetos, Programação funcional, Testes automatizados, Docker etc...
Um dos problemas que estou refatorando consiste em comparar os famosos algoritmos de ordenação e busca para uma lista de 1 milhão de elementos e me deparei revisitando um antigo código meu em python do QuickSort.
Então a seguinte pergunta me veio á mente: Eu sei programar um QuickSort?
Spoiler: Eu não!
QuickSort e Vetorização
Ao atualizar o código começei a estudar a biblioteca de análise de dados Pandas, como eu já tenho bastante familiaridade com o R e pacotes como data.table não foi dificil de pegar o jeito de manipular as tabelas em .csv.
Agora era arrumar os algoritmos de ordenação.
LanguageSort
O primeiro algoritmo que eu atualizei foi o da própria linguagem (basicamente consiste em ordenar a lista pela algoritmo interno da própria linguagem) e foi bem tranquilo de fazer.
QuickSort
O segundo algoritmo foi o clássico QuickSort e como eu estava utilizando o DataFrame do pandas junto com o algorítmo passei umas boas horas tentando encaixar os dois de forma de funcionasse. Foi difícil, mas não impossivel.
MergeSort
O terceiro e ultimo algoritmo foi o MergeSort e assim como no anterior tentei utilizar junto com o DataFrame, foi quando ao estudar me deparei como essa pergunta e derrepente tudo fez sentido....
A dura realizade
Ok...ok, foi meio exagerado, talvez não tão dura...mais para meia-bomba.
A verdade é que eu gosto de estudar algoritmos, compreender como eles funcionam á fundo. Saber a diferença do que acontece, por exemplo, se eu trocar uma recursão por um loop.
Resposta: Você altera a varredura do algoritmo.
Então ao me aprofundar mais na estrutura desses algoritmos acabei descobrindo atualizações mais recentes na forma de faze-los devido á vetorização (map, filter, reduce, etc).
Mas foi também que eu percebi uma coisa que já estava concreta no fundo da minha mente, mas para o R:
Para cada problema, existe uma ferramenta específica.
Não fazia sentido nenhum tentar ordenar um DataFrame pandas com um QuickSort ou MergeSort esses algoritmos existem para listas, essa é a real funcionalidade deles.
Conclusão
Aprendi como programar um QuickSort de memória? Não, e honestamente não esperava que fosse aprender.
Mas o que eu aprendi foi muito mais valioso: Foi a diferença que a forma que se aborda um problema afeta o seu resultado final. A tão famosa complexidade O(nlog(n)) é causada pela recursividade em selecionar o ponto central da lista (mais especificamente, afeta a parte do log(n)).
Caso tenham alguma dica ou queiram conversar estou a disposição.
Obrigado pelo tempo de vocês e caso tenham se interessado visitem o repositório principal Bechmark Languages, ou o pluggin que eu me refiro neste post o bml-python.