<p>Ordenação é uma operação fundamental no campo da ciência da computação e, por conta disso, existem vários algoritmos disponíveis para resolver este problema, cada um com sua aplicação determinada pela quantidade de itens a ordenar, o grau de ordenação já presente, a arquitetura do computador onde o algoritmo será executado, tipo de dispositivo de armazenamento, entre outros fatores. Neste artigo, exploraremos o algoritmo de ordenação por inserção, entendendo suas nuances, forças e limitações.</p>
<h2>O que é ordenação por inserção?</h2>
<p>Ordenação por inserção é um algoritmo baseado em comparação que constrói a sua saída um elemento por vez. Ele funciona de maneira análoga ao método que utilizamos para ordenar as cartas de um baralho: pegamos uma carta de cada vez, comparamos com os anteriores que já estão na nossa mão, colocamos a carta na posição correta e, repetimos esta ação até o fim do nosso baralho.</p>
<p>É um algoritmo adaptativo, o que significa que é eficiente para pequenos conjuntos de dados, assim como outros algoritmos de complexidade quadrática (<span class="katex-inline"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><msup><mi>n</mi><mn>2</mn></msup><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n^2)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1.0641em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord"><span class="mord mathnormal">n</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span></span></span></span></span><span class="mclose">)</span></span></span></span></span>). É simples de implementar, requer um valor constante de memória, pois as alterações na lista são feitas na própria lista (sem a necessidade de criar uma nova lista, o que dobraria o uso da memória) e é capaz de ordenar a lista enquanto a recebe.</p>
<h2>Como a ordenação por inserção funciona?</h2>
<ol>
<li><p><strong>Inicialização</strong>: Assumimos que o primeiro elemento da nossa lista já está ordenado. Prosseguimos para o próximo elemento, consideramos ele como nossa chave e o inserimos na posição correta na parte ordenada da lista;</p>
</li>
<li><p><strong>Iteração</strong>: Para cada item da lista (começando do segundo elemento), armazenamos o item atual (chave) e sua posição. Comparamos então a chave com os elementos na parte ordenada da lista (elementos antes da chave);</p>
</li>
<li><p><strong>Inserção</strong>: Se o elemento atual na parte ordenada for maior que a chave, movemos esse elemento uma posição acima. Isso cria espaço para a nova chave ser inserida;</p>
</li>
<li><p><strong>Reposicionamento da Chave</strong>: Continuamos movendo elementos uma posição acima até encontrarmos a posição correta para a chave. Esta posição é encontrada quando batemos em um elemento menor ou igual à chave ou alcançamos o início da lista.</p>
</li>
<li><p><strong>Repetir</strong>: O processo é repetido para todos os elementos da lista.</p>
</li>
</ol>
<h2>Implementação em JavaScript</h2>
<p>Para melhor entendermos o algoritmo, vamos implementá-lo em JavaScript:</p>
<pre><code class="highlited-code-wrapper langjs"><div class="highlited-code" data-language="js">/**
* Ordena um array de números usando o algoritmo de ordenação por inserção.
* 
* @param  {number[]}  numbers - A lista de números que deve ser ordenada.
* @returns  {number[]} - A lista de números ordenada.
*/
function insertionSort(numbers) {
  for (let i = 1; i &lt; numbers.length; i++) {
    const key = numbers[i]
    let j = i - 1
    
    while (j &gt;= 0 &amp;&amp; numbers[j] &gt; key) {
      numbers[j  +  1] =  numbers[j]
      j--
    }

    numbers[j  +  1] = key
  }
}</div>
</code></pre><h2>Análise da complexidade</h2>
<h3>Complexidade de tempo</h3>
<ul>
<li><strong>Melhor caso (Array já está ordenado)</strong>:  <span class="katex-inline"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span></span>. Isso porque o laço interno (<code>while</code>) não é executado nenhuma vez;</li>
<li><strong>Caso médio e pior caso (Array está ordenado de maneira reversa)</strong>: <span class="katex-inline"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><msup><mi>n</mi><mn>2</mn></msup><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n^2)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1.0641em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord"><span class="mord mathnormal">n</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span></span></span></span></span><span class="mclose">)</span></span></span></span></span>. No pior caso, cada iteração fará com que um elemento seja movido. Isso faz este algoritmo ser ineficiente para conjuntos grandes de dados.</li>
</ul>
<h3>Complexidade de espaço</h3>
<ul>
<li><strong>Complexidade de espaço</strong>: <span class="katex-inline"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(1)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord">1</span><span class="mclose">)</span></span></span></span></span>. ordenação por inserção é um algoritmo <em>in-place</em>; requer um valor constante de espaço na memória.</li>
</ul>


