Sorting is a fundamental operation in the field of computer science, and because of this, there are various algorithms available to solve this problem. Each one is chosen based on factors such as the number of items to sort, the degree of order already present, the computer architecture where the algorithm will be executed, the type of storage device, among others. In this article, we will explore the insertion sort algorithm, understanding its nuances, strengths, and limitations.
<h2>What is insertion sort?</h2>
Insertion sort is a comparison-based algorithm that constructs its output one element at a time. It works similarly to the method we use to sort a deck of cards: we take one card at a time, compare it with the ones we already have in our hand, place the card in the correct position, and repeat this action until we finish our deck.
It is an adaptive algorithm, meaning it is efficient for small data sets, as well as other quadratic complexity algorithms (<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)). It is simple to implement, requires a constant amount of memory, as changes in the list are made in the list itself (without the need to create a new list, which would double the use of memory), and is capable of sorting the list as it receives it.
<h2>How does insertion sort work?</h2>
Initialization: We assume that the first element of our list is already sorted. We proceed to the next element, consider it as our key, and insert it in the correct position in the sorted part of the list;
Iteration: For each item in the list (starting from the second element), we store the current item (key) and its position. Then we compare the key with the elements in the sorted part of the list (elements before the key);
Insertion: If the current element in the sorted part is greater than the key, we move that element one position up. This creates space for the new key to be inserted;
Repositioning the Key: We continue moving elements one position up until we find the correct position for the key. This position is found when we encounter an element that is less than or equal to the key or when we reach the beginning of the list;
Repeat: The process is repeated for all the elements in the list.
<h2>Implementation in JavaScript</h2>
To better understand the algorithm, let&#39;s implement it in JavaScript:
<pre><code class="highlited-code-wrapper langjs"><div class="highlited-code" data-language="js">/**
* Sorts an array of numbers using the insertion sort algorithm.
* 
* @param {number[]} numbers - The list of numbers to be sorted.
* @returns {number[]} - The sorted list of numbers.
*/
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>Complexity Analysis</h2>
<h3>Time Complexity</h3>
Best Case (Array is already sorted): <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). This is because the inner loop (while) is not executed at all;
Average Case and Worst Case (Array is sorted in reverse order): <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). In the worst case, each iteration will cause an element to be moved. This makes the algorithm inefficient for large data sets.
<h2>Space Complexity</h2>
Space Complexity: <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). Insertion sort is an in-place algorithm; it requires a constant amount of memory space.

Mastering Insertion Sort: A Detailed Guide

Using custom dialog elements instead of native browser implementations, such as <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>, or <a href="https://developer.mozilla.org/en-US/docs/Web/API/Window/prompt"><code>prompt</code></a>,
has become the standard for web development for quite some time (popularized by various <a href="https://jqueryui.com/dialog/">jQuery</a> plugins and by <a href="https://getbootstrap.com/2.3.2/javascript.html#modals">Bootstrap</a> itself), so that with every new UI library that emerges[^1][^2][^3], it is common for its authors to re-implement a modal with the framework of the moment (which may or may not implement <a href="https://www.w3.org/WAI/ARIA/apg/patterns/dialog-modal/">WAI-ARIA accessibility</a>).
[^1]: <a href="https://mui.com/material-ui/react-modal/">Material UI Modal</a>
[^2]: <a href="https://ant.design/components/modal">Ant Design Modal</a>
[^3]: <a href="https://carbondesignsystem.com/components/modal/usage/#live-demo">Carbon Design System Modal</a>
But now, with the arrival of the <a href="https://developer.mozilla.org/en-US/docs/Web/HTML/Element/dialog"><code>&lt;dialog&gt;</code></a> element in HTML5 (supported by <a href="https://caniuse.com/dialog">93.85%</a> of browsers in use), it is much easier to create dialogs natively. In this article, we will see how to create a simple modal (and non-modal) dialog with the <code>&lt;dialog&gt;</code> element.
<h2>Understanding the dialog element</h2>
In the sense employed in user interface development, a dialog is a <q>conversation</q> between the system and the user, where the system expects a response from the user to continue. A dialog can be modal or non-modal. A modal dialog (that is, one that changes the mode of interaction of the user with the system) is one that locks the interface, preventing the user from interacting with the rest of the page until it is closed. A non-modal dialog (that is, one that does not change the mode of interaction of the user with the system), on the other hand, allows the user to interact with the rest of the page while the dialog is open.
The simplest way to put a non-modal dialog on the screen is as follows:
<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>Note the form, on line 5, with the dialog method. It is this form that sends actions to the <code>dialog</code>. It will be displayed like this:
<CodePen id="zYMgBOz" />

What makes the example above a non-modal dialog is the use of the <code>open</code> attribute (line 1), which also makes it unable to be closed with the <code>Esc</code> key. It&#39;s possible to create a non-modal dialog using the JavaScript API:
<CodePen id="BaGXqjx" />

In order for it to behave like a modal, it is necessary to open it through its JavaScript API, as we will see next.
<CodePen id="VwVojZB" />

