 |
| Bellacosa Mainframe e alguns algoritmos de ordenação |
☕ Um Café no Bellacosa Mainframe
⚔️ SATOU PENDRAGON E A DUNGEON DOS ALGORITMOS DE ORDENAÇÃO
Bubble Sort, Selection Sort, Insertion Sort, Quicksort, Big-O, recursividade, memória, I/O, SORT, Db2 e o dia em que um programador COBOL descobriu que ORDER BY não era magia.
🎬 PRÓLOGO — SATOU ENCONTROU UM VETOR DESORDENADO
Satou Pendragon já havia enfrentado monstros, labirintos, exércitos e problemas que normalmente exigiriam um grupo inteiro de aventureiros.
Naquela manhã, entretanto, encontrou algo aparentemente muito mais simples:
8 3 7 1 9 2 5
— Satou, precisamos colocar isso em ordem.
O jovem programador COBOL que o acompanhava olhou para a tela.
— Fácil! Coloco em um banco de dados e faço:
SELECT *
FROM TABELA
ORDER BY VALOR;
Satou sorriu.
— E quem você acha que executa o ORDER BY?
Silêncio.
Alguma coisa precisava comparar aqueles valores, movimentá-los e descobrir uma ordem.
Talvez fosse o banco.
Talvez uma biblioteca.
Talvez uma utility.
Talvez o runtime.
Mas o trabalho não desapareceu.
Apenas foi escondido por uma camada de abstração.
Bem-vindo à dungeon dos algoritmos de ordenação.
E cuidado.
O primeiro monstro parece uma bolha.
🏰 CAPÍTULO 1 — QUANDO O PROGRAMADOR PRECISAVA SABER ORDENAR
Durante muito tempo, classificação — ou sorting — fazia parte do repertório básico de praticamente qualquer programador.
Imagine um arquivo contendo:
0007 SILVA 350
0002 SOUZA 120
0009 ALMEIDA 870
0001 COSTA 440
Precisamos gerar um relatório ordenado pelo código do cliente:
0001 COSTA 440
0002 SOUZA 120
0007 SILVA 350
0009 ALMEIDA 870
Hoje podemos pensar imediatamente em SQL, frameworks, bibliotecas ou ferramentas especializadas.
Mas computadores não nasceram sabendo ordenar.
Alguém precisa decidir:
quais elementos comparar;
quando trocar elementos;
quantas vezes repetir a operação;
quanta memória utilizar;
como tratar dados maiores que a memória;
o que fazer quando existem valores repetidos;
quando considerar o trabalho terminado.
Com o crescimento de sistemas gerenciadores de banco de dados e produtos como ADABAS, Db2 e, no universo da microinformática, dBASE, parte dessa responsabilidade deixou de aparecer diretamente no programa de aplicação.
O algoritmo, porém, não morreu.
Ele mudou de endereço.
🧙 CAPÍTULO 2 — ABSTRAÇÃO NÃO É TELETRANSPORTE
Nosso programador iniciante pergunta:
— Então eu realmente não preciso saber isso. O Db2 resolve.
Satou pega uma caneca de café.
— Quando você usa uma ponte, não precisa construir uma ponte. Mas continua sendo útil saber que existe alguma coisa segurando você sobre o rio.
Essa é uma excelente forma de compreender abstração.
Quando escrevemos:
SELECT *
FROM CLIENTES
ORDER BY NOME;
não estamos dizendo:
"Ordenação deixou de existir."
Estamos dizendo:
"Delego a responsabilidade de descobrir uma boa estratégia de ordenação para outra camada."
O mesmo acontece quando utilizamos uma utility de SORT no mainframe.
O desenvolvedor pode especificar as chaves e deixar uma infraestrutura altamente otimizada realizar o trabalho.
Isso é ótimo.
Reutilizar software especializado é engenharia, não preguiça.
O problema começa quando abstração vira desconhecimento.
Um programador não precisa implementar todos os algoritmos que utiliza.
Mas deveria compreender suficientemente bem os fundamentos para perceber quando uma operação aparentemente inocente pode custar uma fortuna em CPU, memória, I/O ou tempo.
🫧 CAPÍTULO 3 — O PRIMEIRO MONSTRO É UMA BOLHA
Bubble Sort é provavelmente um dos algoritmos de ordenação mais conhecidos por estudantes.
Sua ideia é extremamente simples.
Considere:
5 3 8 1 4
Compare os dois primeiros:
5 3
Estão na ordem errada.
Troque:
3 5 8 1 4
Agora compare:
5 8
Estão corretos.
Depois:
8 1
Troque:
3 5 1 8 4
Finalmente:
8 4
Troque:
3 5 1 4 8
Percebeu?
O 8 foi caminhando em direção ao final.
Ele "borbulhou".
Daí o nome Bubble Sort.
Podemos imaginar o algoritmo em pseudocódigo:
REPITA
PARA CADA PAR DE ELEMENTOS VIZINHOS
SE ESQUERDA > DIREITA
TROQUE
FIM-SE
FIM-PARA
ATÉ ESTAR ORDENADO
A grande virtude do Bubble Sort não é performance.
É didática.
Ele permite enxergar claramente:
comparação;
troca;
passagem;
ordenação parcial;
condição de término.
Para quem está começando em COBOL, é uma excelente maneira de compreender arrays, índices e estruturas repetitivas.
⚡ CAPÍTULO 4 — A BANDEIRA QUE SALVA O BUBBLE
Satou encontra:
1 2 3 4 5 6 7 8 9
O aprendiz começa outra sequência enorme de comparações.
— Pare.
— Mas ainda temos várias passadas!
— Você trocou alguma coisa na primeira?
— Não.
— Então por que continuar?
Aqui surge uma pequena otimização extremamente instrutiva.
Criamos uma variável:
HOUVE-TROCA
No começo de cada passada:
HOUVE-TROCA = NÃO
Quando houver troca:
HOUVE-TROCA = SIM
No final:
SE HOUVE-TROCA = NÃO
TERMINAR
Em COBOL, conceitualmente poderíamos possuir algo semelhante a:
01 WS-HOUVE-TROCA PIC X VALUE 'N'.
88 HOUVE-TROCA VALUE 'S'.
88 NAO-HOUVE-TROCA VALUE 'N'.
Essa pequena mudança ensina uma gigantesca lição de engenharia:
Não execute trabalho que você já sabe ser desnecessário.
Guarde essa frase.
Ela reaparecerá em SQL, batch, APIs, loops, VSAM, Db2 e praticamente todo sistema que você conhecer.
🎯 CAPÍTULO 5 — SELECTION SORT E O CAÇADOR DO MENOR
Selection Sort utiliza outra filosofia.
Temos:
8 3 7 2 9
Perguntamos:
Qual é o menor elemento?
Resposta:
2
Colocamos o 2 na primeira posição:
2 3 7 8 9
Agora a primeira posição está resolvida.
Passamos a procurar o menor valor entre as posições restantes.
A filosofia é:
ENCONTRE O MENOR
↓
COLOQUE-O NA POSIÇÃO CORRETA
↓
IGNORE A REGIÃO JÁ RESOLVIDA
↓
REPITA
É extremamente intuitivo.
Imagine organizar livros.
Você procura o primeiro alfabeticamente e coloca na primeira posição.
Depois procura o segundo.
Depois o terceiro.
E assim sucessivamente.
Mas existe um detalhe.
Se recebermos:
1 2 3 4 5 6 7 8 9
Selection Sort tradicional ainda precisa procurar repetidamente o menor elemento da parte restante.
O vetor estar ordenado não produz a mesma vantagem que vimos no Bubble otimizado ou veremos no Insertion Sort.
🃏 CAPÍTULO 6 — INSERTION SORT E AS CARTAS DE SATOU
Satou tira algumas cartas.
Na mão já existem:
3 7 9
Ele recebe:
5
Onde colocar?
Entre 3 e 7.
Resultado:
3 5 7 9
Recebe outra:
4
Resultado:
3 4 5 7 9
Essa é a essência do Insertion Sort.
Em vez de reorganizar tudo a cada instante, mantemos uma parte já ordenada.
Para cada novo elemento:
guardamos o valor;
procuramos sua posição;
deslocamos os maiores;
inserimos o valor;
ampliamos a região ordenada.
Existe uma elegância enorme nessa estratégia.
Principalmente quando os dados já estão quase ordenados.
Imagine:
1 2 3 4 5 7 6 8 9
Existe praticamente apenas uma pequena correção.
Insertion Sort consegue explorar muito bem esse tipo de situação.
E aqui aparece uma lição importante:
As características dos dados importam tanto quanto o algoritmo.
📐 CAPÍTULO 7 — SATOU ABRE O GRIMÓRIO DO BIG-O
Chegamos à pergunta:
Como comparar algoritmos?
Medir segundos ajuda, mas cria problemas.
Um algoritmo executado num computador de 10 MHz e outro numa CPU moderna produzirão tempos completamente diferentes.
Precisamos estudar principalmente como o trabalho cresce quando aumenta o tamanho da entrada.
É aqui que entra a notação Big-O.
Considere:
n = quantidade de elementos
Um algoritmo O(n) cresce aproximadamente de forma linear.
Se dobramos a entrada, esperamos aproximadamente dobrar a quantidade dominante de trabalho.
Já:
O(n²)
é muito mais perigoso.
Se:
n = 5.000
temos como referência:
5.000² = 25.000.000
Agora dobre:
10.000² = 100.000.000
Dobrar os dados produziu aproximadamente quatro vezes o crescimento quadrático dominante.
Bem-vindo à dungeon onde hardware caro começa a chorar.
💥 CAPÍTULO 8 — 674 SEGUNDOS CONTRA 3
No experimento histórico que inspirou nossa aventura, um vetor desordenado com aproximadamente 5.000 elementos apresentou tempos da ordem de:
Bubble 674 segundos
Selection 355 segundos
Insertion 233 segundos
Quicksort 3 segundos
Há inclusive uma provável repetição tipográfica no texto histórico, que chama o terceiro resultado novamente de seleção; pelo contexto, trata-se de inserção.
Mas observe a diferença:
674 / 3 ≈ 225
Mais de duzentas vezes.
Mesmo resultado funcional:
ENTRADA DESORDENADA
↓
SAÍDA ORDENADA
Engenharia completamente diferente.
Essa é uma das razões pelas quais estudar algoritmos continua sendo importante.
Dois programas podem estar funcionalmente corretos e serem economicamente muito diferentes.
Em produção, performance também custa dinheiro.
🧨 CAPÍTULO 9 — ENTRA EM CENA C. A. R. HOARE
No início da década de 1960, Tony Hoare desenvolveu o algoritmo que ficou conhecido como Quicksort.
Aqui precisamos evitar uma simplificação comum.
Quicksort não é simplesmente:
"Bubble Sort que troca elementos mais distantes."
A diferença conceitual é muito mais profunda.
Sua grande arma é o particionamento.
Considere:
9 3 7 1 8 2 5
Escolhemos um pivô.
Por exemplo:
5
Queremos reorganizar os elementos conceitualmente em três regiões:
MENORES | PIVÔ | MAIORES
Podemos chegar a algo semelhante a:
3 1 2 | 5 | 9 8 7
Observe:
3 1 2
ainda não está ordenado.
E:
9 8 7
também não.
Mas aprendemos algo extremamente poderoso:
todos da esquerda < 5
todos da direita > 5
O problema original foi quebrado.
🪆 CAPÍTULO 10 — RECURSIVIDADE: UMA DUNGEON DENTRO DA DUNGEON
Agora aplicamos Quicksort novamente à esquerda:
3 1 2
E novamente à direita:
9 8 7
Temos conceitualmente:
QUICKSORT
│
├── PARTICIONE
│
├── QUICKSORT(esquerda)
│
└── QUICKSORT(direita)
Isso é um exemplo clássico de divide and conquer:
Divida um grande problema em problemas menores da mesma natureza.
Imagine:
5000
↓
2500
↓
1250
↓
625
↓
312
↓
156
↓
78
↓
39
↓
19
↓
9
↓
4
↓
2
↓
1
Quando as divisões são razoavelmente equilibradas, a profundidade cresce aproximadamente como:
log₂(n)
E daí emerge o comportamento esperado clássico do Quicksort:
O(n log n)
Isso explica por que ele pode esmagar algoritmos quadráticos em conjuntos grandes.
☠️ CAPÍTULO 11 — QUICKSORT TAMBÉM TEM UM CHEFÃO SECRETO
Não saia dizendo:
"Quicksort sempre é O(n log n)."
Não é.
O pior caso do Quicksort clássico é:
O(n²)
Tudo depende da estratégia de particionamento e, entre outros fatores, da escolha do pivô.
Se produzirmos repetidamente divisões terríveis:
1 | 999 elementos
depois:
1 | 998
depois:
1 | 997
perdemos grande parte da vantagem do divide and conquer.
Essa é uma excelente aula sobre análise de algoritmos:
melhor caso
caso médio
pior caso
não são necessariamente iguais.
🧪 CAPÍTULO 12 — OS QUATRO VETORES DA DUNGEON
O experimento original utilizava quatro tipos de vetor.
Isso é muito mais sofisticado do que simplesmente testar números aleatórios.
Vetor 1 — crescente
1 2 3 4 5 6 7 8
Já está ordenado.
Vetor 2 — aleatório
7 2 9 1 8 4 3
Representa um caso comum de benchmark.
Vetor 3 — decrescente
9 8 7 6 5 4 3 2 1
Pode ser extremamente ruim para determinadas estratégias.
Vetor 4 — quase tudo igual
55 55 55 55 44 55 55 55 55
Parece uma maluquice.
Não é.
Ele testa como o algoritmo reage a muitas chaves repetidas.
Hoje podemos pensar em:
STATUS
A
A
A
A
A
P
A
A
A
Milhões de registros podem possuir pouquíssimos valores distintos.
Um bom benchmark não pergunta apenas:
"É rápido?"
Pergunta:
"É rápido em quais condições?"
Essa pergunta deveria estar escrita na parede de toda War Room.
📊 CAPÍTULO 13 — O MAPA DOS QUATRO AVENTUREIROS
Como aproximação didática:
| Algoritmo | Melhor caso | Médio | Pior |
|---|
| Bubble otimizado | O(n) | O(n²) | O(n²) |
| Selection | O(n²) | O(n²) | O(n²) |
| Insertion | O(n) | O(n²) | O(n²) |
| Quicksort | O(n log n) esperado | O(n log n) | O(n²) |
Mas Satou imediatamente avisa:
— Não transforme essa tabela numa religião.
Big-O descreve crescimento assintótico.
Não conta sozinho toda a história.
🧠 CAPÍTULO 14 — BIG-O NÃO CONHECE SEU DATACENTER
Imagine dois algoritmos:
A → O(n log n)
B → O(n²)
A parece automaticamente melhor.
Para conjuntos suficientemente grandes, o crescimento assintótico favorece A.
Mas sistemas reais possuem:
Para:
n = 5
um algoritmo teoricamente inferior pode ser mais rápido simplesmente por ser muito simples.
Essa observação explica uma coisa aparentemente absurda:
algoritmos sofisticados podem recorrer ao Insertion Sort quando os subconjuntos ficam pequenos.
Não existe contradição.
Existe engenharia.
🧾 CAPÍTULO 15 — ESTABILIDADE: O DETALHE QUE O RELATÓRIO DESCOBRE
Imagine:
ANA 100
CARLOS 200
MARIA 100
JOÃO 300
PEDRO 100
Ordenamos por valor.
Um sort estável pode produzir:
ANA 100
MARIA 100
PEDRO 100
CARLOS 200
JOÃO 300
ANA, MARIA e PEDRO possuíam a mesma chave 100.
Sua ordem relativa foi preservada.
Isso é estabilidade.
Agora imagine sistemas empresariais contendo:
DATA
HORA
CONTA
SEQUÊNCIA
STATUS
De repente estabilidade deixa de ser curiosidade acadêmica.
Ela pode afetar o resultado esperado de processamentos posteriores.
Bubble e Insertion podem ser implementados de forma estável.
Selection Sort tradicional e Quicksort clássico normalmente não são estáveis.
Moral:
"Está ordenado" não descreve sozinho todas as propriedades relevantes da ordenação.
💾 CAPÍTULO 16 — SATOU ENCONTRA UM ARQUIVO MAIOR QUE A MEMÓRIA
Nosso aprendiz está confiante.
— Entendi! Carrego o arquivo na memória e aplico Quicksort.
Satou olha para o tamanho:
1 TB
Depois olha para a memória disponível ao processo:
16 GB
— Temos um pequeno problema.
Não conseguimos simplesmente carregar tudo.
Aqui aparece a diferença entre ordenação interna e ordenação externa.
Ordenação interna trabalha com dados que podem ser tratados essencialmente na memória disponível.
Ordenação externa precisa considerar armazenamento secundário e I/O.
Uma estratégia conceitual seria:
ARQUIVO GIGANTE
│
├── BLOCO A → SORT ──┐
├── BLOCO B → SORT ──┤
├── BLOCO C → SORT ──┼── MERGE → RESULTADO
└── BLOCO D → SORT ──┘
Ordenamos pedaços.
Depois fazemos merge.
É por isso que famílias de algoritmos de fusão tiveram enorme importância histórica em processamento de arquivos.
📼 CAPÍTULO 17 — QUANDO O SORT TINHA CHEIRO DE FITA MAGNÉTICA
Aqui existe uma curiosidade histórica deliciosa.
Durante a era de processamento sequencial em fitas magnéticas, o acesso aos dados possuía características muito diferentes das de RAM moderna.
Não dava para tratar fita como um array e simplesmente saltar alegremente para qualquer elemento.
Isso tornou estratégias de merge externo fundamentais.
Daí encontramos nomes históricos como:
fusão direta
fusão natural
fusão balanceada multidirecional
classificação polifásica
Esses algoritmos não são fósseis inúteis.
Eles mostram que algoritmos são profundamente influenciados pelo meio físico no qual os dados existem.
Memória muda algoritmo.
Storage muda algoritmo.
Rede muda algoritmo.
Hardware muda algoritmo.
Mas a necessidade de pensar permanece.
🖥️ CAPÍTULO 18 — O PROGRAMADOR COBOL DESCOBRE O SORT
Chegamos ao nosso território.
Em COBOL podemos encontrar construções como:
SORT ARQUIVO-SORT
ON ASCENDING KEY CLIENTE
USING ARQUIVO-ENTRADA
GIVING ARQUIVO-SAIDA.
E no ambiente mainframe existem utilities especializadas de sorting.
Isso significa que deveríamos implementar Quicksort manualmente em todo programa COBOL?
Claro que não.
Conhecer Quicksort e reinventar Quicksort são coisas completamente diferentes.
Se uma infraestrutura de SORT altamente otimizada existe, normalmente queremos aproveitá-la.
O programador especifica:
ENTRADA
CHAVE
ORDEM
SAÍDA
e deixa uma infraestrutura especializada decidir detalhes de execução.
Mas o profissional experiente ainda pensa:
Quantos registros?
Qual o tamanho do registro?
Quanto workspace?
Quanto I/O?
Quais campos são chave?
Há registros duplicados?
Qual a janela batch?
Existe pressão de CPU?
Existe contenção de storage?
É aí que o programador deixa de ser simplesmente alguém que conhece sintaxe COBOL e começa a entender sistemas.
🗄️ CAPÍTULO 19 — O DB2 NÃO USA MAGIA NEGRA
Nosso aprendiz tenta escapar novamente:
SELECT *
FROM TRANSACOES
ORDER BY DATA;
— Pronto.
Satou pergunta:
— Existe índice?
— Não sei.
— Quantas linhas?
— Não sei.
— Qual access path?
— Não sei.
— Houve sort?
— Não sei.
Temos um problema maior que sorting.
Temos programação por esperança.
Um SGBD possui um otimizador justamente para analisar alternativas.
Dependendo da consulta, estruturas existentes e estatísticas, pode ser possível aproveitar uma ordem já fornecida por determinado access path ou pode ser necessário realizar trabalho adicional de ordenação.
Portanto:
ORDER BY
não significa:
CUSTO = ZERO
Significa:
EU PRECISO DO RESULTADO NESTA ORDEM.
Como obter essa ordem é outra história.
⚙️ CAPÍTULO 20 — CPU NÃO É O ÚNICO CHEFÃO
O artigo histórico media segundos numa máquina de aproximadamente 10 MHz.
Era uma forma perfeitamente válida de observar comportamento naquele ambiente.
Hoje, entretanto, precisamos pensar em muito mais coisas.
Considere:
CPU
MEMÓRIA
CACHE
STORAGE
I/O
PARALELISMO
COMPRESSÃO
REDE
Em grandes processamentos empresariais, movimentar dados pode custar mais que compará-los.
Imagine ordenar centenas de gigabytes.
A pergunta deixa de ser apenas:
"Quantas comparações?"
Passa a ser:
"Quanto dado estou movimentando?"
É por isso que otimização moderna não pode ser reduzida à contagem de instruções.
No mainframe, essa conversa rapidamente encontra:
SMF
RMF
WLM
CPU
I/O
elapsed time
service classes
batch window
O algoritmo encontra Capacity Planning.
Satou acaba de chegar à War Room.
🔢 CAPÍTULO 21 — RADIX SORT ENTRA PELA PORTA DOS FUNDOS
Existe outro detalhe fascinante.
Algoritmos baseados exclusivamente em comparação possuem uma barreira teórica da ordem de:
Ω(n log n)
para o problema geral de sorting por comparação.
Mas então alguém pergunta:
— E se eu souber alguma coisa sobre a chave?
Excelente pergunta.
Imagine:
00000017
00000003
00000122
00000045
Algoritmos como Radix Sort exploram a estrutura das próprias chaves.
Em vez de depender exclusivamente de:
A < B?
podem trabalhar com posições/dígitos.
Também encontramos:
Counting Sort
Bucket Sort
Radix Sort
Isso ensina uma lição maravilhosa:
Conhecimento sobre os dados pode mudar o algoritmo disponível.
Para um programador acostumado com campos fixos, PICs, chaves e registros estruturados, isso deveria soar bastante familiar.
🐚 CAPÍTULO 22 — A FAMÍLIA É MUITO MAIOR
Os quatro personagens principais não estão sozinhos.
Existe uma guilda inteira:
Bubble Sort
Selection Sort
Insertion Sort
Quicksort
Shellsort
Heapsort
Merge Sort
Radix Sort
Counting Sort
Bucket Sort
Cocktail/Shaker Sort
Cada um nasceu de determinadas ideias e compromissos.
Shellsort trabalha com inserções usando intervalos que diminuem.
Heapsort explora uma estrutura de heap.
Merge Sort divide e depois combina resultados ordenados.
Cocktail/Shaker Sort lembra Bubble, mas percorre alternadamente direções.
E algoritmos modernos podem ser híbridos.
A frase atribuída no texto antigo a respeito de bons programadores conhecerem várias classificações, mas utilizarem a própria, captura uma ideia interessante quando interpretada com cuidado:
conhecer algoritmos oferece repertório para compreender e escolher ferramentas — não obrigação de reinventá-las.
🤖 CAPÍTULO 23 — A IA APARECE NA DUNGEON
Finalmente nosso aprendiz encontra uma solução definitiva.
— Satou! Agora temos IA!
Ele abre seu assistente favorito:
"Ordene estes dados da maneira mais eficiente."
Código aparece imediatamente.
Problema resolvido?
Satou começa o interrogatório:
Quantos registros?
— Não sei.
Cabe na memória?
— Não sei.
Existem duplicatas?
— Não sei.
Precisa ser estável?
— Não sei.
Está quase ordenado?
— Não sei.
Qual o SLA?
— Não sei.
É batch ou online?
— Não sei.
Quanto I/O podemos consumir?
— Não sei.
Satou fecha o notebook.
A IA consegue produzir código.
Mas alguém ainda precisa compreender o problema.
🧠 CAPÍTULO 24 — QUANTO MAIS ALTA A ABSTRAÇÃO, MAIS IMPORTANTE O FUNDAMENTO
Observe nossa viagem:
ASSEMBLY
↓
LINGUAGENS DE ALTO NÍVEL
↓
COBOL
↓
UTILITIES
↓
SGBDs
↓
FRAMEWORKS
↓
CLOUD
↓
IA GENERATIVA
A cada camada, mais detalhes são escondidos.
Isso é maravilhoso.
É assim que conseguimos construir sistemas cada vez maiores.
Mas existe uma armadilha:
ABSTRAÇÃO ≠ INEXISTÊNCIA
Quando utilizamos Db2, índices continuam existindo.
Quando utilizamos cloud, hardware continua existindo.
Quando utilizamos APIs, rede continua existindo.
Quando utilizamos IA, algoritmos continuam existindo.
Quando utilizamos SORT, alguém continua ordenando.
🧪 CAPÍTULO 25 — LABORATÓRIO PARA O PADAWAN COBOL
Quer realmente aprender?
Não apenas leia.
Experimente.
Crie quatro arrays:
VETOR-1 → crescente
VETOR-2 → aleatório
VETOR-3 → decrescente
VETOR-4 → valores repetidos
Implemente Bubble Sort.
Depois acrescente:
HOUVE-TROCA
Conte:
comparações
trocas
passadas
Não meça apenas segundos.
Depois implemente Selection Sort.
Faça a mesma instrumentação.
Depois Insertion Sort.
Compare.
Para Quicksort, se estiver começando em COBOL, primeiro implemente em pseudocódigo e acompanhe manualmente o particionamento.
Pegue:
9 3 7 1 8 2 5
Escolha:
PIVÔ = 5
E desenhe no papel:
< 5 | 5 | > 5
Depois repita para cada lado.
Você começará a enxergar o algoritmo.
Esse é o momento em que sorting deixa de ser uma receita decorada e vira raciocínio.
🥚 EASTER EGG — O ELEMENTO 03:17
Nos testes, Satou encontra:
55 55 55 55 55 44 55 55 55
— Quem colocou esse 44 aí?
O operador responde:
— Não sei. Apareceu às 03:17.
Silêncio na War Room.
Todo veterano sabe:
se alguma coisa inexplicável aconteceu às 03:17, procure o job batch.
E, por favor, não reinicie nada antes de guardar as evidências.
💡 CAPÍTULO 26 — SETE DICAS PARA QUEM ESTÁ COMEÇANDO
Primeira: não decore apenas Big-O. Entenda por que o algoritmo cresce daquela maneira.
Segunda: teste entradas diferentes. Aleatório não representa o universo inteiro.
Terceira: conte operações. Comparações e movimentações revelam muito.
Quarta: aprenda estabilidade. Em processamento comercial ela pode importar.
Quinta: não reinvente utilities maduras sem motivo. Aprender Quicksort é excelente; substituir um SORT otimizado por seu experimento acadêmico em produção provavelmente não é.
Sexta: olhe além da CPU. Memória e I/O podem dominar o custo.
Sétima: sempre pergunte:
Qual é o tamanho real do problema?
Uma solução fantástica para 100 elementos pode ser desastrosa para 100 milhões.
🏁 EPÍLOGO — SATOU NÃO ESTAVA ENSINANDO SORT
Ao final da dungeon, nosso jovem programador COBOL olha novamente para:
8 3 7 1 9 2 5
Agora ele não vê simplesmente sete números.
Vê possibilidades.
Bubble pergunta:
Quais vizinhos estão invertidos?
Selection pergunta:
Qual elemento deveria ocupar esta posição?
Insertion pergunta:
Onde este novo elemento pertence?
Quicksort pergunta:
Como posso dividir este problema?
E essa talvez seja a maior lição de todas.
Estamos estudando quatro maneiras de ordenar dados, mas estamos aprendendo quatro maneiras de pensar.
BUBBLE
→ corrija pequenos erros locais
SELECTION
→ encontre a próxima escolha correta
INSERTION
→ mantenha uma solução parcial válida
QUICKSORT
→ divida o grande problema em problemas menores
Esses padrões reaparecem muito além de sorting.
Eles aparecem em estruturas de dados, otimização, bancos de dados, compiladores, sistemas distribuídos e engenharia de software.
O computador de 10 MHz desapareceu.
A fita magnética deixou de dominar o datacenter.
ADABAS, Db2, SQL e utilities esconderam boa parte da ordenação.
COBOL evoluiu.
Mainframes ganharam quantidades de memória e capacidade de processamento inimagináveis para os programadores daquela época.
Depois chegaram Java, Python, cloud, containers, APIs, machine learning e IA generativa.
Mas uma pergunta atravessou todas essas gerações:
Existe uma maneira mais inteligente de resolver este problema?
Essa pergunta separa conhecer sintaxe de compreender computação.
Um programador iniciante vê:
ORDER BY CLIENTE
e pensa:
"Está ordenado."
Um programador que começa a compreender sistemas olha para o mesmo comando e pergunta:
Quantos registros?
Qual access path?
Existe índice?
Houve sort?
Quanto custou?
Cabe na memória?
Quanto I/O produziu?
Qual é a distribuição das chaves?
O resultado precisa ser estável?
Existe uma estratégia melhor?
E é nesse instante que o padawan começa sua transformação.
Não porque aprendeu Bubble Sort.
Não porque decorou:
O(n²)
ou:
O(n log n)
Mas porque descobriu que todo comando simples pode esconder uma enorme quantidade de engenharia.
Satou fecha o terminal.
O batch terminou.
Na saída encontramos:
1 2 3 5 7 8 9
O aprendiz comemora.
Satou, naturalmente, pergunta:
— Quanto custou?
Bem-vindo ao mainframe.
Aqui até uma lista perfeitamente ordenada ainda pode abrir um incidente às 03:17.
☕
