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.
<h2>O que é ordenação por inserção?</h2>
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.
É um algoritmo adaptativo, o que significa que é eficiente para pequenos conjuntos de dados, assim como outros algoritmos de complexidade quadrática (<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>O(n2)). É 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.
<h2>Como a ordenação por inserção funciona?</h2>
<ol>
<li>Inicialização: 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;
</li>
<li>Iteração: 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);
</li>
<li>Inserção: 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;
</li>
<li>Reposicionamento da Chave: 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.
</li>
<li>Repetir: O processo é repetido para todos os elementos da lista.
</li>
</ol>
<h2>Implementação em JavaScript</h2>
Para melhor entendermos o algoritmo, vamos implementá-lo em JavaScript:
<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>Melhor caso (Array já está ordenado): <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>O(n). Isso porque o laço interno (<code>while</code>) não é executado nenhuma vez;</li>
<li>Caso médio e pior caso (Array está ordenado de maneira reversa): <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>O(n2). 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>Complexidade de espaço: <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>O(1). ordenação por inserção é um algoritmo in-place; requer um valor constante de espaço na memória.</li>
</ul>

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

<h2>O que é um algoritmo?</h2>
Um algoritmo é uma especificação precisa e sem ambiguidades de uma sequência de passos computacionais que podem ser realizados mecanicamente[^1]. A partir disso, podemos pensar em uma função que recebe um valor ou um conjunto de valores de entrada e retorna um valor ou conjunto de valores em sua saída.
Um algoritmo pode ser correto e incorreto. Ele é correto quando, dados seus parâmetros de entrada, sua saída for correta e, portanto, resolve o problema computacional para qual foi desenvolvido. Um algoritmo incorreto, por sua vez, pode parar com uma saída incorreta ou mesmo não parar para algumas instâncias de entrada. Ainda assim, alguns algoritmos incorretos ainda podem ter aplicações úteis.
Podem haver diferentes algoritmos que resolvem um mesmo problema, alguns mais eficientes, isto é, mais velozes do que outros. Mas, nem todo problema possui uma solução eficiente. Tais problemas são conhecidos como <abbr title="Tempo polinomial não-determinístico">NP</abbr>-completos.
Problemas <abbr title="Tempo polinomial não-determinístico">NP</abbr>-completos são muito interessantes: mesmo que nenhum algoritmo eficiente tenha sido encontrado para esta classe de problemas, não se provou que que não é possível encontrar um algoritmo eficiente (da classe P, que pode ser resolvido em tempo polinomial) para tal problema. Além disso, se houver um algoritmo eficiente para resolver um problema NP-completo, significa que existe um algoritmo eficiente para todos os problemas <abbr title="tempo polinomial não-determinístico">NP</abbr>-completos.
<Alert title="P vs. NP">
P vs. NP é uma questão fundamental em ciência da computação, especificamente no campo da teoria da complexidade computacional. Ela diz respeito à relação entre duas classes de problemas. A classe P consiste em problemas de decisão (problemas com resposta sim ou não) que podem ser resolvidos rapidamente (em tempo polinomial) por um computador determinístico, o que significa que o tempo necessário para resolver o problema cresce a uma taxa gerenciável à medida que o tamanho da entrada aumenta. Por outro lado, a classe NP consiste em problemas de decisão para os quais, se uma solução for fornecida, ela pode ser verificada rapidamente (também em tempo polinomial) por um computador determinístico.

A questão crucial, &quot;P é igual a NP?&quot;, pergunta se todo problema cuja solução pode ser verificada rapidamente (NP) também pode ser resolvido rapidamente (P). Isso é profundo porque, se P fosse igual a NP, significaria que todos os problemas que podemos verificar rapidamente também podem ser resolvidos rapidamente. Isso tem implicações vastas para vários campos, incluindo criptografia, otimização e design de algoritmos.
</Alert>
<h2>Complexidade de algoritmos</h2>
Quando falamos de algoritmos, na maior parte do tempo estamos interessados na taxa de crescimento de tempo e espaço requeridos para resolver instâncias cada vez maiores de determinados problemas. Se estamos interessados no tempo que determinado algoritmo leva para executar sua função, estamos interessados um sua complexidade temporal. E o comportamento do limite da complexidade temporal do nosso algoritmo em relação ao aumento das instâncias do problema é chamado de complexidade assintótica temporal. E é esse complexidade assintótica que que determina o tamanho do problema que pode ser resolvido por algoritmos[^2].
Se um algoritmo leva um tempo <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>c</mi><msup><mi>n</mi><mn>2</mn></msup></mrow><annotation encoding="application/x-tex">cn^2</annotation></semantics></math>cn2 para uma constante <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>c</mi></mrow><annotation encoding="application/x-tex">c</annotation></semantics></math>c para processar um entrada de tamanho <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math>n, dizemos que a complexidade do algoritmo é da ordem de <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mi>n</mi><mn>2</mn></msup></mrow><annotation encoding="application/x-tex">n^2</annotation></semantics></math>n2, ou, em notação Bachmann–Landau (também chamada de notação assintótica e notação Big O), o algoritmo tem a complexidade <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>O(n2).
Para termos uma melhor ideia do que isso significa em relação ao tempo de execução do nosso algoritmo, considere que uma unidade de tempo no computador em que executamos o nosso algoritmo é de 1 milissegundo. Agora, queremos saber qual o tamanho máximo da entrada que o nosso algoritmo pode processar dentro de um determinado limite de tempo (um segundo, um hora e um dia). Observe, na tabela abaixo, o quanto a complexidade do algoritmo interfere no tamanho máximo da entrada que ele pode tratar, dado o limite de tempo:
<table>
<thead>
<tr>
<th>Complexidade de tempo</th>
<th>1 segundo</th>
<th>1 minuto</th>
<th>1 hora</th>
</tr>
</thead>
<tbody><tr>
<td><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math>n</td>
<td>1000</td>
<td>60000</td>
<td>360000</td>
</tr>
<tr>
<td><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi><msub><mrow><mi>log</mi><mo>⁡</mo></mrow><mn>2</mn></msub><mi>n</mi></mrow><annotation encoding="application/x-tex">n \log_2 n</annotation></semantics></math>nlog2​n</td>
<td>140</td>
<td>4895</td>
<td>204095</td>
</tr>
<tr>
<td><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mi>n</mi><mn>2</mn></msup></mrow><annotation encoding="application/x-tex">n^2</annotation></semantics></math>n2</td>
<td>31</td>
<td>244</td>
<td>1897</td>
</tr>
<tr>
<td><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mi>n</mi><mn>3</mn></msup></mrow><annotation encoding="application/x-tex">n^3</annotation></semantics></math>n3</td>
<td>10</td>
<td>39</td>
<td>153</td>
</tr>
<tr>
<td><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mn>2</mn><mi>n</mi></msup></mrow><annotation encoding="application/x-tex">2^n</annotation></semantics></math>2n</td>
<td>9</td>
<td>15</td>
<td>21</td>
</tr>
</tbody></table>
Ainda que possamos construir computadores mais rápidos, o aumento na velocidade de execução dos algoritmos menos eficientes não seria tão significativo, de modo que que devemos buscar sempre o algoritmo de melhor eficiência para tratar determinado problema.
[^1]: AHO, Alfred V.; ULLMAN, Jeffrey D. Foundations of Computer Science. Stanford, 1994.
[^2]: AHO, Alfred V.; HOPCROFT, John E.; ULLMAN, Jeffrey D. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974.

Douglas Moura

Douglas Moura

#Ciência da Computação

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

Introdução à algoritmos