Dominando o algoritmo de ordenação por inserção: um guia detalhado

<p>Há algum tempo, o <a href="https://twitter.com/zanfranceschi">Zan Franceschi</a> postou o seguinte desafio:</p>
<Tweet id="1564671754483765251" />

<p>Neste artigo, vou resolvê-lo de duas formas: uma com laços e outra sem laços, com TypeScript.</p>
<h2>Analisando os dados</h2>
<p>Vou transcrever o JSON do desafio para facilitar a nossa análise:</p>
<pre><code class="highlited-code-wrapper langjson"><div class="highlited-code" data-language="json">{
  &quot;compras&quot;: [
    {
      &quot;data&quot;: &quot;2022-01-01&quot;,
      &quot;produtos&quot;: [
        {
          &quot;cod&quot;: &quot;a&quot;,
          &quot;qtd&quot;: 2,
          &quot;valor_unitario&quot;: 12.24
        },
        {
          &quot;cod&quot;: &quot;b&quot;,
          &quot;qtd&quot;: 1,
          &quot;valor_unitario&quot;: 3.99
        },
        {
          &quot;cod&quot;: &quot;c&quot;,
          &quot;qtd&quot;: 3,
          &quot;valor_unitario&quot;: 98.14
        }
      ]
    },
    {
      &quot;data&quot;: &quot;2022-01-02&quot;,
      &quot;produtos&quot;: [
        {
          &quot;cod&quot;: &quot;a&quot;,
          &quot;qtd&quot;: 6,
          &quot;valor_unitario&quot;: 12.34
        },
        {
          &quot;cod&quot;: &quot;b&quot;,
          &quot;qtd&quot;: 1,
          &quot;valor_unitario&quot;: 3.99
        },
        {
          &quot;cod&quot;: &quot;c&quot;,
          &quot;qtd&quot;: 1,
          &quot;valor_unitario&quot;: 34.02
        }
      ]
    }
  ]
}</div>
</code></pre><p>Podemos definir o JSON acima em dois tipos distintos: <code>Produto</code> e <code>Compra</code>. Seus nomes são autoexplicativos, mas vou defini-los aqui para facilitar a leitura do código:</p>
<pre><code class="highlited-code-wrapper langts"><div class="highlited-code" data-language="ts">type Produto = {
  cod: string
  qtd: number
  valor_unitario: number
}

type Compra = {
  data: string
  produtos: Produto[]
}</div>
</code></pre><h2>Escrevendo testes</h2>
<p>Antes de começar a escrever o código, vamos escrever alguns testes para garantir que o código está funcionando corretamente. Para isso, vamos usar o <a href="https://vitest.dev/">Vitest</a>.</p>
<pre><code class="highlited-code-wrapper langts"><div class="highlited-code" data-language="ts">import { describe, expect, test } from 'vitest'
import {
  somaComFor,
  somaComForIn,
  somaComForOf,
  somaComWhile,
  somaComForEach,
  somaComReduce,
  somaComFlatMapEReduce,
  somaComSum,
  somaComSumEFlatMap
} from './desafio-da-soma'

const { compras } = await import('./data.json', { with: { type: 'json' } })

const result = 434.93999999999994

