Push_Swap – sobrevivendo a 4 algoritmos e 1 mês de Big-O na 42SP · ciproterona

Olaaá, pessoal do Tab! Sophia aqui de novo! 👋

Finalmente entrei no quarto projeto do Common Core da 42, o Push_Swap (o clássico focado em algoritmos e complexidade). Só que o currículo mudou na nova turma: agora o projeto é feito em dupla e a quantidade de algoritmos exigidos aumentou bastante, o que deixou tudo bem mais interessante (leia-se: difícil). Nesse post eu conto como foi desenvolver isso durante um mês, os perrengues que passamos e os números que conseguimos no final.

O que mudou no subject

Se você conhece a versão clássica do Push_Swap, esquece. A versão nova pede pelo menos 4 estratégias de ordenação diferentes, todas rodando dentro do mesmo binário e selecionáveis em tempo de execução:

--simple: um algoritmo O(n²)
--medium: um algoritmo O(n√n)
--complex: um algoritmo O(n log n)
--adaptive (padrão): escolhe automaticamente a estratégia com base na desordem da entrada

E não é desordem "no chute" - o subject define uma métrica objetiva: conta todos os pares fora de ordem e divide pelo total de pares possíveis, dando um número entre 0 e 1. Com base nesse valor, o modo adaptativo tem que respeitar faixas de complexidade:

Desordem	Complexidade exigida
< 0.2	`O(n²)`
0.2 – 0.5	`O(n√n)`
≥ 0.5	`O(n log n)`

Ou seja: não basta ter os 4 algoritmos prontos, você precisa justificar matematicamente por que a troca de estratégia acontece onde acontece.

Escolhendo os algoritmos

Eu e minha dupla decidimos ir com:

Simple Sort (O(n²)) - praticamente uma inserção adaptada pra pilha, pro caso de baixa desordem;
Chunk Sort (O(n√n)) - divide os valores em faixas (√n chunks) e empurra cada faixa pra pilha b antes de reinserir ordenado;
Binary LSD Radix Sort (O(n log n)) - esse foi o queridinho pra listas grandes e bagunçadas, já que ele não depende de comparação, só de bits.

Para a estrutura de dados, usamos uma lista circular duplamente encadeada. Isso facilita muito o acesso ao topo e ao fundo da pilha, o que é essencial pros rotate (ra/rb) e reverse rotate (rra/rrb) - sem isso você fica refém de percorrer a lista inteira toda vez que precisa "girar" a pilha - a menos que você adicione uma calda a ela.

Dividindo o trabalho

Como o projeto agora é em dupla, a organização virou parte do desafio também. Ficou assim:

Eu: os 4 algoritmos de ordenação + o modo --bench (métricas de desordem, contagem de operações por tipo, etc).
Minha dupla: as operações básicas (sa, pb, rr...), a CLI/parsing de argumentos e a caça a vazamentos de memória com Valgrind.

Recomendo fortemente definir essa divisão antes de escrever a primeira linha de código - evita muito retrabalho e discussão de quem mexeu em quê depois. Fazer calls em live codificando e planejando também é muito bom (infelizmente não dá mais pra fazer pelo Discord).

O bug bobo que quase me deixou maluca

Durante os testes do Chunk Sort, o sort_medium simplesmente não passava no checker - a pilha a saía quase ordenada, mas o checker acusava KO do nada, sem erro de lógica aparente no algoritmo em si.

Depois de um bom tempo isolando o problema, achamos o culpado no rr.c: as chamadas de write() estavam usando 3 como tamanho no lugar de 4. Resultado? O \n no final de cada operação era silenciosamente descartado, e o checker recebia strings de operações grudadas umas nas outras (tipo rrpb em vez de rr\npb\n), o que invalidava a leitura da instrução seguinte.

O que aprendi? quando o algoritmo parece certo mas o resultado dá errado, suspeite primeiro da camada de I/O, não da lógica. Foi um 1 de diferença numa constante que custou horas de debug.

Otimizando o Chunk Sort com simulação

Depois de corrigir o bug, partimos pra otimização de verdade: encontrar a constante ideal de tamanho de chunk pro --medium, mirando o teto de 5.000 operações para 500 números (a faixa de "excelente" do benchmark oficial é abaixo de 5.500).

Em vez de ficar recompilando o push_swap em C a cada tentativa, simulei a lógica de ordenação em Python e rodei um parameter sweep variando a constante de chunk contra listas aleatórias de 500 elementos. Isso deu uma resposta muito mais rápida do que testar direto em C, e ajudou a encontrar um valor de chunk que ficasse consistentemente dentro da meta.

Os números finais

Tamanho	Operações (nosso resultado)	Meta "excelente"
100 números	~570 (Medium)	< 700
500 números	~5.035 (Medium), 6.784 (Complex)	< 5.500

Batemos as duas metas de "excelente" do subject, o que nos deu uma folga boa pra defesa, sem precisar torcer pra pegar uma lista de teste na sorte. O Complex sempre bate 6.784 com 500 números, por matemática mesmo pelas comparações entre bits. Eu deveria ter pesquisado formas de contornar isso ou usar outro algoritmo, como o Turk Algorithm.

O que eu levo desse projeto

Trabalhar em dupla num projeto de algoritmo puro é diferente de fazer sozinha: você precisa alinhar não só o quê fazer, mas como documentar decisões pra que a outra pessoa consiga defender sua parte também. E o bug do rr.c me lembrou de novo que otimização prematura é besteira se você nem confirmou que a saída tá correta primeiro - corrigir o básico veio antes de qualquer ganho de performance.

Se quiser dar uma olhada no código, tá tudo aqui:

🔗 GitHub: https://github.com/ciproterona/42_push_swap

Todos são livres pra abrir Issues apontando problemas e como corrigi-los, mas Pull Requests não serão aceitos por ser tratar de um projeto 100% educacional.

E você? Como foi sua entrada no mundo dos algoritmos e Big-O?

Até a próxima! 🚀