This time, we open and close the modal with JavaScript and put the form result in the <code>output</code> element when the modal is closed. Read the code carefully and try to understand what is happening.
<h2>Styling the modal</h2>
The <code>dialog</code> element can (of course), be styled like any other HTML element. However, note that, to style the overlay (the dark background behind the modal), it is necessary to use the <code>::backdrop</code> selector:
<CodePen id="gOQVMYE" />

<h2>Polyfill</h2>
If you want to use <code>dialog</code> and don&#39;t have compatibility issues in older browsers, you can use this <a href="https://github.com/GoogleChrome/dialog-polyfill">polyfill</a>.
<hr />

<h3>References</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>

Creating native modals with the dialog element

Have you ever faced the situation where the layout of your beautifully crafted interface &quot;breaks&quot; if the image (depeding on the quality of your user&#39;s connections) takes some time to load? Something like the example below:
<a href="https://media.giphy.com/media/Q7B0kOHlC7akJmwTCW/giphy.gif"><img src="https://media.giphy.com/media/Q7B0kOHlC7akJmwTCW/giphy.gif" /></a>
This happens because the browser has no clue about the dimensions of the image you want to display on your content beforehand.
The easiest way to solve this issue is using the <a href="https://developer.mozilla.org/en-US/docs/Web/CSS/aspect-ratio"><code>aspect-ratio</code></a> property to tell the browser how much space (based on the user&#39;s size display) it should reserve before the image is loaded. Check the difference:
<pre><code class="highlited-code-wrapper langcss"><div class="highlited-code" data-language="css">img {
/* Makes all images responsive */
 width: 100%;
 height: auto;

/*
 Here, I'm using the image's width and height,
 but you can come up with diference aspect ratios.
*/
 aspect-ratio: 760 / 235;
}</div>
</code></pre><a href="https://media.giphy.com/media/X4dBoFehuhSrpUIdIA/giphy.gif"><img src="https://media.giphy.com/media/X4dBoFehuhSrpUIdIA/giphy.gif" width="100%" /></a>
So, it solves the sudden layout change, but we can do even better do better adding an animated background.
<h2>Displaying an animated background</h2>
You can give a hint for the user that the blank space on your app should be filled with something by adding a background color or animating the transition between two o more colors, like in the example below:
<iframe height="300" style={{width:'100%'}} scrolling="no" title="Animated placeholder" src="https://codepen.io/douglasdemoura/embed/RwyWzEr?default-tab=" frameborder="no" loading="lazy" allowtransparency="true" allowfullscreen="true">
 See the Pen <a href="https://codepen.io/douglasdemoura/pen/RwyWzEr">
 Animated placeholder</a> by Douglas Moura (<a href="https://codepen.io/douglasdemoura">@douglasdemoura</a>)
 on <a href="https://codepen.io">CodePen</a>.
</iframe>

And our code will look like this:
<pre><code class="highlited-code-wrapper langcss"><div class="highlited-code" data-language="css">:root {
 /*
 Set the default aspect ratio. You can change
 this CSS variable per class/id or event
 creating diferente classes.
 */
 --aspect-ratio: 16/9;
}

img {
/* Makes all images responsive */
 width: 100%;
 height: auto;
}

/* Put all your images inside this container */
.image-container { 
 aspect-ratio: var(--aspect-ratio);
 position: relative;
 animation: background-loading .8s linear infinite alternate;
}

.image-container img {
 position: absolute;
 top: 0;
 left: 0;
}

/* The placeholder animation */
@keyframes background-loading {
 0% {
 background-color: #f9fafb;
 }
 100% {
 background-color: #d1d5db;
 }
}</div>
</code></pre>And this is the result (check the code on <a href="https://codepen.io/douglasdemoura/pen/RwyWBOR">CodePen</a>):
<img src="https://media.giphy.com/media/9yYPBL1X9wnAKzhVfE/giphy.gif" />

Yet, this can be even better by displaying a colorful background that matches the image colors.
<h2>Displaying colorful image placeholders</h2>
<a href="https://github.com/woltapp/blurhash">BlurHash</a> is a compact representation of a placeholder for a image. You use it to process your image before sending it to the browser and you&#39;ll get a string of 20-30 characters that the algorithm can turn into a blurred image that you can show to your user before the actual image is downloaded. Check how it looks like:
<img src="https://media.giphy.com/media/1RSpYFokgWI2tKRKHk/giphy.gif" />

I have implemented that last effect in React for the sake of simplicity and time, but you can re-implement it in whatever framework you like. Just pay attention to the <code>onLoad</code> event that changes the opacity of the image.
<iframe src="https://stackblitz.com/edit/vitejs-vite-enczef?embed=1&file=src/Image.module.css" height="500" style={{width: '100%'}} scrolling="no" title="Animated placeholder" frameborder="no" loading="lazy" allowtransparency="true" allowfullscreen="true"></iframe>

Douglas Moura

Douglas Moura

#tutorial

Mastering Insertion Sort: A Detailed Guide

Creating native modals with the dialog element

Create beautiful placeholders for your images