describe('Desafio da soma', () =&gt; {
  test('somaComFor', () =&gt; {
    expect(somaComFor(compras)).toBe(result)
  })

  test('somaComForOf', () =&gt; {
    expect(somaComForOf(compras)).toBe(result)
  })

  test('somaComForIn', () =&gt; {
    expect(somaComForIn(compras)).toBe(result)
  })

  test('somaComWhile', () =&gt; {
    expect(somaComWhile(compras)).toBe(result)
  })

  test('somaComForEach', () =&gt; {
    expect(somaComForEach(compras)).toBe(result)
  })

  test('somaComReduce', () =&gt; {
    expect(somaComReduce(compras)).toBe(result)
  })

  test('somaComFlatMapEReduce', () =&gt; {
    expect(somaComFlatMapEReduce(compras)).toBe(result)
  })

  test('somaComSum', () =&gt; {
    expect(somaComSum(compras)).toBe(result)
  })

  test('somaComSumEFlatMap', () =&gt; {
    expect(somaComSumEFlatMap(compras)).toBe(result)
  })
})</div>
</code></pre><h2>Somando com laços</h2>
<p>Agora que já temos os tipos definidos, podemos começar a resolver o desafio. Podemos fazer isso de quatro formas:</p>
<h3>1. Usando <code>for</code></h3>
<p>O <a href="https://developer.mozilla.org/pt-BR/docs/Web/JavaScript/Reference/Statements/for"><code>for</code></a> é um <strong>laço de repetição</strong> que executa um bloco de código até que uma condição seja satisfeita.</p>
<pre><code class="highlited-code-wrapper langtypescript"><div class="highlited-code" data-language="typescript">function somaComFor(compras: Compra[]): number {
  let soma = 0

  for (let i = 0; i &lt; compras.length; i++) {
    for (let j = 0; j &lt; compras[i].produtos.length; j++) {
      soma += compras[i].produtos[j].qtd * compras[i].produtos[j].valor_unitario
    }
  }

  return soma
}</div>
</code></pre><h3>2. Usando <code>for...of</code></h3>
<p>O <a href="https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Statements/for...of"><code>for...of</code></a> é um <strong>laço de iteração</strong> que itera sobre uma sequência de valores vindos de um <a href="https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols#the_iterable_protocol">objeto iterável</a> (que, no nosso caso, é um <a href="https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array">Array</a>).</p>
<pre><code class="highlited-code-wrapper langtypescript"><div class="highlited-code" data-language="typescript">function somaComForOf(compras: Compra[]): number {
  let soma = 0

  for (const compra of compras) {
    for (const produto of compra.produtos) {
      soma += produto.qtd * produto.valor_unitario
    }
  }

  return soma
}</div>
</code></pre><h3>3. Usando <code>for...in</code></h3>
<p>O <a href="https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Statements/for...in"><code>for...in</code></a> é um <strong>laço de iteração</strong> que itera sobre as propriedades enumeráveis do tipo <em>string</em> de um objeto, inclusive as herdadas. Estou colocando esta solução aqui somente para mostrar que ela é possível, mas deve ser preterida em relação às outras soluções apresentadas neste artigo.</p>
<pre><code class="highlited-code-wrapper langtypescript"><div class="highlited-code" data-language="typescript">function somaComForIn(compras: Compra[]): number {
  let soma = 0

  for (const i in compras) {
    for (const j in compras[i].produtos) {
      soma += compras[i].produtos[j].qtd * compras[i].produtos[j].valor_unitario
    }
  }

  return soma
}</div>
</code></pre><h3>4. Usando <code>while</code></h3>
<p>O <a href="https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Statements/while"><code>while</code></a> é um <strong>laço de repetição</strong> que executa um bloco de código até que uma condição seja satisfeita.</p>
<pre><code class="highlited-code-wrapper langtypescript"><div class="highlited-code" data-language="typescript">function somaComWhile(compras: Compra[]): number {
  let soma = 0

  let i = 0
  while (i &lt; compras.length) {
    let j = 0
    while (j &lt; compras[i].produtos.length) {
      soma += compras[i].produtos[j].qtd * compras[i].produtos[j].valor_unitario
      j++
    }
    i++
  }

  return soma
}</div>
</code></pre><h2>Somando com métodos de <code>Array</code></h2>
<h3>1. Usando <code>Array.prototype.forEach</code></h3>
<p>O <a href="https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/forEach"><code>Array.prototype.forEach</code></a> é um método que executa uma função para cada elemento do array.</p>
<pre><code class="highlited-code-wrapper langtypescript"><div class="highlited-code" data-language="typescript">function somaComForEach(compras: Compra[]): number {
  let soma = 0

  compras.forEach(compra =&gt; {
    compra.produtos.forEach(produto =&gt; {
      soma += produto.qtd * produto.valor_unitario
    })
  })

  return soma
}</div>
</code></pre><h3>2. Usando <code>Array.prototype.reduce</code></h3>
<p>O <a href="https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/reduce"><code>Array.prototype.reduce</code></a> é um método que executa uma função para cada elemento do array, retornando um único valor.</p>
<pre><code class="highlited-code-wrapper langtypescript"><div class="highlited-code" data-language="typescript">function somaComReduce(compras: Compra[]): number {
  return compras.reduce((soma, compra) =&gt; {
    return (
      soma +
      compra.produtos.reduce((soma, produto) =&gt; {
        return soma + produto.qtd * produto.valor_unitario
      }, 0)
    )
  }, 0)
}</div>
</code></pre><p>Mas, podemos torná-la ainda melhor usando o <a href="https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/flatMap"><code>Array.prototype.flatMap</code></a>:</p>
<pre><code class="highlited-code-wrapper langtypescript"><div class="highlited-code" data-language="typescript">function somaComFlatMapEReduce(compras: Compra[]): number {
  return compras
    .flatMap(compra =&gt; compra.produtos)
    .reduce((soma, produto) =&gt; soma + produto.qtd * produto.valor_unitario, 0)
}</div>
</code></pre><h2>Com uma função de ajuda</h2>
<p>Podemos criar uma função genérica que faz a soma de qualquer array da seguinte forma:</p>
<pre><code class="highlited-code-wrapper langtypescript"><div class="highlited-code" data-language="typescript">/**
 * Soma todos os valores de um array. Se o array for de objetos, é possível
 * passar uma função para extrair os números que serão somados.
 *
 * @example soma([1, 2, 3]) // 6
 * @example soma([{ valor: 1 }, { valor: 2 }, { valor: 3 }], item =&gt; item.valor) // 6
 */
