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

In computer science, a first-class citizen is an entity that supports all operations available to other entities. Some of the available operations are:
<ul>
<li>They may be named by variables;</li>
<li>They may be passed as arguments to procedures;</li>
<li>They may be returned as the results of procedures;</li>
<li>They may be included in data structures.</li>
</ul>
It was the British computer scientist Christopher Strachey (1916-1975) <a href="https://link.springer.com/article/10.1023/A:1010052305354">who first</a> coined this notion of first-class citizen status of elements in a programming language in the 1960s.
In JavaScript, for example, functions are first-class citizens, as all of the operations cited above can be applied to them. Let&#39;s see some examples:
A simple function definition in JavaScript
<pre><code class="highlited-code-wrapper langjavascript"><div class="highlited-code" data-language="javascript">function sum(a, b) {
 return a + b
}</div>
</code></pre>Assigning a constant to a function
<pre><code class="highlited-code-wrapper langjavascript"><div class="highlited-code" data-language="javascript">const sum = (a, b) =&gt; a + b

// or
// 
// const sum = function (a, b) {
// a + b
// }</div>
</code></pre>Passing a function as an argument
<pre><code class="highlited-code-wrapper langjavascript"><div class="highlited-code" data-language="javascript">function sum(a, b, callback) {
 const result = a + b

 if (typeof callback === 'function') {
 callback(result) // pass the result as an argument of `callback`
 }

 return result
}

// Pass `console.log` as the callback function
// -------\/
sum(2, 2, console.log) // =&gt; 4</div>
</code></pre>Return a function
<pre><code class="highlited-code-wrapper langjavascript"><div class="highlited-code" data-language="javascript">function sum(a, b, callback) {
 const result = a + b

 if (callback) {
 return () =&gt; callback(result)
 }

 return result
}

// The callback is the sum of the result with 2.
// ------------------\/
const fn = sum(2, 2, (result) =&gt; sum(2, result))
// ^---- Store the returned function in a variable

// Execute the function
// ---------\/
console.log(fn()) // =&gt; 6</div>
</code></pre>Including a function in a data structure
<pre><code class="highlited-code-wrapper langjavascript"><div class="highlited-code" data-language="javascript">// Store the basic operations in an object
const operations = {
 sum: (a, b) =&gt; a + b,
 sub: (a, b) =&gt; a - b,
 mul: (a, b) =&gt; a * b,
 div: (a, b) =&gt; a / b,
}</div>
</code></pre>

What is a first-class citizen in computer science?

A remote procedure call (RPC) is a mechanism of communication between two computational environments, where one can be identified as a client, while the other can be identified as a server.
From the client&#39;s point of view, the RPC is just a matter of calling a function with the desired arguments and await for the response, in order to continue the program&#39;s execution.
<img src="https://dev-to-uploads.s3.amazonaws.com/uploads/articles/p3733ruz3n51tadloaaq.png" alt="Diagram on how a RPC (remote procedure call) works">
Thus, using an RPC allows one programmer to distribute the system, according to their needs.
References:
<ul>
<li><a href="https://www.youtube.com/watch?v=gr7oaiUsxSU">RPC Vs Simple Procedure Call - Georgia Tech - Advanced Operating Systems</a></li>
<li><a href="https://learn.microsoft.com/en-us/windows/win32/rpc/how-rpc-works">How RPC works</a></li>
<li><a href="https://users.cs.cf.ac.uk/Dave.Marshall/C/node33.html">Remote Procedure Calls (RPC)</a></li>
<li><a href="https://web.archive.org/web/20030404113118/http://techpubs.sgi.com/library/tpl/cgi-bin/getdoc.cgi?coll=0650&db=bks&srch=&fname=/SGI_Developer/IRIX_NetPG/sgi_html/ch04.html">Introduction to RPC Programming</a></li>
<li><a href="https://colinhacks.com/essays/painless-typesafety">Building an end-to-end typesafe API — without GraphQL</a></li>
</ul>

Douglas Moura

Douglas Moura

#computerscience

Mastering Insertion Sort: A Detailed Guide

What is a first-class citizen in computer science?

What is a RPC (Remote Procedure Call)?