Programa didático com testes de desempenho para os métodos de ordenação implementados em Python 2: bubble sort, insertion sort, merge sort, quick_sort e selection_sort.
Programadores mais experientes podem achar exagerado a quantidade de comentários, mas o público alvo são estudantes que estão começando na programação, que não têm nem domínio pleno da linguagem Python nem maturidade em raciocinar na lógica de programação, por isso fizemos um descrição detalhada no código.
Terceiro semestre na Fatec, disciplina Estrutura de Dados ministrada pelo querido mestre Professor Dr. Carlos Magnus Carlson Filho. Simplesmente o melhor curso de Estrutura de Dados da galáxia. Ao professor Carlos fica a eterna gratidão de um eterno aprendiz, obrigado Mestre.
A parte I do curso é toda em linguagem C, não há nada como C para entender alocação de memória e como as coisas num nível mais elementar são estruturadas. A Fatec tem a preocupação de se alinhar ao mercado, então vimos Python, uma linguagem em alta e gostosa de programar que nos foi apresentada no semestre anterior pelo Professor Dr. Henrique Dezani. Logo, na breve parte II do curso de Estrutura de Dados tivemos uma revisão de Python, para posteriormente seguir com a parte III onde veríamos, em Python, estruturas de dados como filas, pilhas, listas ligadas, árvores binárias etc.
Pois bem, na ocasião em que estávamos vendo filas e pilhas, o Professor foi abordar a elegante Programação Recursiva. É aqui que nasce este repositório. O Professor nos forneceu uma implementação de algoritmos de ordenaçao escrito em C. Já havia algumas semanas que estavamos brincando com Python, já estávamos "bem acostumados" com as mordomias de uma linguagem moderna e de repente voltamos a esculpir conceitos no machado.
O que fiz foi passar o programa em C do Carlos para Python 2, a versão da máquina do Professor na época. No aspecto visual está absolutamente igual, mesma saída, mesma interação com o usuário. Agora o professor Carlos não precisa mais revisitar a linguagem C do início do curso, pode permanecer em Python tratando dos conceitos elementares da disciplina que são comuns a qualquer linguagem.
- Primeiro se escolhe o método de ordenação.
Figura 1: Menu 1, escolha do método de ordenação
Veja que temos mais de um tipo de implementação para o mesmo método. bubble sort tem o normal direto e o invertido. O de mesclagem (merge sort) tem o recursivo e o não recursivo. Para o meu preferido quick sort fiz três implementações e acredito ser necessário dar mais informações sobre esse métodos e suas variações.
A primeira implementação (opção 7) é a tradicional, como o método foi inicialmente concebido. Nela o algoritmo mergulha em recorrência sempre pelo particionamento à esquerda do pivô e quando bate no fundo pula para o particionamento à direita do pivô e depois vem subindo nos particionamentos e fazendo o lado direito. Isso é ruim porque se empilha demais, faz muitas chamadas em recorrência. O pior cenário é quando temos vetores ordenados em ordem decrescente. Com um vetor assim, o algoritmo tem de inverter totalmente o vetor e para tanto faria muita recorrência, ocasionando o estouro da pilha (stack over flow).
A segunda implementação do quick sort está na opção 71. Nela a recursividade ocorre em uma partição de cada vez, o que requer um empilhamento de chamadas menor. Ainda assim, no vetor de teste descrescente de 20.000 elementos já há o derramamento da pilha. No quick sort tail1 a recorrência sempre entra pelo mesmo lado, no caso, pelo particionamento à esquerda do pivô. Na realidade, o quick sort da opção 71 é uma preparação para o estudante compreender o quick sort tail2.
A terceira implementação do quick sort da opção 72 é a única em que não ocorre o estouro da pilha de chamadas, mesmo para o vetor descrescente de 40.000 elementos. O quick sort tail2 é uma melhoria do caudal 1, com um critério mais inteligente. Nele a recursividade desce sempre pelo menor particionamento. Depois de encontrar a posição correta do pivô compare-se o tamanho de cada lado e se faz a recorrência na partição menor. Dessa forma, além de atacar apenas uma partição por vez, ataca-se a partição menor, sendo assim, o mergulho na recursividade não é tão fundo, retorna-se mais rápido pois a pilha de chamada é mais rasa, é menor.
- Após a escolha do algoritmo de ordenação temos um segundo menu para fazermos a escolha do teste de carga ao qual o algoritmo será submetido.
Figura 2: Menu 2, escolha do tipo de teste
A opção 1 é uma inspeção visual do comportamento do método.
Sempre usamos o mesmo vetor de oito elementos e imprimimos todos os passos da ordenação. Dessa forma, fica fácil checar as movimentações dos elementos pelo algorítmo e comparar seu modus operandi com os demais métodos.
Na figura a seguir, vemos as permutas dos elementos realizadas pelo bubble sort a cada passada do loop. Mentalmente visualizamos a bolha ao redor número 11, o 5° elemento do vetor, deslocando-o para o início do vetor a cada passo.
Figura 3: Bubble sort, etapas da ordenação
Nas opções 2 e 3 criamos vetores de 20 mil e 40 mil, respectivamente, com valores tomados aleatóriamente.
Aplicamos o método de ordenação escolhido e mostramos o tempo necessário para completar a ordenação. Com esses vetores o estudante pode fazer a comparação de desempenho entre os algoritmos, comparando os tempos de um e de outro. Por exemplo, aplicamos o método de ordenação bubble sort a um vetor randômico de 40 mil elementos e o resultado está na figura 4. Na figura 5 temos o desempenho do quick sort tail 2 para um vetor semelhante, de 40 mil elementos gerados aleatóriamente.
Figura 4: Desempenho do bubble sort
Figura 5: Desempenho do quick sort recursivo
Nesse caso específico, enquanto o bubble sort levou 84 segundos para ordenar o vetor, o quick sort levou apenas 5 centésimos de segundo. Mostrando que o método da bolha é pop, talvez o mais famoso, mas tem um desempenho sofrível.
Nas opções 4 e 5 criamos vetores de 20 mil e 40 mil, respectivamente, com valores já ordenandos, mas em ordem decrescente. Nesta situação, o método de ordernação tem de inverter totalmente o vetor e isso pode ser extremamente custoso em recursos computaionais para alguns algoritmos.
Um exemplo está na figura 6. Escolhemos no menu a opção 7.1, um tipo de implementação do quicksort recursivo em que estora a pilha de chamadas. Já com a segunda forma de implementar o quicksort recursivamente da opção 7.2 o estouro não acontece.
Figura 6a: Estouro da pilha de chamada
Figura 6b: Estouro da pilha de chamada
Precisa do Python instalado. Se usa GNU/Linux, provavelmente já possui alguma versão do Python instalada por padrão.
Verifique com o comando:
python --versionOutput: Python 3.10.6
Caso não esteja instalado, instale com os comandos abaixo:
sudo apt updatesudo apt install python3Baixe o arquivo metodos_ordenacao.py e no mesmo diretório execute o comando:
python metodos_ordenacao.pyBaixe o arquivo metodos_ordenacao.py e forneça permissão de execução ao arquivo:
chmod +x metodos_ordenacao.pyE execute com:
./metodos_ordenacao.pySe encontrar algum erro na linha 1 devido a #!/usr/bin/env python3 dê o comando
whereis pythonE corrija o path do python pela saída do whereis, ficaria algo assim: #!/usr/bin/python
Pode executar no próprio navegar usando o Google Colab 
Crie um novo notebook e cole o código de metodos_ordenacao.py e aperte o play.
No código do arquivo metodos_ordenacao.py há comentários padronizados segundo as recomendações para se gerar uma documentação html. Execute os comandos a seguir para gerar essa documentação na sua própria máquina. O html gerado pode ser visto AQUI.
- Instale o gerenciador de pacotes do Python, o pip
sudo apt install python3-pip;
- Peça para o pip instalar a biblioteca de geração de documentação pydoc
sudo python3 -m pip install pdoc3;
- Agora pede pro pydoc gerar a documentação
python3 -m pdoc --html metodos_ordenacao.py;
Se não der certo, tente esse outro. Deverá criar o arquivo html/metodos_ordenacao.html.
PYTHONPATH=. pdoc --html metodos_ordenacao.py;