function sum&lt;T extends number | object&gt;(
  array: T[],
  fn?: (item: T) =&gt; number,
): number {
  return array.reduce(
    (acumulador, item) =&gt; acumulador + (fn ? fn(item) : (item as number)),
    0,
  )
}</div>
</code></pre><p>E usá-la em conjunto com as soluções já apresentadas:</p>
<pre><code class="highlited-code-wrapper langtypescript"><div class="highlited-code" data-language="typescript">function somaComSumEFlatMap(compras: Compra[]): number {
  return sum(
    compras.flatMap(compra =&gt; compra.produtos),
    produto =&gt; produto.qtd * produto.valor_unitario,
  )
}</div>
</code></pre><p>Se tiver alguma sugestão ou alguma outra ideia de como resolver este desafio, conta para mim nos comentários.</p>


Múltiplas formas de somar os valores de um array de objetos, em TypeScript

<p>Usar elementos customizados de diálogo no lugar das implementações nativas do navegador, como <a href="https://developer.mozilla.org/en-US/docs/Web/API/Window/alert"><code>alert</code></a>,
<a href="https://developer.mozilla.org/en-US/docs/Web/API/Window/confirm"><code>confirm</code></a> ou <a href="https://developer.mozilla.org/en-US/docs/Web/API/Window/prompt"><code>prompt</code></a>,
se tornou o padrão do desenvolvimento web há bastante tempo (popularizado por diversos plugins do <a href="https://jqueryui.com/dialog/">jQuery</a> e pelo próprio <a href="https://getbootstrap.com/2.3.2/javascript.html#modals">Bootstrap</a>), de modo que, a cada nova biblioteca de UI que surge[^1][^2][^3], é comum que seus autores re-implementem um modal com o framework da vez (que podem ou não implementar <a href="https://www.w3.org/WAI/ARIA/apg/patterns/dialog-modal/">acessibilidade WAI-ARIA</a>).</p>
<p>[^1]: <a href="https://mui.com/material-ui/react-modal/">Modal do Material UI</a>
[^2]: <a href="https://ant.design/components/modal">Modal do Ant Design</a>
[^3]: <a href="https://carbondesignsystem.com/components/modal/usage/#live-demo">Modal do Carbon Design System</a></p>
<p>Mas agora, com a chegada do elemento <a href="https://developer.mozilla.org/en-US/docs/Web/HTML/Element/dialog"><code>&lt;dialog&gt;</code></a> no HTML5 (suportado por <a href="https://caniuse.com/dialog">93,85%</a> dos navegadores em uso), é muito mais fácil criar diálogos de forma nativa. Neste artigo, vamos ver como criar um diálogo modal (e não-modal) simples com o elemento <code>&lt;dialog&gt;</code>.</p>
<h2>Entendendo o elemento <em>dialog</em></h2>
<p>No sentido empregado no desenvolvimento de interfaces de usuário, um <strong>diálogo</strong> é uma <q>conversação</q> entre o sistema e o usuário, onde o sistema espera uma resposta do usuário para continuar. Um diálogo pode ser <strong>modal</strong> ou <strong>não-modal</strong>. Um diálogo modal (isto é um, um diálogo que muda o <strong>modo</strong> de interação do usuário com o sistema) é aquele que trava a interface, impedindo o usuário de interagir com o restante da página até que ele seja fechado. Um diálogo não-modal (isto é um, um diálogo que <em>não</em> muda o <strong>modo</strong> de interação do usuário com o sistema), por outro lado, permite que o usuário interaja com o restante da página enquanto o diálogo está aberto.</p>
<p>A maneira mais simples de colocar um diálogo não-modal na tela é da seguinte forma:</p>
<pre><code class="highlited-code-wrapper langhtml"><div class="highlited-code" data-language="html">&lt;dialog open&gt;
  &lt;p&gt;Olá, mundo!&lt;/p&gt;
  &lt;form method=&quot;dialog&quot;&gt;
    &lt;button&gt;Fechar&lt;/button&gt;
  &lt;/form&gt;
