Executando verificação de segurança...
3

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.

Carregando publicação patrocinada...
2

Este é um dos assuntos fundamentais para quem lida com ordenação de dados. Geralmente recorremos à funções que realizam esse trabalho pesado. Contudo, para quem está na jornada do aprendizado, sempre vale a pena entender o que ocorre por detrás de uma simples chamada de função.

Apenas para complementar seu post, PedroDrim, encontrei este website que apresenta alguns algoritmos (bubble, selection, insertion, merge, quick, random quick, counting, and radix sort) interativos (claro, existem muitos outros métodos):
https://visualgo.net/en/sorting

Para um pouco mais de teoria, com exemplos animados, tem esse outro aqui:
https://lamfo-unb.github.io/2019/04/21/Sorting-algorithms

Se prefere um vídeo (atenção, podem não ser recomendados para pessoas com epilepsia fotossensível ou fotossensibilidade):
https://youtu.be/Gm8v_MR7TGk
https://youtu.be/kPRA0W1kECg
https://youtu.be/qtRU2Xn76Bc
https://youtu.be/J5WJVMCn2cQ
https://youtu.be/UdTyfJ4zJDA

Dica: Se o vídeo estiver muito rápido, digite essa linha no console do navegador (por enquanto funciona!)...
Super drunk cayote mode
document.getElementsByClassName('html5-main-video')[0].playbackRate=.0625
Coyote mode
document.getElementsByClassName('html5-main-video')[0].playbackRate=1.0
Road-runnar mode
document.getElementsByClassName('html5-main-video')[0].playbackRate=16

Para ativar o pasting (CTRL+V) para dentro do console do navegador (atenção ao que está fazendo ao digitar esse comando!):

allow pasting

Fonte

1

Rapaz, eu lembro quando tive que fazer o meu projeto para avaliação na disciplina de programação avançada, era para implementar 4 códigos de ordenação, um deles era o QuickSort, eu e meus colegas ficamos um tempo tentando tentando até fazer funcionar

Até hoje eu não entendi como funcionou, não sei como funciona, e não sei se estava funcionando certo mas até então eu passei kkkkkkk

O bolha eu consigo do zero kkkkk os outros no mesmo pique também, mas o Quicksort nunca consegui do zero, mas você me deu um desafio legal pra aprender e tentar fazer novamente

0