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.

What is insertion sort?

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 ($O(n^2)$). 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.

How does insertion sort work?

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.

Implementation in JavaScript

To better understand the algorithm, let’s implement it in JavaScript:

/**
* 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 < numbers.length; i++) {
    const key = numbers[i]
    let j = i - 1
    
    while (j >= 0 && numbers[j] > key) {
      numbers[j  +  1] =  numbers[j]
      j--
    }

    numbers[j  +  1] = key
  }
}

Complexity Analysis

Time Complexity

Best Case (Array is already sorted): $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): $O(n^2)$. In the worst case, each iteration will cause an element to be moved. This makes the algorithm inefficient for large data sets.

Space Complexity

Space Complexity: $O(1)$. Insertion sort is an in-place algorithm; it requires a constant amount of memory space.

Using custom dialog elements instead of native browser implementations, such as alert, confirm, or prompt, has become the standard for web development for quite some time (popularized by various jQuery plugins and by Bootstrap 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 WAI-ARIA accessibility).

But now, with the arrival of the <dialog> element in HTML5 (supported by 93.85% 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 <dialog> element.

Understanding the dialog element

In the sense employed in user interface development, a dialog is a conversation 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:

<dialog open>
  <p>Olá, mundo!</p>
  <form method="dialog">
    <button>Fechar</button>
  </form>
</dialog>

Note the form, on line 5, with the dialog method. It is this form that sends actions to the dialog. It will be displayed like this:

What makes the example above a non-modal dialog is the use of the open attribute (line 1), which also makes it unable to be closed with the Esc key. It’s possible to create a non-modal dialog using the JavaScript API:

In order for it to behave like a modal, it is necessary to open it through its JavaScript API, as we will see next.

This time, we open and close the modal with JavaScript and put the form result in the output element when the modal is closed. Read the code carefully and try to understand what is happening.

Styling the modal

The dialog 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 ::backdrop selector:

Polyfill

If you want to use dialog and don’t have compatibility issues in older browsers, you can use this polyfill.

---

References

• Dialog
• Dialog
• Modal & Nonmodal Dialogs: When (& When Not) to Use Them

---

1. Material UI Modal ↩︎

2. Ant Design Modal ↩︎

3. Carbon Design System Modal ↩︎

Have you ever faced the situation where the layout of your beautifully crafted interface “breaks” if the image (depeding on the quality of your user’s connections) takes some time to load? Something like the example below:

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 aspect-ratio property to tell the browser how much space (based on the user’s size display) it should reserve before the image is loaded. Check the difference:

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;
}

So, it solves the sudden layout change, but we can do even better do better adding an animated background.

Displaying an animated background

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:

And our code will look like this:

: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;
  }
}

And this is the result (check the code on CodePen):

Yet, this can be even better by displaying a colorful background that matches the image colors.

Displaying colorful image placeholders

BlurHash 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’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:

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 onLoad event that changes the opacity of the image.