<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Santos on Medium]]></title>
        <description><![CDATA[Stories by Santos on Medium]]></description>
        <link>https://medium.com/@c137santos?source=rss-a4d176dcd2e6------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*QYNm-O0y5dcOFSyfcbukvQ.jpeg</url>
            <title>Stories by Santos on Medium</title>
            <link>https://medium.com/@c137santos?source=rss-a4d176dcd2e6------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Thu, 19 Nov 2026 19:13:04 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@c137santos/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Melhores práticas de Padrões de Design: otimizando desempenho da Amazon S3]]></title>
            <link>https://c137santos.medium.com/melhores-pr%C3%A1ticas-de-padr%C3%B5es-de-design-otimizando-a-desempenho-da-amazon-s3-f08ea0c472f3?source=rss-a4d176dcd2e6------2</link>
            <guid isPermaLink="false">https://medium.com/p/f08ea0c472f3</guid>
            <category><![CDATA[devops]]></category>
            <category><![CDATA[best-practices]]></category>
            <category><![CDATA[amazon]]></category>
            <category><![CDATA[aws]]></category>
            <category><![CDATA[translate-text]]></category>
            <dc:creator><![CDATA[Santos]]></dc:creator>
            <pubDate>Thu, 02 Jan 2025 17:59:25 GMT</pubDate>
            <atom:updated>2025-11-15T13:30:10.037Z</atom:updated>
            <content:encoded><![CDATA[<h4>Anotando e resumido em PT/BR</h4><p>A série “Anotando e Resumido em PT/BR” dispõe de conteúdos importantes traduzido e resumidos para serem encontrados nos googles da vida.</p><blockquote>“Best Practices Design Patterns: Optimizing Amazon S3 Performance AWS Whitepaper” — <a href="https://d1.awsstatic.com/whitepapers/AmazonS3BestPractices.pdf">https://d1.awsstatic.com/whitepapers/AmazonS3BestPractices.pdf</a></blockquote><h4>Introdução</h4><p>As aplicações podem alcançar, facilmente, o desempenho de milhares de transações por segundo, enviando e recuperando dados na Amazon S3. Este escala, automaticamente, para altas taxas de requisição.</p><p>Por exemplo, uma aplicação pode alcançar pelo menos 3.500 requisições PUT/COPY/POST/DELETE e 5.500 requisições GET/HEAD por segundo para cada prefixo em um bucket. (<em>by Santos: prefixo são como pastas, servem para organizar, agrupar e filtrar objetos dentro de um bucket</em>).</p><p>Não há limites para o número de prefixos em um bucket. É possível aumentar o desempenho de leitura ou gravação paralelizando as leituras. Por exemplo, ao criar 10 prefixos em um bucket do Amazon S3 para paralelizar leituras, o desempenho de leitura pode ser escalado para 55.000 requisições de leitura por segundo.</p><p>Algumas aplicações de data lake no Amazon S3 escaneiam milhões/bilhões de objetos para consultas. O que abrangem petabytes de dados. Essas aplicações de data lake alcançam taxas de transferência por instância que maximizam o uso da interface de rede de suas instâncias do Amazon EC2, que podem chegar a<strong> 100 Gb/s em uma única instância</strong>. Essas aplicações agregam a taxa de transferência entre várias instâncias para alcançar múltiplos terabits por segundo.</p><p>Outras aplicações, como as de mensagens em redes sociais, são sensíveis à latência. Essas aplicações podem alcançar latências consistentes para objetos pequenos em torno de 100 a 200 milissegundos (ou latências de saída do primeiro byte para objetos maiores). <em>(By Santos: Ou seja, essas aplicação necessitam de um desempenho estável e confiável, com os tempos de resposta mantendo-se dentro do intervalo esperado)</em></p><p>Outros serviços da AWS também podem ajudar a acelerar o desempenho para diferentes arquiteturas de aplicações. Por exemplo, se for necessário alcançar taxas de transferência mais altas em uma única conexão HTTP ou latências de milissegundos em dígitos únicos, recomenda-se o uso do Amazon CloudFront ou do Amazon ElastiCache para caching com o Amazon S3.<em> (By Santos: ‘em dígito único’ significa que a latência é inferior a 10 milissegundos)</em></p><p>Além disso, para transferência rápida de dados a longas distâncias entre um cliente e um bucket do S3, pode-se usar o Amazon S3 Transfer Acceleration. Este recurso utiliza as localizações de borda globalmente distribuídas do CloudFront para acelerar a transferência de dados entre grandes distâncias geográficas.</p><p>Se a carga de trabalho no Amazon S3 utilizar criptografia no lado do servidor com o AWS Key Management Service (SSE-KMS), é importante consultar os limites do AWS KMS no <em>AWS Key Management Service Developer Guide</em> sobre as taxas de requisição suportadas para o seu caso de uso.</p><h4>1. Diretrizes de Desempenho para o Amazon S3</h4><p><strong>a) Medir a performace / o desempenho</strong></p><p>Ao otimizar o desempenho, é importante avaliar o throughput de rede, os requisitos de CPU e de DRAM (Memória Dinâmica de Acesso Aleatório). Dependendo da combinação de exigências para esses recursos, pode ser vantajoso considerar diferentes tipos de instâncias do Amazon EC2. (<em>by Santos: EC2 é a configuração das máquinas — S3 é armazenamento)</em></p><p>Também é útil analisar o tempo de consulta DNS, latência e velocidade de transferência usando ferramentas de análise HTTP ao medir desempenho.</p><p><strong>b) Escalonar conexões de armazenamento horizontalmente</strong></p><p>Distribuir requisições entre várias conexões é um padrão comum de design para escalar o desempenho horizontalmente. Ao construir aplicações de alto desempenho, pense no Amazon S3 como um sistema distribuído de grande escala, e não como um único ponto de rede, como um servidor de armazenamento tradicional. O melhor desempenho realiza múltiplas requisições simultâneas ao Amazon S3.</p><p>Distribua essas requisições por conexões separadas para maximizar a largura de banda disponível do Amazon S3. O Amazon S3 não impõe limites para o número de conexões feitas ao seu bucket.</p><p><strong>c) Use Busca por Intervalo de Bytes</strong></p><p>Ao utilizar o cabeçalho HTTP Range em uma solicitação GET, você pode buscar um intervalo de bytes de um objeto, transferindo apenas a parte especificada.</p><p>É possível usar conexões simultâneas ao Amazon S3 para buscar diferentes intervalos de bytes dentro do mesmo objeto. Isso ajuda a alcançar um throughput agregado maior em comparação com uma única solicitação de objeto completo. Buscar intervalos menores de um objeto grande também permite que sua aplicação melhore os tempos de nova tentativa quando as requisições são interrompidas.</p><pre>curl -H &quot;Range: bytes=1500-1999&quot; -o parte_do_arquivo_final.dat http://exemplo.com/arquivo_grande.dat</pre><p>Geralmente, a solicitações de intervalo em bytes são de 8MB ou 16MB.</p><p>Para melhor desempenho, se os objetos forem enviados usando um upload multipart, é uma boa prática recuperá-los nos mesmos tamanhos de parte (ou pelo menos alinhados aos limites das partes).</p><p>As solicitações GET podem acessar diretamente partes individuais; por exemplo, GET?partNumber=N.</p><p><strong>d) Retry request (retentativa de request) para aplicações sensíveis à latência.</strong></p><p>Timeouts e retentativas configuradas de forma agressivas (<em>by Santos</em>: <em>que agem rapidamente em caso de falha ou de um tempo de resposta elevado</em>) ajudam a manter a latência consistente.</p><p>Dada a grande escala do Amazon S3, se a primeira solicitação for lenta, uma solicitação repetida provavelmente seguirá um caminho diferente e terá sucesso rapidamente. (<em>by Santos:</em> <em>Desvio de caminhos lentos, uma nova tentativa pode ser direcionada para um caminho diferente, que pode ser mais rápido</em>).</p><p>Os SDKs da AWS possuem valores configuráveis de timeout e retentativas ajustáveis.</p><p><strong>e) Combine Amazon S3 (Armazenamento) e Amazon EC2 (Computação) na mesma Região da AWS</strong></p><p>Embora os nomes dos buckets do Amazon S3 sejam globalmente únicos, cada bucket é armazenado em uma região específica escolhida no momento de sua criação.</p><p>Para otimizar o desempenho, é recomendado acessar o bucket a partir de instâncias do Amazon EC2 localizadas na mesma região da AWS sempre que possível. Isso ajuda a reduzir a latência da rede e os custos de transferência de dados.</p><p><strong>f) Use o Amazon S3 Transfer Acceleration para Minimizar a Latência Causada pela Distância</strong></p><p>O Amazon S3 Transfer Acceleration facilita transferências rápidas, simples e seguras de arquivos ao longo quando há grandes distâncias geográficas entre o cliente e um bucket do S3.</p><p>Ele utiliza as localizações de borda globalmente distribuídas do Amazon CloudFront. Assim que os dados chegam a uma localização de borda, são roteados para o Amazon S3 por meio de um caminho de rede otimizado.</p><p>O Transfer Acceleration é ideal para transferências regulares de gigabytes ou terabytes de dados entre continentes. Também é útil para clientes que enviam dados para um bucket centralizado a partir de diferentes partes do mundo.</p><p>Você pode usar a ferramenta <strong>Amazon S3 Transfer Acceleration Speed Comparison</strong> para comparar velocidades de upload com e sem aceleração em várias regiões do Amazon S3. Essa ferramenta utiliza uploads multipartes para transferir um arquivo do seu navegador para diferentes regiões do S3, permitindo avaliar a eficiência do Amazon S3 Transfer Acceleration.</p><p><strong>g) Use a Versão Mais Recente dos SDKs da AWS</strong></p><p>Os SDKs da AWS oferecem suporte nativo para muitas das diretrizes recomendadas de otimização de desempenho do Amazon S3. Eles fornecem uma API simplificada para integrar o Amazon S3 em suas aplicações e são atualizados regularmente para incorporar as melhores práticas mais recentes. Por exemplo, os SDKs incluem lógica para reexecutar automaticamente requisições em caso de erros HTTP 503 e têm código otimizado para responder e se adaptar a conexões lentas.</p><p>Os SDKs também disponibilizam o <strong>Transfer Manager</strong>, que automatiza o escalonamento horizontal de conexões, permitindo atingir milhares de requisições por segundo ao utilizar requisições de intervalo de bytes (byte-range requests) quando apropriado. É fundamental usar a versão mais recente dos SDKs da AWS para aproveitar os recursos mais atualizados de otimização de desempenho.</p><p>Ao usar a REST API, siga as mesmas boas práticas implementadas nos SDKs: configure timeouts e retentativas para lidar com requisições lentas e aproveite conexões múltiplas para buscar dados de objetos em paralelo.</p><h4>2. <strong>Padrões de Design para Desempenho no Amazon S3</strong></h4><p>Ao projetar aplicações para upload e recuperação de dados no Amazon S3, utilize os padrões de design recomendados para alcançar o melhor desempenho para sua aplicação. Também oferecemos <strong>Diretrizes de Desempenho</strong> para serem consideradas ao planejar a arquitetura da sua aplicação.</p><p><strong>a) Uso de Cache para Conteúdo Frequentemente Acessado</strong></p><p>Muitas aplicações que armazenam dados recebem a mesma solicitação repetidamente pelos usuários. Se houver repetidas requisições <strong>GET</strong> para um conjunto comum de objetos, você pode usar um cache como <strong>Amazon CloudFront</strong>, <strong>Amazon ElastiCache</strong> ou <strong>AWS Elemental MediaStore</strong> para otimizar o desempenho.</p><p>A adoção bem-sucedida de cache pode resultar em <strong>baixa latência</strong> e <strong>altas taxas de transferência de dados</strong>. Aplicações que utilizam cache também enviam menos requisições diretas ao Amazon S3, o que ajuda a reduzir os custos de requisição.</p><p>O <strong>Amazon CloudFront</strong> é uma rede de entrega de conteúdo (<strong>CDN</strong>) rápida que realiza o cache transparente de dados do Amazon S3 em uma grande rede de pontos de presença (<strong>PoPs</strong>) distribuídos geograficamente.</p><p>Quando objetos podem ser acessados em múltiplas regiões ou pela internet, o CloudFront permite que os dados sejam armazenados em cache próximos aos usuários que os acessam. Isso pode resultar em uma entrega de alto desempenho para o conteúdo popular armazenado no Amazon S3.</p><p>O <strong>Amazon ElastiCache</strong> é um serviço gerenciado de cache em memória. Com o ElastiCache, você pode provisionar instâncias Amazon EC2 que armazenam objetos em memória. Esse armazenamento em cache resulta em uma <strong>redução significativa na latência de requisições GET</strong> e em um <strong>aumento substancial na taxa de download</strong>.</p><p>Para usar o ElastiCache, você deve modificar a lógica da aplicação para popular o cache com os objetos mais acessados e verificar o cache antes de requisitar os objetos do Amazon S3.</p><p>O <strong>AWS Elemental MediaStore</strong> é um sistema de cache e distribuição de conteúdo criado especificamente para <strong>fluxos de vídeo</strong> e entrega de mídia a partir do Amazon S3.</p><p>O MediaStore fornece <strong>APIs de armazenamento de ponta a ponta</strong> projetadas para vídeo e é recomendado para cargas de trabalho de vídeo sensíveis ao desempenho. Para mais informações sobre o MediaStore, consulte o <strong>AWS Elemental MediaStore User Guide</strong>.</p><p><strong>b) Timeouts e Retentativas para Aplicações Sensíveis à Latência</strong></p><p>Existem situações em que uma aplicação recebe uma resposta do <strong>Amazon S3</strong> indicando que uma <strong>retentativa</strong> é necessária. O Amazon S3 mapeia nomes de buckets e objetos aos dados associados a eles. Se uma aplicação gerar <strong>taxas elevadas de requisições</strong> (geralmente taxas sustentadas de mais de <strong>5.000 requisições por segundo</strong> para um pequeno número de objetos), ela pode receber <strong>respostas HTTP 503</strong> de <strong>“slowdown”</strong>.</p><p>Quando esses erros ocorrem, cada <strong>AWS SDK</strong> implementa automaticamente uma lógica de retentativa usando <strong>exponential backoff</strong>. Caso você <strong>não esteja usando um AWS SDK</strong>, é importante implementar uma lógica de retentativa ao receber o erro HTTP 503.</p><p>O Amazon S3 realiza o escalonamento automático em resposta a novas taxas de requisição sustentadas, otimizando dinamicamente o desempenho. Durante o período de otimização interna para uma nova taxa de requisições, você pode receber respostas temporárias HTTP 503 até que a otimização seja concluída. Após a otimização, as requisições são geralmente atendidas sem necessidade de retentativas.</p><p>Para aplicações sensíveis à latência, o Amazon S3 recomenda monitorar e retentar agressivamente operações mais lentas. Ao retentar uma requisição, é recomendável usar uma nova conexão com o Amazon S3 e realizar uma nova resolução DNS.</p><p><strong>Requisições Grandes (variáveis): A</strong>cima de 128 MB, é aconselhável monitorar a taxa de transferência obtida e retentar as 5% mais lentas.</p><p><strong>Requisições Pequenas: M</strong>enos de <strong>512 KB</strong>, onde as latências médias geralmente estão na faixa de dezenas de milissegundos, a orientação é a retentar uma operação <strong>GET</strong> ou <strong>PUT</strong> após <strong>2s. </strong>Se for necessário retentar novamente, use um <strong>backoff exponencial</strong>. Ex: 1ª retentativa após <strong>2s, 2º </strong>retentativa após <strong>4s adicionais</strong>.</p><p><strong>Requisições de Tamanho Fixo: </strong>é possível esperar <strong>tempos de resposta mais consistentes</strong>. Nesse caso, identifique <strong>o 1% mais lento</strong> das requisições e retentá-las. Geralmente, <strong>uma única retentativa</strong> já reduz a latência.</p><p><strong>Observações sobre AWS KMS:</strong></p><p>Se você estiver utilizando o <strong>AWS Key Management Service (AWS KMS)</strong> para <strong>criptografia do lado do servidor</strong>, consulte as <a href="https://docs.aws.amazon.com/kms/latest/developerguide/requests-per-second.html"><strong>Quotas no AWS KMS Developer Guide</strong></a> para informações sobre as taxas de requisição suportadas para o seu caso de uso.</p><p><strong>c) Escalonamento Horizontal e Paralelização de Requisições para Alta Taxa de Transferência</strong></p><p>O <strong>Amazon S3</strong> é um sistema distribuído em larga escala. Para ajudar a aproveitar essa escalabilidade, recomendamos o <strong>escalonamento horizontal</strong> das <strong>requisições paralelas</strong> para os endpoints do serviço Amazon S3. Além de distribuir as requisições internamente no Amazon S3, essa abordagem também ajuda a <strong>distribuir a carga</strong> através de múltiplos caminhos na rede.</p><p>Para <strong>transferências de alta taxa de transferência</strong> (<strong>high-throughput</strong>), o Amazon S3 sugere usar aplicações que <strong>utilizem múltiplas conexões</strong> para <strong>GET</strong> ou <strong>PUT</strong> de dados em paralelo.</p><p>Isso é suportado pelo <strong>Amazon S3 Transfer Manager</strong> no <strong>AWS Java SDK</strong>. A maioria dos outros <strong>AWS SDKs</strong> também fornece estruturas similares.</p><p>Para algumas aplicações, é possível obter conexões paralelas iniciando <strong>requisições simultâneas</strong> em diferentes <strong>threads</strong> da aplicação ou em diferentes <strong>instâncias da aplicação</strong>. A <strong>melhor abordagem</strong> depende da estrutura da aplicação e do formato dos objetos que estão sendo acessados. Recomendações para Transferências de Alta Taxa</p><ol><li><strong>Uso de AWS SDKs</strong> para emitir requisições <strong>GET</strong> e <strong>PUT</strong> diretamente. Isso ajusta a carga de trabalho diretamente, mantendo os benefícios do suporte a retentativas e ao tratamento de <strong>respostas HTTP 503</strong>.</li><li><strong>Requisições Concorrentes por Intervalos de Bytes. </strong>Ao fazer <strong>download</strong> grandes dentro de uma Região do Amazon S3 para o Amazon EC2:</li></ol><ul><li>Faça <strong>requisições concorrentes</strong> por <strong>intervalos de bytes</strong> do objeto com granularidade de <strong>8–16 MB</strong>.</li><li>Realize <strong>uma requisição concorrente</strong> para cada <strong>85–90 MB/s</strong> de throughput de rede desejado. ( 85–90 MB por seguindo, geralmente, é um <em>upload ou download ideal de uma única conexão http. E throughput significa vazão, ou volume de dados que pode ser escoado utilizando mesmo ponto. by Santos)</em></li><li>Para saturar uma placa de rede (<strong>NIC</strong>) de <strong>10 Gb/s</strong>, utilize cerca de <strong>15 requisições concorrentes</strong> em conexões separadas.</li><li>Para NICs mais rápidas (ex.: <strong>25 Gb/s</strong> ou <strong>100 Gb/s</strong>), aumente o número de <strong>requisições concorrentes</strong> em conexões adicionais.</li></ul><p><strong>3. Merça o desempenho </strong>para encontrar o número ideal de requisições concorrentes:</p><ul><li>Comece com uma única requisição por vez e <strong>avalie a largura de banda</strong> e o uso de recursos (ex.: CPU, memória).</li><li>Identifique o <strong>gargalo</strong> (recurso com maior utilização) e ajuste o número de requisições simultâneas. Ex: Se processar uma única requisição utiliza <strong>25% da CPU</strong>, isso sugere que até <strong>4 requisições concorrentes</strong> podem ser suportadas.</li><li>Confira a <strong>utilização dos recursos</strong> à medida que a taxa de requisições aumenta.</li></ul><ol><li><strong>Uso do REST API: Se usa REST API</strong> do Amazon S3 diretamente, recomenda-se:</li></ol><ul><li>Utilizar um <strong>pool de conexões HTTP</strong>.</li><li><strong>Reutilizar</strong> cada conexão para uma série de requisições, evitando a configuração de conexão por requisição. Isso elimina a necessidade de <strong>TCP slow-start</strong> e <strong>handshakes SSL</strong> a cada requisição.</li><li>Para mais informações sobre o uso da REST API, consulte a <a href="https://docs.aws.amazon.com/AmazonS3/latest/API/Welcome.html"><strong>Introdução à API REST do Amazon S3</strong></a>.</li></ul><p>Atenção ao DNS: Garanta que as requisições estejam distribuídas em um <strong>pool amplo de endereços IP</strong> do Amazon S3:</p><ul><li>As <strong>consultas DNS</strong> para o Amazon S3 percorrem uma <strong>grande lista de endpoints de IP</strong>.</li><li><strong>Resolvers de cache</strong> ou código da aplicação que reutilizam um <strong>único endereço IP</strong> não aproveitam a <strong>diversidade de endereços</strong> e o <strong>balanceamento de carga</strong> associado.</li></ul><p><strong>Ferramentas de rede</strong> como o comando <strong>netstat</strong> podem ser usadas para verificar os <strong>endereços IP</strong> em uso para comunicação com o Amazon S3.</p><p><strong>d) Uso do Amazon S3 Transfer Acceleration para Acelerar Transferências de Dados Geograficamente Distantes</strong></p><p><em>Deixando um pt/br explicando o transfer acceleration bem simples no </em><a href="https://www.youtube.com/watch?v=s1I7yXctRL8"><em>YouTube</em></a></p><p>O <strong>Amazon S3 Transfer Acceleration</strong> reduz ou elimina a latência causada pela distância geográfica entre clientes globalmente distribuídos e uma aplicação regional que utiliza o Amazon S3. Ele aproveita os edge locations (<strong>locais de borda</strong>— pequeno servidor de cache) distribuídos globalmente no <strong>CloudFront</strong> para acelerar a transferência de dados.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*odwp3jS4ixuiVfJ4" /><figcaption>Edge location da AWS — computadores físicos usado como servidores para o CloudFront</figcaption></figure><p><strong>Rede Global de Pontos de Presença (PoPs)</strong> conta com mais de 50 locais de presença. Essa infraestrutura é usada para distribuir conteúdo via CloudFront, responder rapidamente a consultas DNS feitas ao Amazon Route 53 e acelerar transferências de dados para e do Amazon S3.</p><p><strong>Cenários Ideais de uso </strong>é para transferência de dados entre continentes ou longas distâncias geográficas. Possuem conexões de internet rápidas, lidam com objetos grandes e uploads de grandes volumes de conteúdo.</p><p><em>Se sua conexão for lenta, você ainda pode usar o Transfer Acceleration, mas os ganhos de performance podem não ser tão significativos. Essa recomendação é mais para garantir que você tire o </em><strong><em>máximo benefício possível</em></strong><em> do serviço remediando as longas distâncias. (By santos)</em></p><p><strong>Como Funciona? </strong>À medida que os dados chegam a um edge location (<strong>local de borda)</strong>, eles são roteados para o <strong>Amazon S3</strong> por meio de um <strong>caminho de rede otimizado prórprio da AWS.</strong></p><p>A melhoria de velocidade geralmente aumenta com a <strong>distância da região do Amazon S3</strong>. Ou seja, quanto mais longe cliente - servidor, mais o transfer otimizará o caminho.</p><p>Habilitar o transfer acceleration pode ser em bucket novos ou existentes. Será usado um endpoint separado do Amazon S3 Transfer Acceleration para acessar os edge location da AWS.</p><p>Utilize a <strong>Amazon S3 Transfer Acceleration Speed Comparison Tool</strong> para avaliar o desempenho. Essa ferramenta ajuda a determinar se o <strong>Transfer Acceleration</strong> pode melhorar a performance de suas requisições.</p><p><em>Você pode comparar </em><a href="https://s3-accelerate-speedtest.s3-accelerate.amazonaws.com/en/accelerate-speed-comparsion.html"><em>nesse link </em></a><em>que AWS disponibiliza para verificar o ganho de velocidade na sua região utilizando o acceleration. (By santos)</em></p><p>($$$) Só será cobrado pelas transferências em que o <strong>Transfer Acceleration</strong> possa <strong>potencialmente melhorar o desempenho do upload</strong>.</p><p>A eficácia do Transfer Acceleration depende das <strong>configurações de rede</strong> e das <strong>condições locais e temporais</strong>. É mais vantajoso para <strong>clientes distantes</strong> das regiões do <strong>Amazon S3</strong>, especialmente em transferências internacionais. <em>(Porque se eles tiverem perto, não tem muito efeito né)</em> <a href="https://docs.aws.amazon.com/AmazonS3/latest/dev/transfer-acceleration.html">documentação oficial</a>.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=f08ea0c472f3" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Árvore: conceito e varredura]]></title>
            <link>https://c137santos.medium.com/%C3%A1rvore-conceito-e-varredura-56d0a050c8d9?source=rss-a4d176dcd2e6------2</link>
            <guid isPermaLink="false">https://medium.com/p/56d0a050c8d9</guid>
            <category><![CDATA[binary-tree]]></category>
            <category><![CDATA[traversals]]></category>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[trees]]></category>
            <dc:creator><![CDATA[Santos]]></dc:creator>
            <pubDate>Mon, 02 Dec 2024 15:09:26 GMT</pubDate>
            <atom:updated>2024-12-02T15:09:26.594Z</atom:updated>
            <content:encoded><![CDATA[<h4>Não estava nos meus planos aprender c 🌈 — SenhôMeAjude</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*0Z517T-ADMv4B8jb.jpg" /><figcaption>O maior cajueiro do mundo está na praia de Pirangi do Norte, em Parnamirim — RN. A árvore foi registrada no Guinness Book em 1994</figcaption></figure><p>1º Recursividade (<a href="https://c137santos.medium.com/recursividade-ae12e6b1ea5e">Medium</a>)</p><p>2º Como aprendi LinkedList (<a href="https://medium.com/@c137santos/como-aprendi-linked-list-991bb146e84b">Medium</a>)</p><p>3º Pilhas e filas (<a href="https://c137santos.medium.com/pilhas-e-filas-ebb8b70766db">Medium</a>)</p><p>4º Selection Sort (<a href="https://medium.com/@c137santos/selection-sort-9e3a71a91d08">Medium</a>)</p><p>5º Insertion Sort (<a href="https://medium.com/@c137santos/insertion-sort-692810fd5db1">Medium</a>)</p><p>6º ShellSort (<a href="https://medium.com/@c137santos/shellsort-59beba2768c6">Medium</a>)</p><p>7º QuickSort (Fazendo…)</p><p>8º MergeSort (Build…)</p><p>10º Árvores: conceito e varredura (Actual)</p><h3>Sumário!</h3><ol><li>“As árvores somos nós…”</li><li>Como é uma árvore?</li><li>Para que serve árvore?</li><li>Para nossa alegria: anatomia da árvore</li><li>Como é uma árvore no código?</li><li>Sub-árvores</li><li>Árvore Binária: Definição e Cálculo da Altura e Largura</li><li>Percorrendo uma árvore</li><li>LeetCode — 104.Maximum depth of binary tree</li></ol><h4><strong>“As árvores somos nós…”</strong></h4><p>Após trabalharmos com ordenação, buscas, pilhas e filas, começamos a explorar uma estrutura diferente para a resolução de problemas na computação: as árvores. Enquanto pilhas e filas são estruturas lineares, com um início e um fim bem definidos, as árvores e grafos armazenam dados de forma não linear, ou seja, em uma organização hierárquica.</p><h4><strong>Como é uma árvore?</strong></h4><p>Um exemplo bem conhecido de árvore, especialmente entre os iniciantes em programação, são as estruturas de HTML, que também são baseadas em hierarquia. No HTML, temos elementos que descendem do &lt;head&gt;, como o &lt;title&gt;, e outros que descendem do &lt;body&gt;, incluindo aqueles que estão dentro de estruturas como o &lt;li&gt;. Esses elementos formam uma árvore de nós, onde cada elemento pode ter filhos, criando uma estrutura hierárquica de dados.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*WjoDxdimQviBFO9G.png" /></figure><p>Para backends, podemos pensar na base da hierarquia de classes em Java, onde toda a biblioteca de classes herdam, direta ou indiretamente, da classe raiz Object.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/452/0*2zyGAstAusuPwlAM.gif" /><figcaption><a href="https://docstore.mik.ua/orelly/java-ent/jnut/ch12_01.htm">https://docstore.mik.ua/orelly/java-ent/jnut/ch12_01.htm</a></figcaption></figure><p>Para a galera de dados, árvores servem a indexação do banco de dados! Aquela estratégia de buscar dados de forma eficiencite por meio de indexadores</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/508/0*YcQbSQ3s_ANZ-v1v.jpeg" /><figcaption><a href="https://builtin.com/data-science/b-tree-index">https://builtin.com/data-science/b-tree-index</a></figcaption></figure><p>O conceito de árvore consiste em:</p><blockquote>Um conjunto de entidades chamadas nós , quais os nós são conectados por arestas. Cada nó contém um valor ou dados e pode ou não ter um nó filho . Não devendo existir reconexões ou conexões duplas entre nós filho e pai. Ou seja, precisa ser unidirecional, ou isso vira um grafo.</blockquote><p>O primeiro nó é o nó raiz! Ou nó que tudo liga! É o nó que liga qualquer um dos valores de uma árvore a qualquer outro valor. As pontas das árvores, ou seja, os nós que não tem filhos são chamados de folhas.</p><h4>Para que serve árvore?</h4><p>A árvore tem várias utilidades, mas se destaca na organização dos dados, sendo uma estrutura excepcional para <strong>busca</strong>, <strong>inserção</strong> e <strong>remoção</strong>, devido à sua estrutura hierárquica e ligação não linear. Enquanto, para acessar e organizar pilhas e filas, é necessário percorrer todos os elementos várias vezes, a árvore já está estruturada de forma que permite uma <strong>busca eficiente</strong>, como na busca binária.</p><h4><strong>PARA NOSSA ALEGRIA: Anatomia da árvore</strong></h4><p>As árvores podem ser classificadas a partir do seu comportamento e posição:</p><ul><li>A <strong>raiz</strong> é o nó mais alto da árvore</li><li>A <strong>aresta</strong> é a ligação entre dois nós</li><li>O <strong>filho</strong> é um nó que tem um nópai</li><li>O <strong>pai</strong> é um nó que tem uma aresta apontando para um nófilho</li><li>A <strong>folha</strong> é um nó que não tem nósfilhos na árvore</li><li>A <strong>altura</strong> é o tamanho do caminho mais longo até uma folha</li><li>A <strong>profundidade</strong> é o tamanho do caminho percorrido do nó até a raiz .</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/394/1*wDjmVxoBZBT_-6NA988aJw.png" /></figure><p>Ou seja, a raíz e as folhas são nós, ao mesmo tempo que são raiz e folhas.</p><h4>Como é uma árvore no código?</h4><p>Como vimos em lista ligada, a estrutura de uma LL consistia em node com next (ponteiro) e value o valor. Para árvores, temos filhos da esquerda e os filhos da direita que são referência a próximos nós por meio de ponteiro. Mas tem acompanhado essa série sabe já sobre LL. Os nós contemvalor , filho_esquerdo e filho_direito .</p><pre>typedef struct Node {<br>    int valor;<br>    struct Node *filho_esquerdo;<br>    struct Node *filho_direito;<br>} Node;<br><br>typedef struct Tree {<br>    Node* root;<br>} Tree;<br><br>void plantree(){<br>  root = Node(1);<br>  tree = Tree(root)<br>}</pre><p>Agora temos que desenhar uma função auxiliar para criação desse nó. Pois nada em C é um morango, tudo é alocação de memória</p><pre>Node* createNode(int valor) {<br>    Node* novo_no = (Node*)malloc(sizeof(Node));<br>    novo_no-&gt;valor = valor;<br>    novo_no-&gt;filho_esquerdo = NULL;<br>    novo_no-&gt;filho_direito = NULL;<br>    return novo_no;<br>}</pre><p>Agora, uma estrutura que liga os nós, as árvores. Essa indicará onde está a raíz, Portanto, a classe e a função auxiliar de criação de árvore consistem:</p><pre>typedef struct Tree {<br>    Node* root;<br>} Tree;<br><br>Tree* createTree() {<br>    Tree* nova_arvore = (Tree*)malloc(sizeof(Tree));<br>    if (nova_arvore == NULL) {<br>        perror(&quot;Erro ao alocar memória para a árvore&quot;);<br>        exit(EXIT_FAILURE);<br>    }<br>    nova_arvore-&gt;root = NULL;<br>    return nova_arvore;<br>}</pre><p>Diante dessas estruturas auxiliares, podemos então criar a plantree que plantará nossa árvore.</p><pre>Tree planTree(){<br>  Tree* tree = createTree();<br>  Node* node = createNode(1);<br>  tree -&gt; root = tree;<br>  return tree;<br>}</pre><p>A ideia da árvore em lista ligada!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*DAoQrt1ja_JMDQUxN3sboA.png" /><figcaption>Algothims in C (3ª edit) p. 221 …</figcaption></figure><p>Entenda que, ao ter base com LL, isso significa que sua alocação na memória também não continua. Outra questão é se você desejar varrer a lista pela esquerda, o algoritmo deve ser sempre com referência ao nó esquerdo</p><pre>filho_esquerda = node -&gt; filho_esquerdo;</pre><h4><strong>Sub-árvore</strong></h4><p>Então vamos construir uma árvore de exemplo:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/466/1*vKkj1bEm5NUkFl-agGmIEQ.png" /><figcaption>Árvore</figcaption></figure><p>Dentro dessa árvore temos outra árvore, a subárvore de raiz 7 com filho_esquerda = 3; , filho_direita = 2 .</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/222/1*M4mFo6dif9mkdnuJzHZWdw.png" /><figcaption>Subarvore</figcaption></figure><p>Se você considerar apenas uma folha, uma única folha, vamos ter uma subárvore unitária</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/89/1*ju5GcHqxo4G1I0iCF33Hog.png" /><figcaption>árvore unitária</figcaption></figure><h4><strong>Árvore Binária: Definição e Cálculo da Altura e Largura</strong></h4><p>Uma <strong>árvore binária</strong> é uma estrutura de dados hierárquica em que cada nó pode ter, no máximo, dois filhos: um filho à esquerda e um filho à direita. Em alguns casos, um desses filhos pode ser <strong>vazio</strong>.</p><p>Vamos utilizar a árvore binária para determinar duas características importantes: <strong>a altura</strong> e <strong>a largura</strong>.</p><ul><li><strong>Altura da árvore</strong>: Refere-se ao número máximo de níveis da árvore, ou seja, o número de nós ao longo do caminho mais longo desde a raiz até uma folha.</li><li><strong>Largura da árvore</strong>: A largura é o número máximo de nós presentes em um único nível da árvore. Por exemplo, no primeiro nível temos apenas a raiz; no segundo nível, há 2 nós; e no terceiro nível, podemos ter até 4 nós, se a árvore estiver balanceada.</li></ul><p>Para uma <strong>árvore binária balanceada</strong>, onde cada nó tem exatamente dois filhos, a largura de cada nível segue um padrão. A largura do nível nnn será sempre 2n2^n2n. Isso ocorre porque, em uma árvore balanceada, cada nível pode ter até o dobro de nós do nível anterior.</p><p>Por exemplo:</p><ul><li>No nível 0 (a raiz), há 1 nó: 20=12⁰ = 120=1.</li><li>No nível 1, há 2 nós: 21=22¹ = 221=2.</li><li>No nível 2, há 4 nós: 22=42² = 422=4.</li></ul><p>Este padrão continua até a profundidade da árvore, desde que ela esteja balanceada.</p><pre>int c;<br>c = 2 &lt;&lt; n;</pre><p>Porém, existe um algoritmo de abordagem para descobri a largura nos níveis diferentes. Um algoritmo típico utiliza uma <strong>travessia em nível</strong> (BFS) com uma fila para contar o número de nós em cada nível e determinar o máximo.</p><p>Já em relação a altura, essa seria definida como o comprimento do caminho mais longo da raiz até uma folha.</p><h4><strong>Percorrendo uma árvore</strong></h4><p>Existem algoritmo para varrer árvore. Um deles é percurso de ordem simétrica.</p><blockquote>No percurso em ordem a árvore é percorrida de forma que os nós sejam visitados primeiro o filho esquerdo, depois o nó pai e, por fim, o filho direito</blockquote><p>Vamos definir essa função de ordem simétrica</p><pre>void varreduraSimetrica(Node* root) {<br>    if (root == NULL) {<br>        return;<br>    }<br>    // Primeiro, exibe o valor do filho da esquerda<br>    varreduraSimetrica(root-&gt;filho_esquerdo);<br>    // exibe valor do pai<br>    printf(&quot;%d &quot;, root-&gt;valor);<br>    // Por último, exibe o valor do filho da direita<br>    varreduraSimetrica(root-&gt;filho_direito);<br>}<br><br>int main() {<br>    Node* raiz = createNode(10);<br>    raiz-&gt;filho_esquerdo = createNode(5);<br>    raiz-&gt;filho_direito = createNode(15);<br><br>    // Exibindo a varredura simétrica<br>    printf(&quot;Varredura simétrica (in-order): &quot;);<br>    varreduraSimetrica(raiz);<br>    printf(&quot;\n&quot;);<br>    return 0;<br>}</pre><p>A varredura de uma árvore pode ser usada para diversos motivos, inclusive, para descobri a altura e largura da árvore.</p><h4>LeetCode — 104.Maximum depth of binary tree</h4><p>No LeetCode encontramos um problema de nível fácil, chamado <a href="https://leetcode.com/problems/maximum-depth-of-binary-tree/">104.Maximum depth of binary tree</a>.</p><p>A ideia é devolver qual altura dessa árvore como inteiro, portanto, podemos aplicar o algoritmo de varredura simétrica de forma recursiva retornando sempre o segmento mais profundo da árvore para soma final!</p><pre>int maxDepth(struct TreeNode* root) {<br>    if (root == NULL) {<br>        return 0;<br>    }<br>    int l = maxDepth(root-&gt;left); // Varre a esquerda<br>    int r = maxDepth(root-&gt;right); // Varre a direita<br>    return 1 + (l &gt; r ? l : r); // Retorna a maior profundidade + 1<br>}</pre><p>Geralmente não se conta a raiz como parte da altura da árvore, mas nesse caso desse problema, ele pediu para considerar, por isso somei + 1 no return do max.</p><p>O testes de mesa para recursividade é essencial para compreender o que está acontecendo! Tentei fazer um aqui um esquema de cores para ficar visual o vai e vem da recursão, além da indicação da linha de execução da função.</p><p>A 1ª linha é a declaração int maxDepth(struct TreeNode* root){ , até a 8ª linha é o } . Portanto:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/915/1*tpUcsVm3K7wXw_FqOCnmMg.png" /></figure><p>Análise de desempenho da solução</p><p>Em relação ao tempo, esse método simplesmente foi 100% de aproveitamento com 0ms.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/850/1*fjsNUqwsTd-CPXVzRC2jiQ.png" /></figure><p>Mesmo assim, obtemos uma análise de complexidade O(N), a medida que cresce a quantidade de número, cresce o tempo de execução</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/526/1*GVs8RbpKOTHF3BLo_bjgNQ.png" /></figure><p>Em relação ao espaço, não está nem perto dos melhores, ocupamos o penultimo lugar quanto a eficiência do espaço nessa estratégia.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/806/1*4wN-7Xg2eITmM6ImMN-k5Q.png" /></figure><p>Também em uma complexidade de espaço de O(N)</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/574/1*pRNLR6wmhTlx16dPInh4mg.png" /></figure><p>Isso ocorreu devido ao uso da recursão, que ficou guardando ali vários locais na memória com os resultados que ainda retornaria!</p><p>A melhor estratégia nesse caso para redução quanto ocupação seria verificar, a cada iteração, se estamos lidando uma segmentação maior do que as determinadas. Porém, por enquanto, isso serve para compreender a ideia de árvore e varredura.</p><p>Portanto, por enquanto, é isso de árvore! Não tem como ser mais clara que isso! Até a próxima.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=56d0a050c8d9" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[QuickSort]]></title>
            <link>https://c137santos.medium.com/quicksort-3221d39e5ae2?source=rss-a4d176dcd2e6------2</link>
            <guid isPermaLink="false">https://medium.com/p/3221d39e5ae2</guid>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[c]]></category>
            <category><![CDATA[algoritmos]]></category>
            <category><![CDATA[search]]></category>
            <category><![CDATA[quicksort]]></category>
            <dc:creator><![CDATA[Santos]]></dc:creator>
            <pubDate>Wed, 27 Nov 2024 16:32:55 GMT</pubDate>
            <atom:updated>2024-11-27T16:32:55.911Z</atom:updated>
            <content:encoded><![CDATA[<h4>Não estava nos meus planos aprender c 🌈 — SenhôMeAjude</h4><p>O quicksort é uma batalha constante para conquista .</p><p>1º Recursividade (<a href="https://c137santos.medium.com/recursividade-ae12e6b1ea5e">Medium</a>)</p><p>2º Como aprendi LinkedList (<a href="https://medium.com/@c137santos/como-aprendi-linked-list-991bb146e84b">Medium</a>)</p><p>3º Pilhas e filas (<a href="https://c137santos.medium.com/pilhas-e-filas-ebb8b70766db">Medium</a>)</p><p>4º Selection Sort (<a href="https://medium.com/@c137santos/selection-sort-9e3a71a91d08">Medium</a>)</p><p>5º Insertion Sort (<a href="https://medium.com/@c137santos/insertion-sort-692810fd5db1">Medium</a>)</p><p>6º ShellSort (<a href="https://medium.com/@c137santos/shellsort-59beba2768c6">Medium</a>)</p><p>7º QuickSort (Actual)</p><h3>Sumário!</h3><ol><li>O que significa dividir para conquistar?</li><li>Regras específicas do QuickSort</li><li>Sublistas com apenas um vetor</li><li>LeetCode Sort the People</li><li>Análise técnica de desempenho</li></ol><h4>O que significa dividir para conquistar?</h4><p>O quicksort é ideal para grande datasets, pois ordena com base na estratégia de dividir para conquistar!</p><p>Consiste a estratégia do dividir para conquistar, a divisão do problema em parte menores, com objetivo de propor uma solução simples a menor fração do problema, aplicada <strong>recursivamente</strong>, até a obtenção da resposta como um todo.</p><p>Um exemplo seria calcular a quantidade total de brigadeiros em 10 bandejas, sabendo que todas as bandejas têm a mesma quantidade de brigadeiros. Todos os brigadeiros ocupam o mesmo espaço em uma bandeja. Sabemos que <strong>1/4 de uma bandeja contém 10 brigadeiros</strong>.</p><p>Em vez de calcular diretamente o total em 10 bandejas, começamos analisando <strong>1/4 da bandeja</strong>. Se <strong>1/4 da bandeja = 10 brigadeiros</strong>, então a bandeja inteira contém <strong>10 × 4 = 40 brigadeiros</strong>. Se cada bandeja tem <strong>40 brigadeiros</strong>, e temos <strong>10 bandejas</strong>, o total será <strong>40 × 10 = 400 brigadeiros</strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*hKL6xm5ZQ26f0miOyxaW7w.jpeg" /><figcaption>ChatGPT me ajudando com docinhos</figcaption></figure><p>Assim, dividindo o problema em partes menores (calculando primeiro por fração da bandeja), podemos resolver o problema de forma mais eficiente.</p><p>É um exemplo inocente, mas daqui para partimos para discursão sobre Algoritmo de Euclides é dois palitos! A <strong>estratégia de divisão reduz a complexidade e facilita a solução de problemas maiores</strong>.</p><h4>Regras específicas do QuickSort</h4><ol><li><strong>Array vazio ou de um elemento já está ordenado</strong></li></ol><p>O caso-base e o mais simples é que um array vazio ou um array com um elemento já está ordenado.</p><p><strong>2. A conquista ocorre com um pivô</strong></p><p>Nesse algoritmo há um pivô. Pivô será o ponto que em que elementos menores que ele ficam a esquerda e maiores que ele para direita (em caso crescente).</p><p>A depender da escolha do seu pivô , o algoritmo pode ser melhor ou pior no desempenho. Quando ele faz isso, o pivô estará no seu lugar correto. Ao final teremos de casa iteração, teremos:</p><p>• Um subarray contendo todos os números menores do que o pivô<br>• O pivô<br>• Um subarray contendo todos os números maiores do que o pivô</p><p>Essa mesma solução deve ser então aplicada aos sub-arrays que formaram antes do pivô e depois do pivô.</p><p>Retorne então a junção de subarray esquerdo, o pivô e subarray direito.</p><h4>LeetCode Sort the People</h4><p>Na biblioteca-padrão da linguagem C tem uma função chamada qsort, que é uma implementação do quicksort.</p><p>A solução mais próxima do <em>Quick Sort</em> aplicada ao <strong>Sort the People</strong> precisou ser fracionada em algumas funções diferentes que assumem as diferentes responsabilidades:</p><pre>#include &lt;stdlib.h&gt;<br><br>// Função auxiliar para trocar dois elementos no array<br>void swap(char** names, int* heights, int i, int j) {<br>    char* tempName = names[i];<br>    int tempHeight = heights[i];<br>    names[i] = names[j];<br>    heights[i] = heights[j];<br>    names[j] = tempName;<br>    heights[j] = tempHeight;<br>}<br><br>// Função de partição para o Quicksort<br>int partition(char** names, int* heights, int low, int high) {<br>    int pivot = heights[high]; // Escolhe o último elemento como pivô<br>    int i = low - 1;           // Índice do menor elemento<br>    for (int j = low; j &lt; high; j++) {<br>        if (heights[j] &gt; pivot) { // Ordena em ordem decrescente<br>            i++;<br>            swap(names, heights, i, j);<br>        }<br>    }<br>    swap(names, heights, i + 1, high);<br>    return i + 1;<br>}<br>// Função recursiva do Quicksort<br>void quickSort(char** names, int* heights, int low, int high) {<br>    if (low &lt; high) {<br>        int pi = partition(names, heights, low, high); // Particiona o array<br>        quickSort(names, heights, low, pi - 1);        // Ordena a sublista à esquerda<br>        quickSort(names, heights, pi + 1, high);      // Ordena a sublista à direita<br>    }<br>}<br>// Função principal para ordenar as pessoas<br>char** sortPeople(char** names, int namesSize, int* heights, int heightsSize, int* returnSize) {<br>    quickSort(names, heights, 0, heightsSize - 1);<br>    *returnSize = namesSize;<br>    return names;<br>}</pre><p>A função inicia com a chamada do quickSort , passando os elementos de nome, altura, o índice mais baixo e o índice mais alto ( heightsSize ) para que haja a chamada recursiva.</p><p>No quicksort , vamos ter como critério de parada que o índice mais baixo seja menor que o índice mais baixo. Isso evita que eles cruzem e continuem ordenando (kkk). A partir disso a função partition recebe os parametros:</p><ul><li>escolhe o pivô, nesse caso, o último elemento da lista</li><li>Percorre a lista comparando quem é maior que ele, em caso positivo, aciona o swap para realizar a troca dos elementos nos índices.</li><li>Devolveo índice final do pivô no array reorganizado</li></ul><p>Com o índice final do pivô no array reorganizado, é passado, para a próxima iteração recursiva, a sublista a direita e a sublista a esquerda.</p><h4>Análise técnica de desempenho</h4><p>Em relação ao tempo, a complexidade tende a ser bem rápida com o BigO de O(n log n), ideal para buscar em grandes datasets. O pior cenário seria se o pivô for o menor ou maior dos elementos, ai teremos um tempo de complexidade O(N²). Porque haverá sempre uma lista com nenhum elementos e outra com todos os elementos, tornando uma das chamadas muito longas.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/733/1*0E1VhPzqKlpNpQXWEImePw.png" /><figcaption>BAHRGAVA. Aditya. Entendendo Algoritmos — Um Guia ilustrado para programadores e outros curiosos. p. 113</figcaption></figure><blockquote>O algoritmo quicksort é um caso complicado. Na pior situação, o quicksort tem tempo de execução O(n2). Ele é tão lento quanto a ordenação por seleção! Porém este é o pior caso possível. No caso médio, o quicksort tem tempo de execução O(n log n). O quicksort tem uma constante menor do que o merge sort. Assim, como ambos têm tempo de execução O(n log n), o quicksort acaba sendo mais rápido. Além disso, o quicksort é mais rápido, na prática, pois ele funciona mais vezes no caso médio do que nopior caso. “BAHRGAVA. Aditya. Entendendo Algoritmos — Um Guia ilustrado para programadores e outros curiosos. p. 110”</blockquote><p>No caso dessa solução ficamos com a tendência do O(n log n):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/441/1*W66wlRHaB3sL4JnRqLSItA.png" /></figure><p>Então sim, o pior caso para o quicksort é quando a lista já se encontra ordenada e ele pega o menor ou maior número, pois ele não realiza a checagem se existe ordenação antes de iniciar.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/608/1*IH1SDMZOl1fLTU1r3E4OgA.png" /></figure><p>Em relação ao espaço, quicksort obtém a complexidade de O(log n).</p><p>Em relação ao espaço, temos uma ocupação maior de espaço, que é tendência das soluções recursivas.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/579/1*GCBosbwziULPxg0mJd-5_g.png" /></figure><p>Mas como visto na análise, ele também contém um O(logN).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/459/1*dwPANkqc-Y8AD8VrdXL37Q.png" /></figure><p>Bem, não tem como ser mais Clara que sim! Deixo aqui bibliografias essenciais para a compreensão desse tema.</p><p><strong>Bibliografia</strong></p><ul><li><a href="https://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/quick.html">O algoritmo Quicksort de ordenação de vetores</a></li><li><a href="https://medium.com/@nathaldawson/unraveling-quicksort-the-fast-and-versatile-sorting-algorithm-2c1214755ce9">Unraveling QuickSort: The Fast and Versatile Sorting Algorithm</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=3221d39e5ae2" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[ShellSort]]></title>
            <link>https://c137santos.medium.com/shellsort-59beba2768c6?source=rss-a4d176dcd2e6------2</link>
            <guid isPermaLink="false">https://medium.com/p/59beba2768c6</guid>
            <category><![CDATA[shell-sort]]></category>
            <category><![CDATA[c]]></category>
            <category><![CDATA[algoritmos]]></category>
            <category><![CDATA[algorithms]]></category>
            <dc:creator><![CDATA[Santos]]></dc:creator>
            <pubDate>Mon, 18 Nov 2024 22:16:11 GMT</pubDate>
            <atom:updated>2024-11-18T22:16:11.590Z</atom:updated>
            <content:encoded><![CDATA[<h4>Não estava meus planos aprender C 🌈 — SenhôMeAJude</h4><p>O ShellSort é um insertionSort com um coelho pulando no meio.</p><p>1º Recursividade (<a href="https://c137santos.medium.com/recursividade-ae12e6b1ea5e">Medium</a>)</p><p>2º Como aprendi LinkedList (<a href="https://medium.com/@c137santos/como-aprendi-linked-list-991bb146e84b">Medium</a>)</p><p>3º Pilhas e filas (<a href="https://c137santos.medium.com/pilhas-e-filas-ebb8b70766db">Medium</a>)</p><p>4º Selection Sort (<a href="https://medium.com/@c137santos/selection-sort-9e3a71a91d08">Medium</a>)</p><p>5º Insertion Sort (<a href="https://medium.com/@c137santos/insertion-sort-692810fd5db1">Medium</a>)</p><p>6º ShellSort (actual)</p><h3>Sumário!</h3><ol><li>Por que os coelhos nos ajudam com shellSort?</li><li>Regras específicas do shellSort</li><li>Sublistas com apenas um vetor</li><li>LeetCode Sort the People</li><li>Análise técnica de desempenho</li></ol><p><strong>Por que os coelhos nos ajudam com shellSort?</strong></p><p>O ShellSort é um algoritmo de ordenação facilmente compreendido se já entender sobre InsertionSort. Porque a ideia é realizar a ordenação de uma lista por meio do insertionSort em dois elementos, o 1º e o último das sublistas fracionadas em intervalos determinados pelo gap. Ou um pulo de um coelho! Wtf…</p><p>Sabe que aqui a gente trabalha com analogias para você nunca mais esquecer. Imagina um coelho que pula sob uma lista sempre na mesma distancia. Mas a medida que ele pula, ele cansa! Então pula mais curtinho da próxima vez. Não conseguiu imaginar? Meu deus que mente pouco criativa, toma aqui um desenho para te ajuda!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*-QTOOGLcqNMHACvH9jqjIA.jpeg" /></figure><p>Então nessa lista aqui, nosso pernalonga pula no máximo de números em distâncias iguais. Como são 9 elementos, vamos fazer ele pular certinho de 3 em 3 elementos.</p><p>Então, pula do índice 0 ao índice 2 e verifica: “Esse números estão na ordem correta? Esse número 2 localizado no índice 0 é menor que esse número 1 que está no índice 2?”</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Arhd7XKXi5CyTmiOa9EkSA.jpeg" /></figure><p>Caso não seja: Pernalonga trata de trocar os números de lugar. Ficando o número 1 no índice 0 e númeo 2 no índice 2.</p><p>Agora ele saltará do índice 2 para o índice 5 (lembra que índice conta 0). E vai fazer a mesma análise relativa aos números que estão ali. Se está na ordem não modifica, se não está na ordem, troca. Até chegar ao último elemento!</p><p>Agora nosso coelho está mais cansado, e vai pular a metade do que pulava. Se ele pulava 3, agora pula de 2 em 2! (Pq coelho não pula 1/2! Então vamos arredonda para cima!) Repetindo o processo.</p><p>O último salto é sempre será de 1. Onde estaremos aplicando o insertionSort na lista completa.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/734/0*YAuZLxxFk_8tn7Sk.png" /><figcaption>Organização das sublistas utilizando o pulo de distância 4!</figcaption></figure><h4>Regras específicas do shellSort</h4><p><strong>Como o shellSort pode ser um algoritmo melhor que o InsertionSort, se ele é um sistema baseado no InsertionSort com etapas a mais?</strong></p><p>O Insertion Sort possui um problema inerente, ele tem cópias demais! Pois precisa ficar movendo TODOS os elementos para frente para encaixar um outro elemento na ordem. Isso realiza diversas cópias do array. (Para mais detalhes sobre seu funcionamento InsertionSort (<a href="https://medium.com/@c137santos/insertion-sort-692810fd5db1">Medium</a>)</p><p>Por isso que são os saltos que determinam o big(O) do algoritmo. Ele tende a O(n) e O(n²). Porque ao reordenar alguns elementos de forma a trocar suas posições, ele não empurra nínguem, nem promove mais cópia, apenas troca índice x por índice y se necessário, por consequência ocorre uma pré-ordenação do vetor!</p><p>Lafore explica, compreendendo h como os gaps determinados que:</p><blockquote>Quando o valor de h é elevado, há poucas trocas por passagem, e os elementos podem ser movidos a longas distâncias, como já foi ilustrado, o que é extremamente eficiente. À medida que h diminui, o número de trocas aumenta, mas os elementos já estão mais próximos de suas posições finais, facilitando a ordenação por inserção. Essa combinação de fatores é o que torna a ordenação Shell tão eficaz.(LAFORE, 2004, p. 130).</blockquote><p><strong>A determinação desses saltos pode ocorrer de diferentes formas.</strong></p><p>A original foi elaborada por Donald Shell, onde o calculo do gap ocorre pela múltiplicação do divisor por 2 a medida de n/2, n/4, n/8… Porém, existem outras formas de determinar um gap funcional.</p><ul><li><strong>Hibbard</strong>: 2^k−1</li><li><strong>Knuth</strong>: 3^k — 1 / 2​</li><li><strong>Sedgewick</strong>: 1, 5 , 19 , 41 , 109 , … (alternando potências de 4 e 9)</li><li><strong>Ciura (Empírica)</strong>: 1,4,10,23,57,132,301,701,1750</li></ul><p>A pré-organização por saltos diminui a incidência do pior caso do inserSort, que seria o caso de uma lista inversamento ordenada, onde o 1º elemento teria que empurar todos para frente.</p><p>O processo de determinar quais serão os gaps aplicados quando o pulo se torna maior que o vetor.</p><p>Se eu for, por exemplo, determinando o pulo por <strong>Knuth, </strong>para um vetor com 1000 elementos, o 7º número da sequência, 1093, é grande demais. Portanto, a ordenação começa pelo 6º maior número, em 364. Então, a cada vez no laço externo da rotina de ordenação, reduzimos o intervalo usando o inverso da fórmula dada anteriormente: <strong>h = (h-1) / 3</strong>.(LAFORE, 2004, p. 131).</p><p>Ao realizar essa pre-organização, ao chegar no passo de intervalo 1, então utilizaremos o insertSort na lista completa que estará praticamente ordenada.</p><p><strong>LeetCode Sort the People</strong></p><p>O problema que vamos levar nessa série como comparativo é o <a href="https://leetcode.com/problems/sort-the-people/">2418. Sort the People</a> do leetcode! Pretendo usar ele como exemplo para mostra a eficiencia de cada algoritmo de ordenação.</p><p>Já mostramos ele com Selection Sort (<a href="https://medium.com/@c137santos/selection-sort-9e3a71a91d08">Medium</a>) e no Insertion Sort (<a href="https://medium.com/@c137santos/insertion-sort-692810fd5db1">Medium</a>).</p><p>A aplicação de um algoritmo de ordenação de pessoas, nesse caso, nem é tão complicada. O problema consiste em, dado um array de nomes e um array correspondente de alturas, retornar os nomes das pessoas ordenados em ordem decrescente de altura. Por exemplo, com names = [&quot;Mary&quot;, &quot;John&quot;, &quot;Emma&quot;] e heights = [180, 165, 170], a saída correta seria [&quot;Mary&quot;, &quot;Emma&quot;, &quot;John&quot;].</p><p>A solução mais próxima do <em>Insertion Sort</em> aplicada ao <strong>Sort the People</strong> consiste em:</p><pre>/**<br> * Note: The returned array must be malloced, assume caller calls free().<br> */<br>char** sortPeople(char** names, int namesSize, int* heights, int heightsSize, int* returnSize) {<br>    int h = 1;<br>    // Define o valor inicial de h na sequência (Knuth): h &lt;= n/3<br>    while (h &lt;= heightsSize / 3) {<br>        h = h * 3 + 1;<br>    }<br><br>    // Loop principal do Shell Sort<br>    while (h &gt; 0) {<br>        for (int endInterv = h; endInterv &lt; heightsSize; endInterv++) {<br>            int tempHeight = heights[endInterv];<br>            char* tempName = names[endInterv];<br>            int begInterv = endInterv;<br><br>            // Inserção por deslocamento com base no gap h<br>            while (begInterv &gt;= h &amp;&amp; heights[begInterv - h] &lt;= tempHeight) {<br>                heights[begInterv] = heights[begInterv - h];<br>                names[begInterv] = names[begInterv - h];<br>                begInterv -= h;<br>            }<br><br>            // Insere o elemento na posição correta<br>            heights[begInterv] = tempHeight;<br>            names[begInterv] = tempName;<br>        }<br><br>        // Reduz o gap para o próximo valor<br>        h = (h - 1) / 3;<br>    }<br>    // Retorna os dados ordenados<br>    *returnSize = namesSize;<br>    return names;<br>}</pre><p>Como estamos programando em C na plataforma LeetCode, somos obrigados a definir o tamanho do array de retorno da função. O parâmetro returnSize é essencial para que o LeetCode saiba o tamanho exato da lista retornada e possa percorrê-la corretamente para avaliação. Nesse caso, returnSize será igual a namesSize, já que todos os nomes devem ser retornados e a quantidade de nomes não muda.</p><p>Em termos de tempo de execução, essa solução está entre as melhores, simplesmente 0ms! Uma solução que bateu 100% de aproveitamento. Enquanto SelectionSort demorou 45ms, e o InsertionSort 15ms.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/633/1*ChnHiUBY44Ol6nKh4YlRWg.png" /></figure><p>Em relação a memória, tivemos um dos piores de ocupação da memória, porém, a diferença desse algoritmo para outros foi apenas de 0.32MB! Então não é tão ruim em relação aos outros, mas é bem ruim ainda.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/622/1*rNfJJisMvv6FDmu7jnpMZw.png" /></figure><h3>Bibliografia</h3><p>LAFORE, Robert. <strong>Estruturas de Dados e Algoritmos em Java</strong>. São Paulo: Pearson Makron Books, 2004.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=59beba2768c6" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Insertion sort]]></title>
            <link>https://c137santos.medium.com/insertion-sort-692810fd5db1?source=rss-a4d176dcd2e6------2</link>
            <guid isPermaLink="false">https://medium.com/p/692810fd5db1</guid>
            <category><![CDATA[c]]></category>
            <category><![CDATA[insertion-sort]]></category>
            <category><![CDATA[ordenação]]></category>
            <category><![CDATA[sorting-algorithms]]></category>
            <category><![CDATA[algorithms]]></category>
            <dc:creator><![CDATA[Santos]]></dc:creator>
            <pubDate>Wed, 30 Oct 2024 13:00:25 GMT</pubDate>
            <atom:updated>2024-11-04T11:41:55.365Z</atom:updated>
            <content:encoded><![CDATA[<h4>Não estava meus planos aprender C 🌈 — SenhôMeAJude</h4><blockquote>“TA UM EMPURRA EMPURRA AQUI! MAS TA GOSTOSO, UM EMPURRA EMPUURA AQUIII!! MELHOR AINDA É PULAR NO MEIO DO POVO“ — <a href="https://www.tiktok.com/@bahiafm88/video/7193909606274419973">Empurra-Empurra</a> Sangalo, Ivete, 2005.</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/774/0*gMm2KeC5ZQuLfeSW.jpg" /><figcaption>Praia da Barra — Carnaval Bahia — Veveta</figcaption></figure><p>1º Recursividade (<a href="https://c137santos.medium.com/recursividade-ae12e6b1ea5e">Medium</a>)</p><p>2º Como aprendi LinkedList (<a href="https://medium.com/@c137santos/como-aprendi-linked-list-991bb146e84b">Medium</a>)</p><p>3º Pilhas e filas (<a href="https://c137santos.medium.com/pilhas-e-filas-ebb8b70766db">Medium</a>)</p><p>4º Selection Sort (<a href="https://medium.com/@c137santos/selection-sort-9e3a71a91d08">Medium</a>)</p><p>5º InsertionSort (actua)</p><h4>Sumário!</h4><ol><li>O que o carnaval de Bahia e Ivete Sangalo pode me ensinar sobre algoritmo de ordenação?</li><li>Regras específicas do InsertionSort</li><li>Sublistas com apenas um vetor</li><li>Detalhes do algoritmo</li><li>LeetCode Sort the People</li><li>Análise técnica de desempenho</li></ol><h4>O que o carnaval de Bahia e Ivete Sangalo pode me ensinar sobre algoritmo de ordenação?</h4><p>Ela pode te ensinar sobre InsertionSort! Insertion Sort é algoritmo eficiente para ordenar um número pequeno de elementos.</p><p>A base desse algoritmo é ir empurrando quem é maior ou quem é menor para trás de um pivô, até achar sua posição ideal!</p><p>Inicialmente, vamos sempre lembrar daquela <strong>premissa geral</strong> para ordenação. Todo array de 0 ou 1 elemento está ordenado.</p><h4><strong>Regras específicas:</strong></h4><ol><li>Temos um pivô, ele é o elemento sob análise que está na vez de ser ordenado</li><li>No insertion sort, todos elementos por onde passar o pivô estarão ordenado, enquanto a outra parte ainda será ordenado</li><li>A operação do insertion sort precisa ser feito em um vetor apenas.</li><li>A análise ocorre elemento por elemento, contra os anteriores que estão ordenados pós pivô.</li></ol><p><strong>Complexidade</strong>: No melhor dos caso, o menor elemento está no início e não será comparado a ninguem. Pior do caso, a lista está inversamente ordenado, então todo elemento será comparado com todos elementos. Portanto temos o O(N²).</p><p>Não entendeu? Imagine desembaraçar um cabelo. O pivô é a escova de cabelo, todo cabelo já desembaraçado já passou pela escova, o que ainda precisa ser desembaraçado é o que ainda vai ser escovado.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/514/1*WGUvjUry6Yew3_OGjwzSnw.png" /><figcaption>A lista no caso de O(N²)</figcaption></figure><p>Muitos lugares vão exemplificar essa ordenação como o ato de ordena cartas de um baralho que estão sua mão.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/636/1*1ayoBm5SUhCh96ZDuejk1Q.png" /></figure><blockquote>“We start with insertion sort, which is an efﬁcient algorithm for sorting a small number of elements. Insertion sort works the way many people sort a hand of playing cards. We start with an empty left hand and the cards face down on the table. We then remove one card at a time from the table and insert it into the correct position in the left hand. To ﬁnd the correct position for a card, we compare it with each of the cards already in the hand, from right to left, as illustrated in Figure 2.1. At all times, the cards held in the left hand are sorted, and these cards were originally the top cards of the pile on the table.” Introduction to algorithms / Thomas H. Cormen . . . [et al.]. — 3rd ed. página 17</blockquote><p>Por isso se chama InsertionSort, pois você insere os elementos já na posição correta.</p><h4><strong>SubListas apenas com um vetor</strong></h4><p>Vamos trabalhar com sub listas! Mas como disse, você só deve usar um vetor. Então, as sub listas serão compreendidas a partir do fatiamento da lista entre seu início até o elemento que está sendo analisado para inserção (o pivô).</p><p>Portanto, em uma lista de 5 elementos como Lista=[5,4,3,2,1], nossa primeira sublista será compostas de subl=[5,2].</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/561/1*wxz_O598mbXzRN2riDT3Og.png" /></figure><p>Porque não começar com uma subl de 5? Por conta que conversamos, toda lista de 0 ou 1 elemento, já está automaticamente ordenada!</p><p>A partir daqui vamos eleger dois caras. O elemento sob análise (que ando chamando de pivô), e a chave de parada (key).</p><h4>Detalhes do algoritmo</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*-R2ljpjabLIeDHjf" /><figcaption>Pivô tentando encontrar seu lugar enquanto a Key empurra a lista.</figcaption></figure><ol><li>O limite do algoritmo Insertion Sort é o tamanho da lista, ou até encontrar next == null (no caso de listas encadeadas - LL - (<a href="https://medium.com/@c137santos/selection-sort-9e3a71a91d08">Medium</a>));</li><li>Existem dois loopings. Um for para percorrer pivôs. E um whiledentro do for, para comparar askey aos pivôpara buscando elemento maior que ele.</li><li>O primeiro elemento da lista já é considerado ordenado, então o primeiro elemento a ser analisado como pivô está na segunda posição;</li><li>Portanto, o pivô está na posição i, onde (i = 1; i++, i &lt; n);</li><li>O pivô libera sua posição atual para ser ocupada por elementos maiores que ele, à medida que esses elementos são “empurrados” para a frente até que o pivô encontre seu novo lugar na lista;</li><li>A key inicia como o elemento anterior ao pivô (posição i-1);</li><li>A key é um índice móvel que percorre os elementos antes do pivô, indo da posição i-1 até o início da lista dentro do while;</li><li>A condição de parada ocorre quando a key atinge o final da lista (índice 0 ou um índice negativo) ou encontra um elemento maior que o pivô;</li><li>Se a key não estiver em índice 0 ou negativo, ou se o elemento for menor que o pivô, ele será movido um índice para a frente;</li><li>A key é decrementada a cada iteração em que não atinge a parada;</li><li>Caso a condição de parada seja key == 0, o pivô será colocado na posição inicial (índice 1), após n movimentações na lista, encerrando a iteração;</li><li>Se a condição de parada for por encontrar um elemento maior que o pivô, o pivô troca de posição com a key, e a iteração é encerrada;</li></ol><h4>LeetCode Sort the People</h4><p>O problema que vamos levar nessa série como comparativo é o <a href="https://leetcode.com/problems/sort-the-people/">2418. Sort the People</a> do leetcode! Pretendo usar ele como exemplo para mostra a eficiencia de cada algoritmo de ordenação.</p><p>Já mostramos ele com Selection Sort (<a href="https://medium.com/@c137santos/selection-sort-9e3a71a91d08">Medium</a>)</p><p>A aplicação de um algoritmo de ordenação de pessoas, nesse caso, nem é tão complicada. O problema consiste em, dado um array de nomes e um array correspondente de alturas, retornar os nomes das pessoas ordenados em ordem decrescente de altura. Por exemplo, com names = [&quot;Mary&quot;, &quot;John&quot;, &quot;Emma&quot;] e heights = [180, 165, 170], a saída correta seria [&quot;Mary&quot;, &quot;Emma&quot;, &quot;John&quot;].</p><p>A solução mais próxima do <em>Selection Sort</em> aplicada ao <strong>Sort the People</strong> consiste em:</p><pre>/**<br> * Note: The returned array must be malloced, assume caller calls free().<br> */<br>char** sortPeople(char** names, int namesSize, int* heights, int heightsSize, int* returnSize) {<br>    for (int i = 1; i &lt; heightsSize; i++) {<br>        int pivo = heights[i]; <br>// Guardei o pivô relativo a array de altura p/ deixar seu espaço livre<br>        char* namePivo = names[i]; <br>// Guardei o pivô relativo ao nome p/ deixar seu espaço livre<br>        int key = i - 1; <br>// declarei o ínicio dos antecessores - a key!<br><br>        while (key &gt;= 0 &amp;&amp; heights[key] &lt; pivo) {  <br>// Empurra empurra de elementos maiores que o elemento pivô para a direita<br>            heights[key + 1] = heights[key];<br>// empurrando altura maior que a do pivô pra frente do pivô!<br>            names[key + 1] = names[key]; <br>// Empurra empurra do nome correspondente ao pivô pra frente do pivô!<br>            key = key - 1; <br>// indo mais um índice para trás p/ continuar buscando elemento menor que o pivô<br>        }<br>// Critério de parada atendido? (key &gt;= 0 &amp;&amp; heights[key] &lt; pivo)<br>// Insere o pivô de altura e nome na posição correta<br>        heights[key + 1] = pivo;<br>        names[key + 1] = namePivo;<br>    }<br><br>    *returnSize = namesSize;<br>    return names;<br>}</pre><p>Como estamos programando em C na plataforma LeetCode, somos obrigados a definir o tamanho do array de retorno da função. O parâmetro returnSize é essencial para que o LeetCode saiba o tamanho exato da lista retornada e possa percorrê-la corretamente para avaliação. Nesse caso, returnSize será igual a namesSize, já que todos os nomes devem ser retornados e a quantidade de nomes não muda.</p><p>Em termos de tempo de execução, essa solução está entre as piores quando comparada a outras propostas submetidas na plataforma.</p><h4>Análise técnica de desempenho</h4><p>Em termos de Big(O) para tempo, temos o previsto pela literatura, O(N²).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/640/1*4IPY-Vdj1yveQIouNE59jg.png" /><figcaption>Análise Time Complexity LeetCode ao algoritmo demonstrado</figcaption></figure><p>Em termos de tempo, foi um ganho considerável em relação ao SelectionSOrt, que havia batido 47ms, agora estou com 15ms!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/818/1*sFhhoy36jlKj9l70XUtUXQ.png" /><figcaption>Análise do LeetCode ao algoritmo demonstrado</figcaption></figure><p>Em relação a memória, é um algoritmo que perde para o SelectionSort por alguns poucos mbs! Tem uma complexidade constante.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/591/1*EwMJvBvKgsxpNl8IZ1ZDHQ.png" /><figcaption>BigO constante em termos de espaço.</figcaption></figure><p>Nosso SelectionSort havia dado 13.26MB, e estava acima de 94.44% das soluções, enquanto esse está apenas melhor que os 76.17% das soluções.os</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/776/1*ugkZFALxs5qOh7-wRcD6CQ.png" /></figure><p>Bom galera! Esse é o InsertionSort. Eu espero te ajudado na compreensão, e não tem como ser mais Clara que isso!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=692810fd5db1" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Selection Sort]]></title>
            <link>https://c137santos.medium.com/selection-sort-9e3a71a91d08?source=rss-a4d176dcd2e6------2</link>
            <guid isPermaLink="false">https://medium.com/p/9e3a71a91d08</guid>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[selection-sort]]></category>
            <category><![CDATA[sorting-algorithms]]></category>
            <category><![CDATA[c]]></category>
            <dc:creator><![CDATA[Santos]]></dc:creator>
            <pubDate>Fri, 18 Oct 2024 23:03:21 GMT</pubDate>
            <atom:updated>2024-10-18T23:03:21.467Z</atom:updated>
            <content:encoded><![CDATA[<h4><em>Não estava meus planos aprender C 🌈 — SenhôMeAJude</em></h4><blockquote>O campeonato mineiro de 2006 atrasa devido ao sistema baseado no selection sort.</blockquote><p>1º Recursividade (<a href="https://c137santos.medium.com/recursividade-ae12e6b1ea5e">Medium</a>)</p><p>2º Como aprendi LinkedList (<a href="https://medium.com/@c137santos/como-aprendi-linked-list-991bb146e84b">Medium</a>)</p><p>3º Pilhas e filas (<a href="https://c137santos.medium.com/pilhas-e-filas-ebb8b70766db">Medium</a>)</p><p>4º Selection Sort (actual)</p><h4>Sumário!</h4><ol><li>O que o campeonato mineiro tem a ver com SelectionSort?</li><li>Passos gerais do SelectionSort</li><li>Implementação em C</li><li>Detalhes do algoritmo</li><li>O passo C — Como realizar a troca de</li><li>LeetCode Sort the People</li></ol><h4>O que o campeonato mineiro tem a ver com SelectionSort?</h4><blockquote><a href="https://web.archive.org/web/20141220221439/http://esportes.terra.com.br/noticias/0,,OI799885-EI1846,00-FMF+enfim+divulga+a+tabela+do+Mineiro+de.html">FMF, enfim, divulga a tabela do Mineiro de 2006.</a></blockquote><blockquote>Com quase um mês de atraso, a Federação Mineira de Futebol (FMF) divulgou, na quinta-feira à noite, a tabela do Campeonato Estadual de 2006. O torneio, que a princípio estava marcado para começar dia 22 de janeiro, terá um jogo da primeira rodada no dia 18, o confronto entre Villa Nova e Ituiutaba.</blockquote><p>Essa notícia é legal, contam que o atraso foi devido a formação da tabela de confronto do campeonato, pois não existia um conhecedor da técnica de distribuição todos-contra-todos. Essa técnica consiste em:</p><blockquote>Em competições esportivas, o <strong>sistema de todos contra todos</strong> designa todo tipo de torneio em que cada um dos competidores enfrenta todos os demais. Geralmente, é usado em conjunto com o sistema de pontos corridos na maioria das ligas nacionais de futebol. Em inglês, esse sistema é conhecido como <strong><em>round-robin</em></strong>. <a href="https://pt.wikipedia.org/wiki/Competi%C3%A7%C3%B5es_de_todos_contra_todos">Wiki</a> — video explicativo do prof</blockquote><p>Não atoa se chama <strong>Campeonato</strong> Estadual. Na educação física, o que define um campeonato é exatamente o tática de todos jogarem contra todos! Para mais detalhes, veja esse vídeo de um professor de educação física <a href="https://www.youtube.com/watch?app=desktop&amp;v=DdVw5ulEbrU">ensinando a elaborar essa tabela na mão</a>!</p><p>Ou seja, o time A joga contra todos os outros. O time B joga contra todos os outros menos o A. O time C contra todos exceto A e B e assim por diante.</p><p><em>Mas o que isso tem a ver com selection sort??</em></p><p>Bem, conheça agora o PIOR algoritmo de ordenação do mundo. Tão horrível que seu pior caso é O(n²)! Porém, é justo ressaltar que ele é um algoritmo muito simples de trabalho, e serve a pequena quantidade de elementos.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*-bm2l3sfzL2bN0F-J8mAtg.png" /><figcaption>ChatGPT</figcaption></figure><h4>Passos gerais do SelectionSort</h4><p>a) Pegue o 1º elemento;</p><p>b) Compare ao longo da lista, procurando se existe algum que seja menor que ele (para casos que deseje ordenação crescente, se não procure o maior deles);</p><p>c) Encontrando um menor, troque as posições desses via índice;</p><p>d) Passe para o próximo elemento da lista, sabendo que o anterior já está ordenado.</p><p>MAS TEM QUE SER O MENOR MESMO! Ou seja, vai ter que passar pela lista inteira toda vez para verificar quem de fato é o menor. Tal qual a competição do campeonato mineiro, todos contra todos.</p><p>Esse algoritmo é O(n)², pois a medida que o array cresce, a quantidade de operação necessária para ordenação cresce.</p><p>Se tiver a “sorte” do maior está na primeira posição, é possível que esse número seja trocado em todas as comparações, assim, <strong>número máximo de trocas</strong> envolvendo um único elemento é <strong>n -1</strong>, onde <strong>n</strong> é o número de elementos no array.</p><h4>Implementação em C</h4><pre>void selectionSort(Item listaDesordenada[], int indexInicio, int indexFinal)<br>{<br>    int i, j;<br>    for (i = indexInicio; i &lt; indexFinal; i++) {<br>        int min = i;<br>        for (j = i + 1; j &lt;= indexFinal; j++) {<br>            if (listaDesordenada[j] &lt; listaDesordenada[min]) {<br>                min = j;<br>            }<br>        }<br>        Item temp = a[i];<br>        a[i] = a[min];<br>        a[min] = temp;<br>    }<br>}</pre><h4>Detalhes do algoritmo</h4><p><strong>a) Percorra índices, compare valores:</strong></p><p>A base são <strong>índices</strong> e os <strong>valores</strong> correspondetes. Se percorre índices, se troca via índices, mas se compara o conteúdo alocado naquele índices. Ex: índice 0 com valor 3 será trocado com índices1 valor 2.</p><p><strong>b) Você precisa de dois </strong><strong>fors aninhados:</strong></p><p>O algoritmo precisa de 2 fors aninhados. Inclusive é culpa desse aninhamento que a complexidade é quadrática. Se seu algoritmo de implementação estiver com mais de 2 fors, ou seja, pior que quadrática, está implementado errado.</p><p>b.1) O 1º for percorrerá a lista mais lentamente, elegendo uma posição, com seu respectivo elemento como mínimo da partida! Uma partida de round-robin!</p><p>Então 1º for dita as partidas de todos contra todos! Este deverá ser enfretado por todos os outros em busca de alguém menor que ele!</p><p>b.2) O 2º for percorerá o resto da lista a partir do elemento índice 0até o final da lista, comparando o valor do índices 0 com todos demais elementos dos índices a frente. O 2º forfor dita as rodadas do round-robin! Se alguém desse segundo for for menor que o elemento da partida, esse tomar o seu lugar como mínimo e vencedor!</p><p>Diante disso, a partir da 2ª partida, você terá três certeza, que a índices do elemento atual até o inicio da lista estão ordenados, que o elemento localizado nesse índices é o menor de todos da lista e que a próxima partida contará com uma rodada menor, pois a lista a ser percorrida na 2ª partida tem 1 elemento a menos que a partida anterior, pois toda nova partida inicia do próximo índices adiante.</p><h4>c) O passo c!</h4><p>O passo “c” foi resumido apenas em “ troque, via índice, as posições desses”. Vamos usar o exemplo [1,2,9,5,10]e eu te explico os detalhes desse passo:</p><p>c.1) Declare o índeci da partida como o min! O elemento do 1º índice da 3ª partida é o número 9, por se encontrar na segunda posição do índice dessa lista. (contamos índice incluindo zero, lembra!)</p><p>Ou seja, nessa 3ª partida já temos os 2 primeiros índices ordenados. Nesse exemplo: [<strong>1,2</strong>,9,5,10]</p><p>c.2) E APITA O ÁRBITRO, COMEÇAM AS RODADAS! AGORA O ÍNDICE 2 ENFRENTA O ÍNDICE 3, CARA A CARA! E AÍ, GALERA, VOCÊS SE PERGUNTAM: SERÁ QUE O ELEMENTO DO ÍNDICE 2 VAI GANHAR OU VAI PERDER??? SE ACONTECER DE ENCONTRARMOS UM VALOR ABAIXO DO MÍNIMO, O ÍNDICE 2 PERDE A JOGADA! E AÍ, AMIGOS, A VARIÁVEL MIN É CORRIGIDA PARA O ÍNDICE DO NOVO MENOR NÚMERO ENCONTRADO. É?? É??!! [1,2,<strong>9</strong>,<em>5</em>,10]</p><p>O ÍNDICE 3 TEM ELEMENTO 5 MEUS AMIGOS! É ISSO MESMO, O ÍNDICE 3 SE CONSAGRA VENCEDOR NESSA DISPUTA ELETRIZANTE! ELE É O NOVO MÍÍÍÍNIMO DESSA PARTIDA! #VAIIICORINTHIAAAANS!</p><p>c.4) VAMOS PARA MAIS UMA RODADA, E O JOGO NÃO PARA! O NOVO MINDO ÍNDICE 3 QUEM VAI DISPUTAR AGORA COM O RESTO DA LISTA! ELE TEM VALOR 5 AGORA! [1,2,9,<strong>5</strong>,<em>10</em>]</p><p>INICIA A RODADA DA VEZ CONTRA O ÍNDICE +1! QUE É O ÍNDIC E 4! A DISPUTA COMEÇA QUENTE, MEUS AMIGOS! O MIN ATUAL ESTÁ DE OLHO NO ÍNDICE 4, QUE CARREGA O VALOR 10! E LÁ VEM O CONFRONTO! O ÍNDICE 4 TENTA COM SEU VALOR 10, MAS O MIN NÃO DÁ CHANCE! É ISSO MESMO, GALERA, O MIN VENCE COM SEU VALOR 5! COM AUTORIDADE, ELE PASSA PRA BASE DA LISTA DESSA PARTIDA!</p><p>c.4) Partida acaba! Vamos entregar os prêmios. Primeiro, temos um <em>vencedor</em> (o menor valor da lista da partida) que será posicionado corretamente no início da lista daquela partida.</p><p>Então você guardar o valor atual (valor do1º índice da partida) em uma variável temporária para não perder. Trocar o valor desse índice com o vencedor, pois ele que ganha a posição de menor da lista agora, e por fim, colocar o valor temporário onde o vencedor estava</p><pre># Lista inicial<br>l = [1,2,9,5,10]<br><br># Índices a serem comparados<br>minIndex = 2  # Índice do valor mínimo inicial (9)<br>jIndex = 3    # Índice do próximo valor a ser comparado (5)<br><br># Troca os valores<br>temp = l[minIndex]  # Armazena o valor atual do minIndex (9)<br>l[minIndex] = l[jIndex]  # Coloca o valor de jIndex (5) na posição de minIndex<br>l[jIndex] = temp  # Coloca o valor temporário (9) na posição de jIndex<br><br>l = [1,2,5,9,10]<br><br># Atualiza o minIndex para o novo índice do menor valor<br>minIndex = jIndex<br></pre><p>Ok! Após esse surto narrativo, espero que tenha entendido que precisa terminar de percorrer a lista inteira de partidas, ou seja, do 1º for com todas as rodadas necessárias para ordenação via selectSort.</p><h4>LeetCode Sort the People</h4><p>O problema que vamos levar nessa série como comparativo é o <a href="https://leetcode.com/problems/sort-the-people/">2418. Sort the People</a> do leetcode! Pretendo usar ele como exemplo para mostra a eficiencia de cada algoritmo de ordenação.</p><p>A aplicação de um algoritmo de ordenação de pessoas, nesse caso, nem é tão complicada. O problema consiste em, dado um array de nomes e um array correspondente de alturas, retornar os nomes das pessoas ordenados em ordem decrescente de altura. Por exemplo, com names = [&quot;Mary&quot;, &quot;John&quot;, &quot;Emma&quot;] e heights = [180, 165, 170], a saída correta seria [&quot;Mary&quot;, &quot;Emma&quot;, &quot;John&quot;].</p><p>Nesse caso, faremos uma busca pelo maior valor, já que o objetivo é uma lista ordenada de forma decrescente.</p><p>A solução mais próxima do <em>Selection Sort</em> aplicada ao <strong>Sort the People</strong> consiste em:</p><pre>/**<br> * Note: The returned array must be malloced, assume caller calls free().<br> */<br>char** sortPeople(char** names, int namesSize, int* heights, int heightsSize, int* returnSize) {<br>    int i, j;<br><br>    // Loop para percorrer todos os elementos da lista de alturas<br>    // Esses ditam as partidas!<br>    for (i = 0; i &lt; heightsSize - 1; i++) {<br>        int max = i;  // Assume o i-ésimo elemento como o maior inicialmente<br><br>        // Encontra o maior elemento no restante da lista<br>        // Esses definem as rodadas que vão ocorrer em cada partida<br>        for (j = i + 1; j &lt; heightsSize; j++) {<br>            // Se encontrar uma altura maior, atualiza para o índice do maior!<br>            if (heights[max] &lt; heights[j]) {<br>                max = j;<br>            }<br>        }<br>        <br>        // Ao fim da partida, então atribui o prêmio! O Max será o max.<br>        // Troca a altura atual pela altura máxima encontrada<br>        int tempHei = heights[i];<br>        heights[i] = heights[max];<br>        heights[max] = tempHei;<br><br>        // Troca o nome correspondente à altura que foi movida<br>        char* tempName = names[i];<br>        names[i] = names[max];<br>        names[max] = tempName;<br>    }<br><br>    // Define o tamanho do array de retorno como o tamanho original de &#39;names&#39;<br>    *returnSize = namesSize;<br><br>    // Retorna o array de nomes agora ordenado de acordo com as alturas<br>    return names;<br>}</pre><p>Como estamos programando em C na plataforma LeetCode, somos obrigados a definir o tamanho do array de retorno da função. O parâmetro returnSize é essencial para que o LeetCode saiba o tamanho exato da lista retornada e possa percorrê-la corretamente para avaliação. Nesse caso, returnSize será igual a namesSize, já que todos os nomes devem ser retornados e a quantidade de nomes não muda.</p><p>Em termos de tempo de execução, essa solução está entre as piores quando comparada a outras propostas submetidas na plataforma.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/767/1*-5BEK21aKCYA1iOGY1ROUg.png" /><figcaption>Análise de runtime</figcaption></figure><p>Em relação a memória, chega ser interessante, afinal, usamos apenas uma variável temporaria a mais.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/785/1*K5HNlEtwVg-Y-pC_iSgcjg.png" /></figure><p>Bom galera! Esse é o SelectionSort. Eu espero te ajudado na compreensão, e não tem como ser mais Clara que isso!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9e3a71a91d08" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Pilhas e filas]]></title>
            <link>https://c137santos.medium.com/pilhas-e-filas-ebb8b70766db?source=rss-a4d176dcd2e6------2</link>
            <guid isPermaLink="false">https://medium.com/p/ebb8b70766db</guid>
            <dc:creator><![CDATA[Santos]]></dc:creator>
            <pubDate>Fri, 04 Oct 2024 00:12:22 GMT</pubDate>
            <atom:updated>2024-10-18T11:19:46.027Z</atom:updated>
            <content:encoded><![CDATA[<h4><em>Não estava meus planos aprender C 🌈 — SenhôMeAJude</em></h4><blockquote>Se você estiver uma pilha, lide 1º com os problemas mais recentes</blockquote><p>1º Recursividade (<a href="https://c137santos.medium.com/recursividade-ae12e6b1ea5e">Medium</a>)</p><p>2º Como aprendi LinkedList (<a href="https://medium.com/@c137santos/como-aprendi-linked-list-991bb146e84b">Medium</a>)</p><p>3º Pilhas e filas (actual)</p><h3>O que você vai encontrar nesse medium gigante?</h3><ol><li>Pilha</li><li>Pilha com lista sem cabeça</li><li>Operações essenciais para pilha</li><li>Perguntas que me fiz sobre pilha</li><li>Fila</li><li>Operações essenciais com fila</li><li>Importância da fila</li><li>Implementando a fila com LinkedList</li></ol><h3>Pilha</h3><p>Falamos brevimente quando tratamos de recursão. Lembra do meu desenho da torre de pisa?</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/770/0*_Pbv-cFBY_gqYGCh.png" /><figcaption><a href="https://medium.com/@c137santos/recursividade-ae12e6b1ea5e">https://medium.com/@c137santos/recursividade-ae12e6b1ea5e</a> — <strong>Toda recursão é uma pilha</strong></figcaption></figure><p>Segundo o <a href="https://www.ime.usp.br/~pf/algoritmos/aulas/pilha.html">Projeto de Algoritmos do Ime</a>: “Uma pilha é uma estrutura de dados que permite remoção e inserção de novos objetos, de forma que o elemento removido é o que está na estrutura há menos tempo” — Famosa ordem de LastInFirstOut.</p><p>Ao trabalhar pilha com lista ligada, evitamos o transbordamento (overflow). Com array, é necessário sempre checar se ainda existe espaço para ocupar no array pretendido.</p><p>Curiosidade é, um array de nelementos está vazio quando testá no índice0, e cheia se t vale a n.</p><p>Como dito na obra “Cracking the coding interview”, por vezes, é mais favorável armazenar dados em uma pilha do que no array.</p><h4>Operações essenciais para pilha</h4><p>Algumas operações são essenciais para trabalhar com as stacks. Se estamos em array, operações como</p><p>pop() Retira um elemento da stack</p><p>push(item) Adicionar um item a stack</p><p>peek() Retorna o topo da stack</p><p>IsEmpty() Verifica se a pilha está vazia</p><p>Para <em>remover </em>elementos da pilha , você desempilhar (= <em>to pop).</em> No array será:</p><pre>x = pilha[--t];</pre><p>Para empilhar, a operação <em>to push:</em></p><pre>pilha[t++] = y;</pre><h4>Pilha com lista sem cabeça</h4><p>Para exercício, vamos escrever um algoritmo para ajudar na respiração quadrática da yoga.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/780/0*B4paQhqZyzzfJ3t9.jpg" /><figcaption>Suponha que o último ar que entrou, é o primeiro que vai sair, pois ta perto do seu nariz!</figcaption></figure><p>Para deixar a coisa ainda mais completa visitando conceitos anteriores, vamos utilizar uma pilha sem cabeça.</p><p>Como desejamos empilhar elementos em uma lista ligada sem nó cabeça, precisamos inserir novos itens antes do 1º elemento atual.</p><p>O algoritmo para inserir elementos no início de uma lista sem nó cabeça exige que passemos o endereço do ponteiro do 1º nó da lista.</p><p>Fazemos isso usando um ponteiro de ponteiro como parâmetro da função, permitindo modificar o ponteiro original para apontar para o novo nó inserido. Além disso, precisamos fornecer o valor que será armazenado no novo nó. (mais detalhes sobre Lista Ligada — <a href="https://medium.com/@c137santos/como-aprendi-linked-list-991bb146e84b">Medium sobre Lista Ligada</a>)</p><p>Esse exercício potencialmente perigoso, pois sem critério de parada para recursão você vai inspirar ou expirar para sempre! Talvez você desmaei! Então construa bem esse algoritmo. (para mais detalhes — <a href="https://medium.com/@c137santos/recursividade-ae12e6b1ea5e">Medium sobre recursão</a>)</p><p>Se bem executado, você vai passar pela experiência interessante de respirar direito enquanto está testando o algoritmo em funcionamento.</p><pre>#include &lt;stdio.h&gt;<br>#include &lt;stdlib.h&gt;<br>#include &lt;unistd.h&gt;  // Para sleep (funciona em Unix-like)<br><br>// Definição da estrutura Node<br>typedef struct Node {<br>    int data;<br>    struct Node* next;<br>} Node;<br><br>int isEmpty(Node** p) {<br>    if (*p == NULL) {<br>        return 1;<br>    } else{<br>        return 0;<br>      }<br>}<br><br>// Função para empilhar (adicionar ao topo da pilha)<br>void inspirar(Node** p, int oxigenio) {<br>    if (*p != NULL &amp;&amp; (*p)-&gt;data &gt;= 100) {<br>        printf(&quot;Pulmão cheio. Vamos segura por 4 segundos! Nível de oxigênio: %d\n&quot;, (*p)-&gt;data);<br>        sleep(4);<br>        return;<br>    }<br>    Node* suspiro = (Node*)malloc(sizeof(Node));<br>    suspiro-&gt;data = oxigenio;<br>    suspiro-&gt;next = *p; // O novo nó aponta para o topo da pilha<br>    *p = suspiro; // Atualiza o ponteiro da pilha para o novo nó como o topo<br>    <br>    printf(&quot;Inspirando oxigênio: %d\n&quot;, suspiro-&gt;data);<br>    sleep(1); // Atraso de 1 segundo<br>    inspirar(p, oxigenio+25);<br>}<br><br>// Função para desempilhar (remover do topo da pilha)<br>void expirar(Node** p) {<br>    if (isEmpty(p)) {<br>        printf(&quot;Pulmão vazio. Vamos segurar por 4 segundos\n&quot;);<br>        sleep(4);<br>        return;<br>    }<br>    Node* temp = *p; // Nó atual no topo da pilha<br>    printf(&quot;Expirando oxigênio: %d\n&quot;, temp-&gt;data);<br>    *p = (*p)-&gt;next; // Atualiza o topo para o próximo nó<br>    free(temp); // Libera a memória do nó removido<br>    sleep(1); // Atraso de 1 segundo<br>    expirar(p);<br>    <br>}<br><br>int main() {<br>    Node* pulmao = NULL; // Inicializa a pilha como vazia<br><br>    for (int i = 0; i &lt; 3; i++){ // A respiração quadratica precisa de 4 tempos<br>        inspirar(&amp;pulmao, 0); <br>        // Empilhando (inspirando) valores em ordem crescente<br>        expirar(&amp;pulmao);<br>        // Desempilhando (expirando) valores em ordem decrescente<br>    }<br>    printf(&quot;Parabéns! Respirou quadraticamente&quot;);<br><br>    return 0;<br>}</pre><p>Algumas notações são interessantes aqui. Vamos observar:</p><ul><li>Como se trata de uma pilha sem cabeça, sua atribuição inicial é Node* pulmão = NULL;</li><li>Como não temos nenhuma célula apontando qual é o começo da lista, então temos uma pilha sem cabeça;</li><li>Para receber esse ponteiro por meio de seu endereço em uma nova função, é essencial a notação de ponteiro de ponteiro. (**)</li></ul><h4><strong><em>Perguntas que me fiz sobre pilha:</em></strong></h4><p>Se eu quero o novo elemento apontando para o topo da pilha, que deveria ser agora 2º elemento após a criação do novo nó, por que estou apontando meu 1º elemento para o 2º e o 2º para o 1ª?? ? Eu deveria apenas fazer meu topo apontar para novo nó que será meu 1º elemento!</p><pre>suspiro-&gt;next = *p;<br>*p = suspiro;</pre><p>Esse último movimento sempre me causou muita dúvida, no movimento de inspirar, para atualizar o ponteiro da pilha para o novo nó *p = suspiro .</p><p>Antes eu achei que, por conta de está fazendo o next do novo nó (suspiro) apontar para do início da fila, na verdade, eu estava fazendo 1080-&gt;5038 .</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/219/1*gpinTu7UiE2tWNVZzvxfUg.png" /><figcaption>Como eu estava entendendo esse movimento</figcaption></figure><p><em>Importante ressaltar! isso é uma pilha, o topo é o último elemento que entrou! A célula que tem o next-&gt;NULL, porque ele é o último elemento da pilha;</em></p><p>O ponteiro do ponteiro <strong>contém</strong>, necessariamente, o endereço da célula topo, nesse caso endereço1080 . Ao atribuir o novo nó a esse ponteiro de ponteiro com movimento de*p = suspiro , por meio da notação da desreferenciação, célula 1080 , dentro do seu contexto, receberá como next a nova célula de endereço 5038 . Causando um empurrão no topo da pilha para segundo colocado.</p><p>Ao terminar o contexto da função insert_before_head ou qualquer outra função que use o ponteiro de ponteiro, as alterações feitas nas ligações da lista encadeada permanecem, porque foi alterado o conteúdo de um ponteiro externo via a desreferenciação (*p). Mesmo que o ponteiro de ponteiro em si &quot;morra&quot; quando a função termina, a estrutura da lista permanece intacta. Restando 5038-&gt;1080-&gt;null</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/590/1*9uYWkS6ui8c_acysyy0URA.png" /><figcaption>Lembre-se : uma stack é uma pilha, o que está no topo ainda está em execução</figcaption></figure><h4>Fila</h4><p>O <a href="https://www.ime.usp.br/~pf/algoritmos/aulas/pilha.html">Projeto de Algoritmos do Ime</a>: “Uma pilha é uma estrutura de dados que permite remoção e inserção de novos objetos, de forma que o elemento mais antigo é o primeiro a deixar a estrutura” — Famoso FirstInFirstOut.Os itens serão retirados na mesma ordem que foram adicionados.</p><p>A fila trabalha com um head e um tail. Onde head aponta para início e o tail aponta para o fim da fila. As principais operações para manipular uma fila são o adicionar item no final da fila, e o remove(item) da última posição.</p><h4>Operações essenciais com fila</h4><p>add() Adiciona um elemento no final da fila</p><p>remove(item) Remove o 1ª item da fila</p><p>peek() Retorna o inicio da fila</p><p>IsEmpty() Verifica se a fila está vazia</p><p>Em se tratando de uma fila em array, existe uma coisa pouco intuitiva sobre inserir e retirar elementos de uma fila apresentada no matérial do IME, pois eles não lidam com uma remoção física do elemento do array, mas o avanço para o próximo elemento.</p><pre>x = fila[p++]</pre><p>Esse é o comportamento típico de uma fila, onde se lê o primeiro elemento e depois vai para o próximo, incrementando o índice, sem remove-lo físicamente da fila. Isso é percorrer uma lista.</p><p>Enquanto inserir será buscar o índice depois do último e adicionar o novo elemento.</p><pre> fila[u++] = y;</pre><h4>Importância da fila</h4><p>A fila é uma estrutura essencial em diversos algoritmos de grafos, especialmente em problemas que envolvem cálculo de distâncias, como a Busca em Largura (Breadth-First Search — BFS).</p><p>Um conceito interessante é que, a fila está vazia quando há um encontro entre head e tail.</p><p>No contexto de grafos, a fila estará vazia quando todos os vértices acessíveis já tiverem sido processados.A condição de fila vazia indica que não há mais vértices para explorar.</p><p>Vamos aprofundar nisso mais a frente na série.</p><h4>Implementação de fila em linked-list</h4><p>Para ilustrar, esse desenho é do livro <em>Algoritms in C</em>, com representação de head e de tail.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/450/1*RsNJe1ct2SKuLTCqZwjkug.png" /><figcaption><strong>SEDGEWICK, Robert.</strong> Algorithms in C. 3. ed. [S.l.]: Addison-Wesley, 1998. 720 p. ISBN 0–201–31452–5</figcaption></figure><p>Para o nosso estudo de caso, vamos utilizar um sistema de alongamento com enrijecimento e relaxamento de músculos conforme a lógica de fila.</p><p>Primeiro músculo tensionado, será o primeiro a relaxar.</p><pre>#include &lt;stdio.h&gt;<br>#include &lt;stdlib.h&gt;<br>#include &lt;unistd.h&gt;  // Para sleep (funciona em Unix-like)<br><br>typedef struct Node {<br>    char musculo[50];<br>    struct Node* next;<br>} Node;<br><br>Node* HEAD = NULL;<br>Node* TAIL = NULL;<br><br>int isEmpty() {<br>    return HEAD == TAIL;<br>}<br><br>void adicionarFila(const char* musculoTenso) {<br>    Node* musculoFila = (Node*)malloc(sizeof(Node));<br>    strcpy(musculoFila-&gt;musculo, musculoTenso);<br>    musculoFila-&gt;next = NULL;<br><br>    if (HEAD == NULL) {<br>        HEAD = TAIL = musculoFila;<br>    } else {<br>        TAIL-&gt;next = musculoFila;<br>        TAIL = musculoFila;<br>    }<br>}<br><br>void removerFila() {<br>    Node* temp = HEAD;<br>    HEAD = HEAD-&gt;next;<br>    if (isEmpty()) {<br>        TAIL = NULL;<br>    }<br>    free(temp);<br>}<br><br>void filarelaxamento() {<br>    if (isEmpty()) {<br>        printf(&quot;Tudo relaxado!\n&quot;);<br>        return;<br>    }<br>    printf(&quot;Agora relaxe o musculo %s\n&quot;, HEAD-&gt;musculo);<br>    removerFila();<br>    sleep(2);<br>    filarelaxamento();<br>}<br><br>void filaTensao(Node* inicio) {<br>    if (inicio == TAIL) {<br>        printf(&quot;Tensione o musculo %s\n&quot;, inicio-&gt;musculo);<br>        sleep(2);<br>        return;<br>    }<br>    printf(&quot;Tensione o musculo %s\n&quot;, inicio-&gt;musculo);<br>    sleep(2);<br>    filaTensao(inicio-&gt;next);<br>}<br><br>int main() {<br>    char musculo[50];<br>    for (int i = 0; i &lt; 3; i++) {<br>        printf(&quot;Digite o nome do músculo que você deseja relaxar (%d/3): &quot;, i + 1);<br>        scanf(&quot;%49s&quot;, musculo); <br>        adicionarFila(musculo);<br>    }<br><br>    filaTensao(HEAD);<br><br>    filarelaxamento();<br><br>    return 0;<br>}</pre><p>Como estamos com fila com cabeça, pude ter o deleite e direito de declarar a cabeça em um contexto global! Pois cabeças não mudam 🌐</p><p>Como estamos trabalhando com LL, não foi necessário ficar retornando estrutura final, afinal, eu posso consulta-la, mesmo após modificado, apenas pela sua cabeça.</p><p>Só precisei passa-la em 1contexto.</p><p>Na função filaTensao() , porque usei da recursão para percorre-la, tensionando os músculos na ordem em que foram adicionados.</p><p>O adicionarFila(), adiciona um músculo ao final da fila. Se a fila estiver vazia, o primeiro músculo se torna tanto a cabeça (HEAD) quanto a cauda (TAIL). Para receber nessa função, é preciso o params ser declarado como ponteiro.</p><p>isEmpty() , abraça aquele conceito de que fila vazia é o encontro de Head e Tail.</p><p>removerFila(),Remove o primeiro músculo da fila, que está na frente (HEAD). Essa função mantém o comportamento FIFO, removendo sempre o primeiro elemento da fila. Não precisei usar recursão, pois eu não iria mais necessitar desse elemento em próxima operação, então usei o HEAD mesmo.</p><p>filarelaxamento(), Processa a fila, relaxando os músculos em ordem. A função remove cada músculo após relaxá-lo e faz uma pausa de 2 segundos entre os relaxamentos usando a função sleep().</p><p>Não tenho como ser mais clara que isso! Espero que tenham relaxado com esses algoritmos!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=ebb8b70766db" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Como aprendi Linked List!]]></title>
            <link>https://c137santos.medium.com/como-aprendi-linked-list-991bb146e84b?source=rss-a4d176dcd2e6------2</link>
            <guid isPermaLink="false">https://medium.com/p/991bb146e84b</guid>
            <category><![CDATA[estruturas-de-dados]]></category>
            <category><![CDATA[linked-lists]]></category>
            <category><![CDATA[leetcode-solution]]></category>
            <category><![CDATA[c]]></category>
            <dc:creator><![CDATA[Santos]]></dc:creator>
            <pubDate>Mon, 23 Sep 2024 12:21:25 GMT</pubDate>
            <atom:updated>2024-10-18T11:13:59.405Z</atom:updated>
            <content:encoded><![CDATA[<h4>Não estava meus planos aprender C 🌈 — SenhôMeAJude</h4><blockquote>Cuidado para não perde a cabeça, é sério!</blockquote><p>1º Recursividade (<a href="https://c137santos.medium.com/recursividade-ae12e6b1ea5e">Medium</a>)</p><p>2º Como aprendi LinkedList (actual)</p><h4>O que você vai encontrar nesse medium gigante?</h4><ol><li>Conceito e representação de LinkedList</li><li>Diferença de LL e Array</li><li>Notações necessárias para ponteiro</li><li>Perdendo a cabeça com o conceito da cabeça e da falta de cabeça em LL</li><li>Inserindo células em uma LL</li><li>Deletando células em uma LL</li><li>Mergeando duas sortLinkedList</li><li>Invertendo uma LL com exercício do Swap Nodes in Pairs</li></ol><p>Tempo passa, mundo gira, e aqui estamos, dando continuidade a série de aprendizagem de estrutura de dados em C a partir de exercícios práticos do LeetCode.</p><blockquote>Linked List é uma estrutura de dados linear composta por nós. Mais especificamente, é uma sequência de células, que cada uma é um objeto com conteúdo e o endereço da célula seguinte.</blockquote><p>Em C, o simbolo * indica que estamos tratando de um ponteiro! Um tipo que guarda referência para o próximo endereço de memória (chamamos aqui de célula, ok?). Vamos dar o nome a essa célula de ListNode.</p><pre>struct ListNode {<br>    int val;<br>    struct ListNode* next;<br>};</pre><h4><strong>Representação da LL em desenho animado.</strong></h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*T2kBmI6yrALA-kVMiUCw3A.png" /></figure><ul><li><strong>Diferença de LL e Array. (Em python parece tudo igual…)</strong></li></ul><p>Para encontrar/buscar k elemento na LinkedList é preciso percorrer cada célula da LL para encontrar/buscar a k. Enquanto no array, o tempo de acesso é constante por conta do acesso via index.</p><p>Quero o 3º valor da LL e o 3º do Array.</p><p>LL = Consulto 1º ponteiro para saber valor do 2º ponteiro, para visitar o 2º ponteiro em busca do valor do 3º ponteiro, visito 3º ponteiro e pego seu valor. — 3 operações —</p><p>Array = Consulto a 3º posição do array e obtenho seu valor. a[2]. FIM! Ou seja, a indexação nesse caso faz diferença.</p><p>O fato de ter um ponteiro viabiliza o armazenamento de uma lista de valores em um espaço descontínuo da memória! Como visto na figura do homem aranha, 1ª célula está posição 0 da memória, enquanto a segunda na 2º posição, e graça a informação de onde está a próxima alocada no anterior!</p><p>Outra vantagem da LL é a inserção e exclusão em tempo constante, O(1). Enquanto nos arrays, como o armazenamento exige um espaço contíguo na memória, a inserção ou exclusão requer a realocação do array inteiro para um novo espaço que o comporte, ou o deslocamento de todas as células subsequentes para preencher o espaço vazio.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*homEDR7GI2yIrieg" /><figcaption>Bing 2024</figcaption></figure><h3>Notações necessárias para ponteiro</h3><p>Geralmente células são construídas da seguinte forma.</p><ul><li>Elas contém um ponteiro do tipo ListNode chamado *next</li><li>ListNode contém, obrigatoriamente, 4 bytes, visto que contém o *next que é do tipo ponteiro e exige esse tamanho de memória para seu tipo.</li><li>ListNode podem conter mais <strong>x</strong> bytes de acordo com o tipo de valor que ele abrigar, nesse nosso caso é um inteiro (int val).</li></ul><pre>struct ListNode {<br>    int val;<br>    struct ListNode *next;<br>};</pre><ul><li>Interessante tratar ListNod como um novo tipo de dados, por isso a tipagem com typedef struct e batizar com mesmo nome, por exemplo. Struct ListNode chamará ListNode.</li><li>Não tenho usado tanto esse batismo nas resoluções de problemas, porque queria decorar a sintaxe e diferença entre ponteiro *next e a estrutura que abriga o ponteiro *next.</li><li>O batismo permite que você não ficar declaramento o tempo todo o struct com struct ListNode ListNode, pode fazer apenas ListNode node.</li></ul><pre>typedef struct ListNode ListNode;<br><br>// ou<br><br>typedef struct ListNode {<br>    int data;           <br>    struct ListNode* next;<br>} ListNode;</pre><ul><li>Ponteiros são do mesmo tipo da estrutura criada.</li><li>O operador &amp; obtém endereço de variável. Devendo ser atribuído a um variável do tipo ponteiro.</li></ul><pre>struct ListNode* ptr = &amp;(*newCell);<br> Isso é igual e redundante para a operação<br>struct ListNode* ptr = newCell;</pre><p><em>Qual a diferença entre </em><em>*novaCelula e </em><em>novaCelula?</em></p><ul><li><strong>novaCelula</strong> (sem o *): é o ponteiro em si, ou seja, uma variável que armazena o <strong>endereço</strong> de uma estrutura.</li><li><strong>*novaCelula</strong>: é a <strong>desreferência</strong> do ponteiro, ou seja, você está acessando o valor (a estrutura) para o qual o ponteiro aponta.</li></ul><p>Sim, ponteiros <strong>são representados</strong> pela notação *, mas o uso de * depende do que você está fazendo com o ponteiro:</p><ol><li><strong>Declaração de um ponteiro:</strong><br>Para declarar uma variável que <strong>é um ponteiro</strong>, você usa * na declaração:</li></ol><pre>struct ListNode* novaCelula;  // novaCelula é um ponteiro para um struct ListNode</pre><p>Aqui, novaCelula <strong>é um ponteiro</strong>, mas a partir desse momento, o uso de * é opcional, dependendo do que você está fazendo.</p><ol><li><strong>Usando o ponteiro (sem </strong><strong>*):</strong><br>Quando você manipula ou passa o <strong>ponteiro em si</strong> (o endereço que ele armazena), você <strong>não usa o </strong><strong>*</strong>. Por exemplo:</li></ol><pre>novaCelula = malloc(sizeof(struct ListNode));  // atribuindo um endereço a novaCelula</pre><p>Aqui, novaCelula representa o ponteiro, ou seja, o endereço de memória que aponta para uma estrutura ListNode, mas você <strong>não precisa usar </strong><strong>*</strong> porque você está lidando com o ponteiro como uma variável que armazena um endereço.</p><ol><li><strong>Desreferenciando o ponteiro (com </strong><strong>*):</strong><br>Quando você quer acessar o <strong>valor para o qual o ponteiro aponta</strong>, você usa * para <strong>desreferenciar</strong> o ponteiro:</li></ol><pre>(*novaCelula).valor = 10; // desreferenciando novaCelula para acessar o membro valor</pre><p>A forma acima é redundate e pouco utilizada. Mais simples:</p><pre>novaCelula-&gt;valor = 10;  // usando o operador -&gt; para desreferenciar e acessar o valor</pre><p>No caso de estruturas, usamos -&gt; como uma forma simplificada de desreferenciar e acessar diretamente os membros de uma estrutura. Então, aqui está uma reformulação da explicação:</p><pre>outra-&gt;data++; // Acessa e incrementa o valor de &#39;data&#39; na estrutura apontada por &#39;outra&#39;</pre><ul><li>Use -&gt; quando você tem um <strong>ponteiro</strong> para uma estrutura. Acessa o valor através do ponteiro.</li></ul><pre>struct ListNode {<br>    int val;<br>    struct ListNode* next;<br>}; <br>// Alocando dinamicamente um nó<br>struct ListNode* node = malloc(sizeof(struct ListNode)); // tratando como ponteiro<br>node-&gt;val = 10;           // Usando &#39;-&gt;&#39; porque &#39;node&#39; é um ponteiro<br>node-&gt;next = NULL;</pre><ul><li>O uso do . é mais utilizado quando você tem uma <strong>instância direta</strong> da estrutura (não um ponteiro). Isso é comum quando você tem uma variável que representa a estrutura diretamente, não uma referência a ela. Perceba que apenas o ListNode interno é identificado como ponteiro, não oexterno.</li></ul><pre>struct ListNode { // essa é a estrutura que contém ponteiro<br>    int val;<br>    struct ListNode* next; // Este next é o ponteiro para o próximo nó<br>};<br>struct ListNode node;<br>node.val = 10; // Usando &#39;.&#39; porque &#39;node&#39; é uma instância direta<br>node.next = NULL;</pre><ul><li>É possível acessar o ponteiro dos seguintes usando next -&gt; next -&gt; next…Só cuidado, pois se o 2º next for NULL, isso dar erro. Portanto, sempre verificar antes desse tipo de acesso se if(next-&gt;next !=null)</li></ul><pre>[(1,1), (30,2), (12,3)...]<br>struct ListNode* iPoint = i-&gt;next-&gt;next<br>printf(iPoint)<br>$ 3</pre><h3>Perdendo a cabeça com o conceito das cabeças da lista.</h3><p>Cabeça de uma lista é uma célula especial qual o conteúdo é desprezado, porém seu ponteiro é o <strong>X</strong> da questão. Uma sentinela. É a partir dessa cabeça que sabemos onde está o começo da lista encadeada.</p><p>Uma lista vazia com cabeça existirá uma célula, com conteúdo desprezado, e o next NULL. Ela serve apenas para indicar o inicio da lista e facilitar manipulação daquela lista. Ela é um ponteiro universal para toda estrutura. A representação da lista com cabeça vazia é:</p><figure><img alt="http://www.decom.ufop.br/reinaldo/site_media/uploads/2013-02-bcc202/aula_09_-_listas_(parte_2)_(v1).pdf" src="https://cdn-images-1.medium.com/max/213/1*Vq_d74vfffbzpCSoxRDldA.png" /><figcaption><a href="http://www.decom.ufop.br/reinaldo/site_media/uploads/2013-02-bcc202/aula_09_-_listas_(parte_2)_(v1).pdf">http://www.decom.ufop.br/reinaldo/site_media/uploads/2013-02-bcc202/aula_09_-_listas_(parte_2)_(v1).pdf</a></figcaption></figure><pre>struct ListNode {<br>    int val;<br>    struct ListNode* next;<br>};<br><br>struct ListNode* node = malloc(sizeof(struct ListNode));<br>node-&gt;next = NULL;</pre><p>Uma lista sem cabeça é um ponteiro sem alocação de memória, pois o conteúdo da primeira célula é tão relevante quanto o das demais. Nesse caso, a lista sem cabeça está vazia se o endereço de sua primeira célula é NULL. Para criar uma lista vazia basta:</p><pre>celula *ini; <br>ini = NULL;</pre><p>Nesse caso, o problema clássico que vai ajudar na compreensão (próximo medium) da estrutura de fila é a inserção de nós em uma lista sem cabeça. Aqui está um exemplo de código de inserção de valor antes da cabeça de uma pilha sem cabeça.</p><pre>#include &lt;stdio.h&gt;<br>#include &lt;stdlib.h&gt;  // Para malloc e free<br>#include &lt;unistd.h&gt;  // Para sleep (funciona em Unix-like)<br><br>// Definição da estrutura Node<br>typedef struct Node {<br>    int data;<br>    struct Node* next;<br>} Node;<br><br>// Função para empilhar (adicionar ao topo da pilha)<br>void empilhar(Node** p, int novoValor) {<br>    Node* newCell = (Node*)malloc(sizeof(Node));<br>    newCell-&gt;data = novoValor;<br>    newCell-&gt;next = *p; // O novo nó aponta para o antigo topo da pilha<br>    *p = newCell; // Atualiza o ponteiro da pilha para o novo nó como o topo<br>}<br><br>// Função para desempilhar (remover do topo da pilha)<br>void desempilhar(Node** p) {<br>    if (*p == NULL) {<br>        printf(&quot;Pilha vazia!&quot;);<br>    } else {<br>        Node* temp = *p; // Nó atual no topo da pilha<br>        *p = (*p)-&gt;next; // Atualiza o topo para o próximo nó<br>        free(temp); // Libera a memória do nó removido<br>    }<br>}<br><br>int main() {<br>    Node* pilha = NULL; // Inicializa a pilha como vazia<br><br>    // Empilhando valores em ordem crescente<br>    empilhar(&amp;pilha, 25);<br>    empilhar(&amp;pilha, 50);<br><br>    // Desempilhandovalores em ordem decrescente<br>    empilhar(&amp;pilha);<br>    empilhar(&amp;pilha);<br>    empilhar(&amp;pilha); // Tentativa de desempilhar quando a pilha está vazia<br><br>    return 0;<br>}</pre><p>Representação do que ta rolando via desenhos!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/590/1*IRxQmyJ4cN4YV3nruSAvyg.png" /><figcaption>Depois que aquela stack superior da pilha morrer, vai restar 5038 -&gt; 1080</figcaption></figure><p>Agora podemos abordas as operações!</p><h3><strong>Inserindo uma célula em uma LL</strong></h3><p>A função recebe um ponteiro da LL e o novo valor da célula a ser inserido. O valor deve ser atribuído ao nova célula. Essa nova célula deve ficar entre o ponteiro e o seu next:</p><p>p -&gt; nextDep | p -&gt; novoValor -&gt; nextDep</p><p>IMPORTANTE: Sempre que for inserir ou deletar, precisa, necessariamente, que dois elementos apontarem para um mesmo next em um determinado momento do código, ou VOCÊ VAI PERDE O PONTEIRO! Isso também evita o uso de variável auxiliar.</p><p>Visualize você <strong>perdendo</strong> o ponteiro ao ficar sem referência do next do 1º:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/678/1*lglvA1RVPNUDWuo3vMTxjQ.png" /><figcaption>Você perdendo o ponteiro. Nota dó!</figcaption></figure><p>Vamos desenhar os passos corretos para não perder o ponteiro.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/678/1*AG2RkBx7HF_08ggOITe-cw.png" /><figcaption>Você não perdendo ponteiro!</figcaption></figure><p>Agora em código!</p><pre>struct ListNode {<br>    int data;<br>    struct ListNode* next;<br>}<br><br>void insertNodeInList(int data, struct ListNode* p) {<br>      struct ListNode *novaCelula = malloc(sizeof(struct ListNode))<br>      novaCelula -&gt; data = data;<br>      novaCelula -&gt; next = p -&gt; next;<br>      p-&gt;next = novaCelula;<br>}</pre><p><em>Perguntas que me fiz:</em></p><p><em>Porque ao atribuir memória, precisei atribuir ao ponteiro, e não a célula inteira? Ou seja, atribui a *novaCelula, ao invés de novaCelula.</em></p><p>Porque a função que aloca memória (malloc), retorna um ponteiro do tipo void *, que é genérico e aponta para qualquer tipo de dado para realizar a alocação de memória. PORTANTO, ela precisa ser recebida pela variável que indica seu tipo de dado apropriado que a memória vai tratar. Por isso o struct ListNode *, que indica a estrutura de ponteiro para a novaCelula.</p><h3><strong>Deletando células em LL</strong></h3><p>Para deletar um nó em uma lista encadeada, é preciso ter cuidado para não tentar acessar nenhum next de um NULL point. Por isso vamos adotar duas abordagens complementares:</p><ol><li><strong>Redirecionamento de Ponteiros</strong>: redirecionar o ponteiro do nó anterior ( nó 1) diretamente para o nó seguinte ao que será excluído (nó 3). Em seguida, atribuímos NULL ao ponteiro next do nó que desejamos excluir (nó 2), isolando-o da lista. Embora essa técnica remova o nó da lista, ela pode ser problemática se o nó que precisa ser excluído for a própria cabeça da lista.</li><li><strong>Ajuste da Cabeça da Lista</strong>: A segunda abordagem, complementar à primeira, envolve encontrar uma nova cabeça válida para a lista. Uma cabeça válida é um nó não nulo cujo valor não seja igual ao valor que deve ser removido. Uma vez encontrada essa cabeça válida, podemos aplicar a primeira abordagem para o restante da lista.</li></ol><p>Como vamos usar recursão, nosso critério de parada será quando não houver mais um próximo nó (next) a ser processado.</p><p>Caso precise se aprofundar em recursão, dá uma lida no <a href="https://medium.com/@c137santos/recursividade-ae12e6b1ea5e">medium anterior</a>!)</p><p>Vamos ilustrar essa lógica com o exercício de remover elementos de uma lista encadeada (remove linked list elements). Dado uma lista encadeada, precisamos remover todos os nós cujo valor seja igual ao valorProibido.</p><p><strong>Verificação da Cabeça</strong>: Primeiramente, verificamos se a cabeça da lista é válida, ou seja, se ela não é nula e se o valor contido nela é diferente do valorProibido.</p><p><strong>Remoção de Cabeças Inválidas</strong>: Se a cabeça não for nula, mas contiver o valorProibido, guardamos temporariamente esse nó, avançamos a cabeça para o próximo nó (head = head-&gt;next), e liberamos a memória do nó anterior, removendo-o da lista. Esse processo se repete em um loop até encontrarmos uma cabeça válida.</p><p><strong>Recursão</strong>: Depois de validar a cabeça, verificamos se a lista ainda contém elementos. Se a lista estiver vazia (cabeça for NULL), retornamos NULL. Caso contrário, aplicamos recursivamente a mesma lógica para o próximo nó, ajustando o ponteiro next do nó atual para o resultado da chamada recursiva.</p><pre>struct ListNode* removeElements(struct ListNode* head, int valorProibido) {<br>    while (head != NULL &amp;&amp; head-&gt;val == valorProibido) {<br>        struct ListNode* temp = head;<br>        head = head-&gt;next;<br>        free(temp);<br>    }<br><br>    if (head == NULL) {<br>        return NULL;<br>    }<br><br>    head-&gt;next = removeElements(head-&gt;next, valorProibido);<br><br>    return head;<br>}</pre><p>Agora vamos aos exercícios de fixação!</p><p>Exercícios do leetcode que ajudou a entender LL foi <a href="https://leetcode.com/problems/merge-two-sorted-lists/description/">Merge Two Sorted Lists</a> e o <a href="http://24. Swap Nodes in Pairs">24.Swap Nodes in Pairs do Leetcode</a>.</p><p>Primeira grande lição é<a href="https://leetcode.com/problems/reverse-linked-list/description/"> Reverse Linked List</a></p><h3>Mergeando duas sortLinkedList</h3><p>Basicamente ele dá duas listas <strong>ligadas</strong> e <strong>ordenadas</strong> e quer o retorno de uma única lista ordenada com números de ambas.</p><p>Ao receber duas listas ligadas, é necessário verificar se alguma dela é nula, pois se for, já retorna a outra lista, que a <strong>list1</strong> não tem nada para ligar com nínguem, então ela vai ser, necessariamente, igual a <strong>list2.</strong> E vice-versa.</p><p>Caso não sejam nulas, verifica se o 1º valor da <strong>list1</strong> é menor ou igual ao valor da 1º da <strong>lista2</strong>.</p><p>Dado a<strong> list1 = [1,2,4]</strong> e <strong>list2 = [1,3,4]</strong>,</p><p>Então temos uma igualdade! Diante disso, eu vou disponibilizar meu ponteiro da <strong>list1</strong> para receber o valor do próximo endereço! Pois ele vai ser o inicio da lista!</p><p>Chamo a função novamente (sim, vamos trabalhar com recursão), e entrego a função <strong>mergeTwoLists</strong> a <strong>list1</strong> a partir do 2º valor dela, ou seja, a partir do endereço do next, ou seja, entrego para ela a linkedList <strong>list1</strong> dessa forma = [2,4].</p><pre>list1 -&gt; next = mergeTwoLists([2,4], [1, 3,4])</pre><p>Pois eu já tenho o 1º elemento esperando na filinha para ser religado!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/681/1*fZp6MAIpW2rfEg7VoLx_nA.png" /></figure><p>Na próxima iteração, então, <strong>list1 = [2,4]</strong>,<strong> list2 = [1,3,4]. </strong>Portanto, caímos no else e o next(ponteiro) do valor <strong>1</strong> de <strong>list2</strong> fica disponível para atribuição.</p><p>Sabendo que o próximo número se trata do <strong>1 </strong>da <strong>list2</strong>, já podemos deduzir que na volta da recursão, o next(ponteiro) do valor <strong>1</strong> da <strong>list1</strong>, que estava disponível para atribuição, receberá o endereço do <strong>1</strong> da <strong>list2</strong>.</p><p>Agora é o next(ponteiro) da <strong>list2</strong> disponível para atribuição com uma chamada de recursão onde passamos <strong>list2</strong> a partir do seu <strong>index 2!</strong></p><pre>list2 -&gt; next = mergeTwoLists([2,4], [3,4])</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/681/1*aceZQKpBL0Ftj5Nwof3cNw.png" /></figure><p>A função cai no if porque <strong>2</strong> da <strong>list1 </strong>é maior que<strong> 3 </strong>da<strong> list2</strong>. Ficando o next(ponteiro) de <strong>2</strong> disponível para atribuição, enviando <strong>list1</strong> a partir do ponteiro de <strong>2</strong>.</p><pre>list1 -&gt; next = mergeTwoLists([4], [3,4])</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/681/1*8gtrPLKNLRf9U_-c-xUDJA.png" /></figure><p>Próximo caso, já que valor <strong>4</strong> de <strong>list1</strong> é maior que o <strong>3</strong> de <strong>list2</strong>, a função vai para o else, onde deixa o ponteiro de <strong>list2</strong> do valor <strong>3</strong> disponível para atribuição, e passa a <strong>list2</strong> para função a partir desse.</p><pre>list2 -&gt; next = mergeTwoLists([4], [4])</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/681/1*fQhTUt-yZiyQl77vnzfsPw.png" /></figure><p>Então, sabendo que a próxima iteração temos ambos iguais, caímos no if, disponibilizamos o ponteiro do valor <strong>4</strong> da <strong>list1</strong> e chamamos a função com <strong>list1</strong> <strong>Null</strong> (que indica o tail — final da lista) e <strong>list2</strong> com valor <strong>4</strong>.</p><pre>list2 -&gt; next = mergeTwoLists([Null], [4])</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/681/1*2eIdNhPOoPv9jhL0_R1vhQ.png" /></figure><p>Nessa iteração, caímos no 1º if, pois list1 está null, portanto, retornamos para o ponteiro do valor 4 de list1 a referência da list2 por completo.</p><p>Agora é o retorno da recursão que vai atribuir aos ponteiros disponíveis a nova referência, gerando uma lista que tem essas ligações.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/681/1*84BySAqOS4mgdXB01DbmxA.png" /></figure><pre>/**<br> * Definition for singly-linked list.<br> * struct ListNode {<br> *     int val;<br> *     struct ListNode *next;<br> * };<br> */<br>struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {<br>    if(list1 == NULL){<br>       /*6) f([null], [4]*/<br>        return list2;<br>    }<br>    if(list2 == NULL){<br>        return list1;<br>    }<br>    if(list1 -&gt; val &lt;= list2 -&gt; val){<br>        list1 -&gt; next = mergeTwoLists(list1 -&gt; next, list2);<br>        /* 1) 1.next  f([2,4], [1,3,4]<br>        3) 2.next  f([4], [3,4]<br>        5) 4.next  f[null], [4]*/<br>        return list1;<br>    }<br>    else {<br>        list2 -&gt; next = mergeTwoLists(list1, list2 -&gt; next);<br>        /* 2) 1.next  f([2,4], [3,4])<br>        4) 3.next  f[4], [4]*/<br>        return list2;<br>    }<br>}</pre><h3>Swap Nodes in Pairs</h3><p>Dado uma lista, é preciso inverter a posição de dois em dois elementos, movimentando apenas seus ponteiros.</p><pre>Input: head = [1,2,3,4]<br>Output: [2,1,4,3]</pre><h4>1º Tratando o caso base.</h4><p>Quando a cabeça é nula ou a cabeça não tem head.</p><p>A 1ª célula de uma lista encadeada pode ser um mero marcador de início, onde o conteúdo é ignorado. Ou seja, ela só tem informação de ponteiro.</p><ul><li><strong>Lista Vazia</strong>: Se head é NULL, significa que a lista não existe.</li><li><strong>Lista com Um Nó</strong>: Se head não é NULL e head-&gt;next é NULL, isso indica que o nó cabeça é o único nó na lista. Mesmo que o conteúdo da cabeça não seja útil, isso é diferente de não existir uma lista.</li></ul><pre>struct ListNode* swapPairs(struct ListNode* head) {<br>    if (!head || !head-&gt;next) {<br>        return head;<br>    }</pre><p>Agora precisamos armazenar:</p><ul><li>A célula atual. A 1ª interação contém o ponteiro do Head. Não tenho certeza do porque, mas se usarmos uma variável para armazenar esse ponteiro, o código torna 4 segundos mais rápido do que o uso direto do next do head, segundo avaliação do LeetCode.</li></ul><pre>struct ListNode* current = head;</pre><ul><li>O novo início, o ponteiro do next do head, que deve vir para o ínicio da lista obrigatoriamente!</li></ul><pre>struct ListNode* newHead = head-&gt;next;</pre><ul><li>Variável auxiliar chamado prévios. Essa guardará a referência do 3º next! Qual deverá o 1º célula apontar. (Entende? A 1ª apontar para 3ª no endereço 2 da memória, a 2ª apontar para a 1ª no endereço 0 da memória)</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/717/1*YDMpHjJK7pB24USuFalAkQ.png" /></figure><p>Iniciar while e ele dura até o fim da lista. Identificamos o fim da lista enquanto houver um next para da célula atual.</p><pre>while (current &amp;&amp; current-&gt;next)</pre><p>Agora realiza as trocas dos ponteiros da célular atual e da sua sucessora.</p><ol><li>Pega ponteiro do terceiro;</li><li>Pega ponteiro do segundo;</li><li>Ponteiro da segunda célula recebe ponteiro da atual célula (necessariamente a célula anterior a dela)</li><li>Ponteiro da célula atual recebe ponteiro da segunda célula (necessariamente a célula posterior a ela)</li></ol><pre>struct ListNode* nextPair = current-&gt;next-&gt;next;<br>struct ListNode* second = current-&gt;next;<br><br>second-&gt;next = current;<br>current-&gt;next = nextPair;</pre><p>Caso seja uma iteração que tenha uma célula anterior as duas quais estamos trabalhando, é importante passar da anterior para 2ª.</p><pre>if (previous) {<br>      previous-&gt;next = second;<br>  }</pre><p>Por fim, atualiza a célula previous com ponteiro da 1ª célula. Para que no futuro, possamos trocar corretamente o valor da iteração anterior com a nova.</p><p>Ao terminar, retornamos o início da lista, armazenado no começo do código, que era nossa antiga 2ª célula.</p><pre>/**<br> * Definition for singly-linked list.<br> * struct ListNode {<br> *     int val;<br> *     struct ListNode *next;<br> * };<br> */<br><br>struct ListNode* swapPairs(struct ListNode* head) {<br>    if (!head || !head-&gt;next) {<br>        return head;<br>    }<br>/* Caso que a lista pode ter um único ou nenhum elemento */<br><br>    struct ListNode* current = head;<br>    struct ListNode* newHead = head-&gt;next;<br>    struct ListNode* previous = NULL;<br><br>    while (current &amp;&amp; current-&gt;next) {<br>        struct ListNode* nextPair = current-&gt;next-&gt;next;<br>        struct ListNode* second = current-&gt;next;<br><br>        second-&gt;next = current;<br>        current-&gt;next = nextPair;<br><br>        if (previous) {<br>            previous-&gt;next = second;<br>        }<br><br>        previous = current;<br>        current = nextPair;<br>    }<br><br>    return newHead;<br>}</pre><p>Confuso? É legal fazer teste de mesa para isso!</p><p>Recomendo esse exercício de fixação</p><p>Ordene a lista ligada <a href="https://leetcode.com/problems/insertion-sort-list/description/">https://leetcode.com/problems/insertion-sort-list/description/</a></p><p>Obrigada por chegar até aqui! Bons estudos!</p><p>Não tenho como ser mais Clara que isso!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=991bb146e84b" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Recursividade]]></title>
            <link>https://c137santos.medium.com/recursividade-ae12e6b1ea5e?source=rss-a4d176dcd2e6------2</link>
            <guid isPermaLink="false">https://medium.com/p/ae12e6b1ea5e</guid>
            <category><![CDATA[logic]]></category>
            <category><![CDATA[recursive-function]]></category>
            <category><![CDATA[c]]></category>
            <category><![CDATA[lógica-de-programação]]></category>
            <category><![CDATA[structured-data]]></category>
            <dc:creator><![CDATA[Santos]]></dc:creator>
            <pubDate>Tue, 10 Sep 2024 01:09:22 GMT</pubDate>
            <atom:updated>2024-09-23T12:23:13.199Z</atom:updated>
            <content:encoded><![CDATA[<p>Vou começar a série “Não estava meus planos aprender C 🌈 — SenhôMeAJude”</p><blockquote>Sumário da série “Não estava meus planos aprender C 🌈 — SenhôMeAJude”</blockquote><p>1º Recursividade.</p><p>2º Como aprendi LinkedList (<a href="https://c137santos.medium.com/como-aprendi-linked-list-991bb146e84b">Medium</a>)</p><blockquote>“A verdadeira solução da recursão são os critérios de parada que encontramos pelo caminho”. Santos, 2024 . <a href="https://knowyourmeme.com/memes/maybe-the-real-treasure-was-the-friends-we-made-along-the-way?full=1">Referência</a></blockquote><p>No meu estudo de estrutura de dados na <a href="https://fatecsjc-prd.azurewebsites.net/">FATEC</a>, decide registrar meu jeitinho de aprender e pensar. Que é bem babysteps!</p><p>Tal qual uma lista encadeada, essa série construirá a cada medium um conteúdo importante e seu ponteiro para o next.</p><pre>struct medium {<br>    char textoMedium;<br>    struct medium* next;<br>}</pre><p>Tudo começou com Recursão! A explicação de Recursão é bem simples, mas a prática já não!</p><p>Recursão é a técnica de encontrar o caso mais simples de um problema, propor uma solução para resolve-lo diretamente, e usar desse resultado e dessa solução para lidar com os casos mais complexos subsequentes. .</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/754/1*FM2BhWifw4DshTGHWLQGMg.png" /><figcaption>“Entedendo algoritmos. Um guia ilustrado para programadores e outros curiosos.” Aditya Y. Bhargava</figcaption></figure><p>Se somar um número com o seu antecessor, no caso mais simples, 0 + 1, o resultado será 1. Esse processo de soma repetidamente o número atual com o anterior é o conceito básico por trás da sequência de Fibonacci.</p><p>A abordagem recursiva reflete exatamente essa ideia: a partir de um caso simples, repetindo o mesmo padrão ao longo da sequência, se obtem o resultado de um caso mais complexo. A literatura chama o “dividir para conquistar”</p><h3>Como estrururar uma recursão</h3><p>Procure os inputs mais simples para propor um algoritmo de solução. No caminho, você encontrar: o final do algoritmo e o caso base.</p><p>Normalmente aparecem nessa ordem, casos que indicam a finalização do problema e inputs mais simples para um caminho feliz. Com o caminho feliz, então, é possível desenvolver a solução direta, ou o caso base.</p><p>Então, eu divido em 3 passos:</p><p><em>a) O(s) resultado(s) que indica(m) o fim do problema. Também conhecido como critério de parada.</em></p><p><em>b) O input mais simples do caminho feliz</em></p><p><em>c) A solução mais direta aplicada ao input mais simples do caminho feliz. Também chamado de algoritmo base de resolução da recursão;</em></p><p>É buscando o input mais simples para o caminho feliz que você encontrará os critérios de parada.</p><p>O critério de parada de uma função recursiva pode indicar o fim por sucesso, por falha ou porque a função alcançou a solução via caso base (o menor caso). Mas eles são essenciais, ou você vai cair num loop eterno de desilusão.</p><blockquote>“A verdadeira solução da recursão são os critérios de parada que encontramos pelo caminho”. Santos, 2024 . <a href="https://knowyourmeme.com/memes/maybe-the-real-treasure-was-the-friends-we-made-along-the-way?full=1">Referência</a></blockquote><h4>Encontrando os critérios de parada em busca do caso base</h4><p>Vamos usar o problema do <a href="https://leetcode.com/problems/power-of-two/">LeetCode Power of Two</a>. Dado um número, você precisa saber se ele é potência de 2.</p><p>Buscando caminho feliz…</p><p>b.1) int 0. não é um caminho feliz de resolução. Zero não é potência de nada. Ele e os números negativos. Temos uma regra então! O 1º critério de parada indicativo, até mesmo de insucesso.</p><pre>if (n &lt;= 0) {<br>    return false;<br>}</pre><p>b.2) int 1. Não é um caminho feliz de resolução. Um já é potência de 2 sem qualquer operação. Temos outra regra então! O 2º critério de parada, que indica sucesso, pois, necessariamente 1 é potência de 2, inclusive de qualquer outro número!</p><pre>if (n==1){<br>  return true;<br>}</pre><p>b.2) int 2. É UM CAMINHO! Porque 2 é potência de 2 e precisaremos operar para chegar nele! O que nos permite buscar o 3º passo. O desenvolvimento do <em>algoritmo base de resolução.</em></p><p>Achamos o menor input para o caminho feliz e dois critério de parada!</p><h4>Proposta para caso base</h4><p>Como chegar em uma operação que demonstre que 2 é potência de 2? Existem algumas formas, por exemplo, verificar log de “n”! Mas eu quero uma recursão.</p><p>Então 2/2 = 1 e não sobra nada, pois que 2¹=2, sobrando nada!</p><p>Já sabendo que if(n==1){return true}; é um critério de parada identificado! Então temos a chave que, ao chegar em 1 em uma divisão por 2 que não sobrando nada, temos uma potencia de 2. n % 2 == 0. Caso contrário, já sabemos que o número não é potência de 2!</p><pre>if (n % 2 == 0 ){<br>  return true;<br>}</pre><p>Achamos a proposta de recursão! Eu vou verificar se N é divido por 2, restando 0 até chegar em 1, pois 2x2x2x2 sempre será potência…!</p><p>Portanto, vou chamar a própria função com a metáde de N. Estou promovendo operações antes da chamada da recursão (isso impacta que tipo de resultado e estratégia devemos adotar na estruturação)</p><p>Caso alguém saia dos conformes! Ou seja, contrarie nossas regras encontrada! Eu já nego como potência. Ele ser zero, menor que zero, ou a divisão por 2 der resto.</p><pre>bool isPowerOfTwo(int n) {<br>    bool response;<br>    if (n==1){<br>        return true;<br>    }<br>    if (n &lt;= 0 || n % 2 != 0) {<br>        return false;<br>    }<br>    response = isPowerOfTwo(n / 2);<br>    return response<br>    }</pre><p><strong>Testes de mesa</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/675/1*JINQx62M3GMixQAE18USLg.png" /><figcaption>Teste de mesa do caso onde ‘n’ é potência de 2.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/562/1*DnMD6COi7PTsTJV9kvsdvQ.png" /><figcaption>Teste de mesa do caso onde ’n’ não é potência de 2.</figcaption></figure><h3>Entrelinhas da recursão</h3><p><strong>Toda recursão é uma pilha</strong></p><p>Uma recursão é uma pilha de execução (call stack). Ao entender uma pilha de recursão, entendemos melhor a recursão e a iteração em cada etapa.</p><p>Call Stack — “Ao encontrar a invocação de uma função, o computador cria um novo espaço de trabalho, que contém todos os parâmetros e todas as variáveis locais da função. Esse espaço de trabalho é colocado na pilha de execução (por cima do espaço de trabalho que invocou a função) e a execução da função começa (confinada ao seu espaço de trabalho). Quando a execução da função termina, o seu espaço de trabalho é removido da pilha e descartado. O espaço de trabalho que estiver agora no topo da pilha é reativado e a execução é retomada do ponto em que havia sido interrompida”. (<a href="https://www.ime.usp.br/~pf/algoritmos/aulas/pilha.html">Pilha</a>, IME)</p><p>Portanto, ao desenvolver uma recursão, você compreende que a cada iteração, existe um novo espaço de memória atribuido, com todas aquelas variáveis e valores.</p><p>Ao começar a resolve-la, eu empilho coisas, e ao chegar no ápice, eu desempilho as soluções.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*KAk7lAHmjmrcxEQChM1K4g.png" /><figcaption>Na minha cabeça, uma pilha é torre de pisa, torta, pronta para cair. Onde a cabeça é a base.</figcaption></figure><p><strong>Onde ficam critérios de parada?</strong></p><p>Os critérios de parada em uma recursão geralmente devem vir antes da chamada recursiva. Isso evita loops infinitos, inputs inválidos para algoritmo de resolução base ou causar um estouro de pilha (stack overflow).</p><p><strong>Impacto da ordem das operações em funções recursivas</strong></p><p>A depender do local em que haja as operações são realizadas (antes ou após a chamada recursiva, ou até sem operação) afeta o resultado final da função e condicionam a estruturação da função.</p><p><strong>Recursão sem retorno</strong></p><p>Quando há recursão como a<strong> isPowerOfTwo(),</strong> que após o retorno da recursão não existe qualquer operação, não precisa se preocupar em voltar com esse valor, pois o valor da última operação da recursão é o resultado.</p><p>A função pode ser até mesmo void com printf! Porque o retorno não influencia.</p><pre>#include &lt;stdio.h&gt;<br><br>void isPowerOfTwo(int n) {<br>    if (n == 1) {    // Critério de parada: 1 é potência de 2<br>        printf(&quot;true\n&quot;);<br>        return;<br>    }<br>    if (n &lt;= 0 || n % 2 != 0) {  // Se n é negativo ou ímpar (exceto 1), não é potência de 2<br>        printf(&quot;false\n&quot;);<br>        return;<br>    }<br><br>    // Chamada recursiva com n dividido por 2<br>    isPowerOfTwo(n / 2);<br>}</pre><p><strong>Recursão com retorno — operação anterior a chamada</strong></p><p>Quando a operação ocorre antes da chamada recursiva, temos algo próximo a função acima, qual nem ao menos precisa de retorno. Pois o último retorno é direto.</p><p>Também podemos evitar a recursão, pois é o cenário ideal para uma estrutura iterativa (for, while), pois o valor é processado antes de fazer a chamada subsequente, e isso é ideal para for e while.</p><pre>#include &lt;stdio.h&gt;<br>#include &lt;stdbool.h&gt;<br><br>bool isPowerOfTwo(int n) {<br>    if (n &lt; 1) {  // Números menores que 1 não são potências de 2<br>        return false;<br>    }<br><br>    while (n &gt; 1) {<br>        if (n % 2 != 0) {  // Se o número não for divisível por 2, não é uma potência de 2<br>            return false;<br>        }<br>        n /= 2;  // Divide por 2 a cada passo<br>    }<br><br>    return true;  // Se chegarmos a 1, é uma potência de 2<br>}</pre><p><strong>Recursão com retorno — operação depois da chamada</strong></p><p>Quando existem operaçõs depois da chamada, já não é tão simples converter para um modo iterativo.</p><p>Converter uma função recursiva, especialmente aquelas em que a operação ocorre <strong>após</strong> a chamada recursiva, para uma versão iterativa, é um desafio porque envolve a simulação da “subida” e “descida” da <strong>pilha de chamadas.</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/744/1*_fRlBxWSj0bPZgS0H3Bmkw.png" /><figcaption>Faço o que com esse 1 agora meu deus?</figcaption></figure><p>Quando a operação é feita após a chamada recursiva, isso quer dizer que função depende do <strong>resultado da chamada recursiva</strong> para concluir sua operação. Sem o resultado da recursão, a função não pode completar a tarefa. Logo, ela nunca será void, exceto se trabalhar com reatribuição de ponteiros.</p><p>Eu gosto muito desse problema de imprimir todos os itens de uma lista de forma crescente depois decescente. Pois apresenta o comportamento de um empilhamento e desempilhamento conforme a posição da operação na chamada recursiva.</p><p>Vou fazer com python, visto que, o próximo medium que irá abordar a lista encadeada e a recurvidade. Então desenvolver uma lista encadeada do nada pode ser bem confuso devida tanta notação diferente sem qualquer explicação, desmotivador.</p><pre>def podio(lista):<br>    if len(lista) &gt; 0:<br>        print(lista[0])<br>        podio(lista[1:])<br>        print(lista[0])<br>    else:<br>        return<br><br>def main():<br>    lista = [1, 2, 3, 4]<br>    podio(lista)<br><br>if __name__ == &quot;__main__&quot;:<br>    main()<br>prints:<br>1<br>2<br>3<br>4<br>4<br>3<br>2<br>1</pre><p>Pois é gente, não tem como ser mais clara que isso. Espero que curtam o tema da recursão.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=ae12e6b1ea5e" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Flaskano com MongoDB]]></title>
            <link>https://c137santos.medium.com/flaskano-com-mongodb-8fbaed488cf3?source=rss-a4d176dcd2e6------2</link>
            <guid isPermaLink="false">https://medium.com/p/8fbaed488cf3</guid>
            <category><![CDATA[api]]></category>
            <category><![CDATA[mongodb]]></category>
            <category><![CDATA[flask-restful]]></category>
            <category><![CDATA[flask]]></category>
            <category><![CDATA[flask-framework]]></category>
            <dc:creator><![CDATA[Santos]]></dc:creator>
            <pubDate>Sat, 09 Dec 2023 13:01:32 GMT</pubDate>
            <atom:updated>2023-12-11T21:14:25.704Z</atom:updated>
            <content:encoded><![CDATA[<p>O mais importante é nunca parar de aprender! Flask e o MongoDB.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*Avy7JIPodTH_XP5s" /></figure><p><em>Thanks bing! Que a força esteja com você</em>!</p><p>Meu <a href="https://github.com/c137santos/starwars_api">projetinho de estudo</a> teve como base desenvolver uma API de StarWars! Créditos para o bing que fez a imagem e o GPT que me ajudou com Readme alá Lucas Filmes.</p><p>MongoDB — muito utilizado para quem quer provar um MVP (isso não quer dizer que não existam empresas sérias e estruturadas utilizem esse tipo de Banco NoSQL. É organizado em documentos JSON e BSON.</p><p>O Flask é um microframework python também conhecido por sua simplicidade e flexibilidade. Podemos até encarar Flask como uma boa escadinha para o Django.</p><h3>API: Astromech’s Protocol Interstellar</h3><p>Essa API consultará planetas e filmes da franquia.</p><p><strong>Arquitetura:</strong></p><p>Estruturado em três camadas principais.</p><ul><li>Serve.py: onde residem as views, as validações com pydantic e o estabelecimento do contrato da APIRest com seus paths e seus métodos adequados.</li><li>service.py: estabelece as regras de negócios e a conexão com banco de dados, realizando as operações no DB.</li><li>models: onde ficam basesmodels que, em sua maioria, dão uma controlada no mongoDB.</li><li>db.py: constituído de uma monoclasse que configura o acesso ao DB. Inclusive, assunto para próximo tópico.</li><li>Pasta de testes com conftest, test para o service e para cada um dos server.</li><li>O requirements.txt e o requirements-dev.txt serve para separar as dependência de desenvolvimento e de produção.</li><li>Usei simplemente o black e o ruff para formatar o text. Isso é suficiente.</li><li>Para me nortear sobre cobertura de teste, <a href="https://coverage.readthedocs.io/en/7.3.2/">coverage</a>!</li></ul><p><strong>Docker</strong></p><p>Não quero me aprofundar nisso, pois a ideia aqui é busca pessoas iniciantes, e acaba que docker pode assustar um pouco, porém, você deve saber que, o <a href="https://github.com/c137santos/starwars_api/blob/main/docker-compose.yml">docker-compose.yml</a>, aponta três serviços (db, flask_app, nginx) e como eles se relacionam entre si.</p><p>Usa a imagem mais recente do MongoDB. Separa o conteiner de teste do de produção, qual só será executado quando necessário rodar os teste. nginx que será construído a partir do diretório ./nginx. Reinicia sempre e depende do serviço flask_app.Essas configurações são úteis para criar um ambiente de desenvolvimento ou teste para uma aplicação Flask com um banco de dados MongoDB, onde o Nginx atua como um servidor proxy para a aplicação Flask.</p><p><strong>Conectando com o MongoDBConnection:</strong></p><p>Primeiro dos primeiros passo É conectar seu sistema ao banco de dados. Esse sempre recomendável como passo inicial! No arquivo <a href="https://github.com/c137santos/starwars_api/blob/main/flask_app/app/db.py">DB</a>.py organizei uma forma de conexão por meio de uma classe.</p><p>O class MongoDBConnection é um wrapper (que significa invólucro). Ela poderá ser instanciada toda vez que eu precisar de uma conexão com o banco, algo responsável pelo seu método get_client!</p><p>Nas primeiras linhas do arquivo, eu defino as constantes. Tratam do login, usuário, host, porta usada para conexão, a senha e o nome do banco! Onde serão as variáveis definidas no env, em caso de ausência, serão definidas as default.</p><pre># MongoDB connection setup<br>class MongoDBConnection:<br>    client = None<br>    <br>    @classmethod<br>    def get_client(cls):<br>        if cls.client is None:<br>            cls.client = MongoClient(<br>                host=MONGODB_HOST,<br>                port=MONGODB_PORT,<br>                username=MONGODB_USER,<br>                password=MONGODB_PASS,<br>                authSource=&quot;admin&quot;,<br>            )<br>        return cls.client</pre><p>@ classmethod é um método associados à classe em vez de uma instância específica da classe, ou seja, se houver uma modificação do get_client ou de suas variáveis, isso vai ser modificado em todos os lugares que essa classe foi instaciada!</p><p>Ter feito dessa forma garante que só exista uma conexão com banco de dados por vez. Acredite em mim, você não quer mais de uma conexão.</p><p><strong>1ª Estruturando o Banco: Desnormalizando para normalizar.</strong></p><p>Se tratando de um banco MongoDB, precisei tomar algumas decisão: Qual dados importantes há em cada um dos documentos que precisa aparecer no outro? Ou seja, quais informações de Planetas precisa aparecer em filmes e filmes em planetas.</p><p>Essa desnormalização se dá por conta do carater NoSQL do MongoDB.</p><p>Descobri que dá para fazer relações com o MongoEngine! Um Object-Document Mapper (ODM) que permite que você defina relações entre documentos usando referências/incorporando documentos uns nos outros, mas não realiza joins da mesma forma que um banco de dados relacional. Afinal, se você realmente quer joins, considere o PostgreSQL!</p><p>Porém, escolhi que eu deveria adicionar uma lista de nome de planetas nos filmes e a lista de filmes em planetas, apenas nomes.</p><p>a) Porque não vejo ninguem deletando um filme ou um planeta</p><p>b) Porque posso apresentar algo para meu cliente validar ou reprovar, e isso vai demandar um trabalho mais inteligente, um MVP real.</p><p><strong>2º o MongoDB é super liberal!</strong></p><p>Aqui não tem trava de segurança baby, você salvando uma linha contando “title, episode_id, director, producer, release_date, planets” em um Collection (Collection corresponde a tabela) vamos ter:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/984/1*L6rV9LnokANj46-DEs8kWg.png" /></figure><p>Porém, se logo em seguida vc salvar na mesma Collection “batatinha, clarinha, python” com respectivos valores. ELE DEIXA !</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*h0oP1hHztxFa8av1Br0ZkA.png" /></figure><p>Para lidar com esse problema, criei uma camada de <a href="https://github.com/c137santos/starwars_api/blob/main/flask_app/app/models.py">models</a>.py com pydantic para o BaseModel.</p><p>Assim, os BaseModel validarão a entrada que será salva no banco de dados em cada endpoint!</p><p>Por exemplo, quando uso o endpoint de salvar um planeta, o body do Request deve corresponder aos padrões e informações esperados pelo models PlanetCreated, determinado pelo spec.validate</p><pre>spec = FlaskPydanticSpec(<br>    &quot;flask&quot;, title=&quot;API: Astromech&#39;s Protocol Interstellar&quot;, version=&quot;v1&quot;<br>)<br>spec.register(app)<br>@app.post(&quot;/planets&quot;)<br>@spec.validate(body=Request(PlanetCreated), resp=Response(HTTP_201=Message))<br>def create_planet():<br>...</pre><p>O FlaskPydantic<a href="https://pypi.org/project/flask-pydantic-spec/">Spec</a> é uma Lib bem mágica, ela auxilia adicionar documentação no formato OpenAPI e também promove validações do request usando pydantic.</p><p>Portanto, esse @spec.validate é a instância que aplica o pydantic PlanetCreated ao body! Só autoriza requisições no formato adequado para a Collection de planetas possam ser salva.</p><p>E existe um model para todos os endpoints com objetivo controlar toda essa flexibilidade.</p><h4>CRUD — CRUz creDo</h4><p>Tanto em filme, quanto para planeta, apliquei a mesma lógica.</p><p>Foi criado uma classe composta só de staticmethod, isso quer dizer que tem a finalidade muito mais de agrupar toda lógica em um lugar, do que um motivo real para se usar uma classe e não funções normais!</p><p>A classe contém staticmethod para cada letra do CRUD. A operação no DB é acionada pela classe MongoDBConnection (que encapsula a conexão com o banco) da collection especificada (que é atributo dessa instância), seguida método do driver Python do MongoDB para realizar uma operação de inserção de um único documento.</p><p><em>Create</em></p><p><em>MongoDBConnection.films().</em><strong><em>insert_one</em></strong><em>(film_data).inserted_id</em> <strong>-&gt; </strong>Estabaleceu conexão com banco, na collection films acionando a método de <strong>inserir</strong> um único filme e retornar o id.</p><p><em>Update</em></p><p>O método utilizado foi o update_one, com o operador $set.O operador atualiza ou adiciona campos específicos em um documento existente, sem afetar outros campos que não estão incluídos na operação.</p><p>O campo chamado “last_updated” é definido com um valor de datetime gerado pelo método now_str() que eu formatei ele lá no models! Por que eu queria um padrão de data certinho pro banco.</p><pre>def now_str() -&gt; str:<br> return datetime.now().strftime(&quot;%Y-%m-%d %H:%M:%S&quot;)</pre><p><em>Read</em></p><p>Talvez a parte mais diferentona do CRUD foi fazer o filtro. O filtrar tem como base o método find a partir do dicionário construído pelas opções chamadofilter_query.</p><p>Foi necessário usar o operador $regex como expressão regular para compatibilizar o buscado e o que está no banco.</p><p>Como parâmetros de entrada, tudo é opcional! Ou seja, dicionário vazio como query de consulta traz todos os documentos do banco. Porém, ela também pode filtrar por title, director, order_by, page, page_size, planet.</p><p>Todos são <a href="https://www.mongodb.com/docs/manual/reference/operator/query/regex/#std-label-regex-case-insensitive">caseinsessitive</a>, porque adicionei ao filter_query o parâmetro “$options”: “i”. Além disso, para melhor performace, utilize o sort, skip e o limit, e eu quero detalhar isso aqui para vocês!</p><pre>return list(<br>    MongoDBConnection.films()<br>    .find(filter_query)<br>    .sort(order_by, d)<br>    .skip(skip)<br>    .limit(page_size)<br>)</pre><p>O find é comando do mongoDB que executa query no banco usando os filtros fornecidos pelo nosso dicionário construído filter_query.</p><p><em>sort</em></p><p>Método .sort(order_by, d) ordena os resultados de uma consulta. O parâmetro order_by especifica a coluna pela qual você deseja ordenar (por default é episode_id), e por padrão, a ordenação é feita em ordem crescente,devido ao ‘d’.</p><p>Se houver um um hífen ou um sinal de menos (&quot;-&quot;) no parâmetro de ordenação, esse servirá para inverter o d, que significa a direção da ordenação, sendo 1 para ordem crescente e -1 para ordem decrescente.</p><pre>      d = 1<br>      if order_by[0] == &quot;-&quot;:<br>          order_by = order_by[1:]<br>          d = -1</pre><p>O caso, ordenado, portanto:</p><pre>.sort(&quot;episode_id&quot;, 1)</pre><p>O caso descrescente, portanto:</p><pre>.sort(&quot;episode_id&quot;, -1)</pre><p>Em resumo, .sort(order_by, d) permite personalizar a ordenação dos resultados da consulta no MongoDB, sendo order_by a coluna de referência e d a direção (1 para crescente, -1 para decrescente).</p><p>POIS É, MAS! Trazer tudo tudo que há no banco não seja uma excelente ideia! Por isso usei paginação.</p><p><em>Página</em>:</p><p>O que é página? É sua melhor amiga! Página é simplesmente uma forma de quebrar o envio de dados da sua API em partezinhas menores, nesse caso a primeira página contará com 10 documentos por vez (page_size). Mas se você for atras da página dois, isso vai te enviar os 11–20 primeiros docs.</p><p>Não é legal mandar um arroba de dados você lesmará sua API.</p><pre><br>    @staticmethod<br>    def list(<br>        title: Optional[str] = None,<br>        director: Optional[str] = None,<br>        order_by: str = &quot;episode_id&quot;,<br>        page: int = 1,<br>        page_size: int = 10,<br>    ) -&gt; List[dict]:</pre><p>A lógica do page_size está baseada no skip. Esse serve para pular os dados que já foram indexados em uma página. Por exemplo, na primeira página você usa 10 primeiros documentos para enviar, e na segunda, você não quer repetir esses 10 primeiros documentos já enviados, então ele skipa os 10 primeiros e manda os 11 a 20!</p><p>Aqui a primeira página sempre vai ter o skip zero. Afinal: skip = (page — 1) * page_size -&gt; skip = (0 -1) * 0 -&gt; 0.</p><p><em>Delete</em></p><p>Delete sem mistério, aciona delete_one do mondoDB! MongoDB retorna um objeto do tipo DeleteResult que contém informações sobre a operação de exclusão, caso o len desse retorno seja zero, algo não foi deletado e uma excessão será lançada.</p><p><em>Retorno</em></p><p>Os resultados da consulta são convertidos em uma lista de dicionários (cada dicionário representa um filme) e são retornados.</p><p>Para padronizar o tipo de data que eu quero que retorne da minha API, criei uma classe que herda do DefaulJsonProvider e que, se encontra algo do tipo data, ele aplica o strtime escolhido.</p><pre>class MongoJsonProvider(DefaultJSONProvider):<br>    def default(self, obj):<br>        if isinstance(obj, datetime):<br>            return obj.strftime(&quot;%Y-%m-%d %H:%M:%S&quot;)<br>        if isinstance(obj, ObjectId):<br>            return str(obj)<br>        return super().default(obj)</pre><p>Utilizei o jsonify que é do próprio Flask para os retornos. Geralmente eu usava o json.dumps, um recurso da biblioteca Json que converter objetos python em data do tipo JSON, inclusive dicionários e listas.</p><p>Como eu desejava enviar dados em uma estrutura de HTTP, a melhor opção foi o flask.jsonify(), pois ele retorna um objeto do tipo Response, ou seja, colocando no formato JSON e adicionando os dados apropriados, tipo o headers!</p><p>Bem gente, não tinha como ser mais Clara que isso!</p><p>Espero ter ajudado com essa descrição de um CRUD básico e simples de uma API mongoDB utilizando Flask!</p><p>Aceito e adoro sugestões, correções, brigas, devaneios!</p><p>Referências</p><ul><li>API REST — <a href="https://www.youtube.com/live/1_nQ5A2HcgU?si=DV9PQ2LDCE2h-zbX">Live de Python #175</a></li><li>MongoDB — <a href="https://www.youtube.com/live/gOTMudRsf6A?si=0wMXYMUB8Mysljgm">Live de Python #174</a></li><li><a href="https://www.mongodb.com/languages/python">Documentação do MongoDb</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=8fbaed488cf3" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>