&lt;/dialog&gt;</div>
</code></pre><p>Note o formulário, na linha 5, com o método <em>dialog</em>. É este formulário que envia ações para o <code>dialog</code>. Ele será exibido dessa forma:</p>
<CodePen id="qBQzzww" />

<p>O que torna o exemplo acima um diálogo não modal é o uso do atributo <code>open</code> (linha 1), o que também faz com que ele não possa ser fechado com a tecla <code>Esc</code>. Também é possível criar um diálogo não modal usando a API JavaScript:</p>
<CodePen id="BaGXqjx" />

<p>Agora, para que o diálogo se comporte como um modal, é necessário que ele seja aberto através de sua API JavaScript, você pode ver no exemplo a seguir:</p>
<CodePen id="ZEmdgYj" />

<p>Desta vez, abrimos e fechamos o modal com JavaScript e colocamos o resultado do formulário no elemento <code>output</code> quando o modal é fechado. Leia o código com calma e tente entender o que está acontecendo.</p>
<h2>Estilizando o modal</h2>
<p>O elemento <code>dialog</code> pode (é claro), ser estilizado como qualquer outro elemento HTML. Atente-se, porém, que, para estilizar o <em>overlay</em> (o fundo escuro que fica atrás do modal), é necessário usar o seletor <code>::backdrop</code>:</p>
<CodePen id="PoxrMzW" />

<h2>Polyfill</h2>
<p>Se você quiser usar o <code>dialog</code> e não ter problemas de compatibilidade em navegadores mais antigos, pode usar este <a href="https://github.com/GoogleChrome/dialog-polyfill">polyfill</a>.</p>
<hr />

<h3>Referências</h3>

<ul>
<li><a href="https://web.dev/learn/html/dialog/">Dialog</a></li>
<li><a href="https://developer.mozilla.org/en-US/docs/Web/HTML/Element/dialog">Dialog</a></li>
<li><a href="https://www.nngroup.com/articles/modal-nonmodal-dialog/">Modal &amp; Nonmodal Dialogs: When (&amp; When Not) to Use Them</a></li>
</ul>


Douglas Moura

Douglas Moura

#tutorial

Dominando o algoritmo de ordenação por inserção: um guia detalhado

Múltiplas formas de somar os valores de um array de objetos, em TypeScript

Criando modais nativos com o elemento dialog