JavaScript Program for Insertion Sort

An overview of insertion sort in JavaScript

Sorting is a fundamental concept that anyone embarking on a path in computer science needs to grasp, irrespective of the programming language they decide to learn. This technique of organizing data enables us to locate and retrieve information swiftly and easily by arranging it in either ascending or descending sequences.

Sorting algorithms are designed to arrange elements, which can include numbers or strings. Numerous sorting algorithms exist, and they can be categorized based on their sorting techniques and the approaches utilized during the sorting process. Each algorithm comes with its own set of advantages and disadvantages.

In this article, we will concentrate on insertion sort, a widely employed sorting algorithm that is not only effective but also quite easy to comprehend and implement.

What is insertion sort in JavaScript?

Insertion Sort is an easy-to-understand and straightforward algorithm that proves effective for organizing small datasets. The mechanism involves positioning each element sequentially from the left to the right of the list. As a comparison sort, it assesses the current element against other elements within the already sorted portion of the list. By employing an iterative technique, it systematically arranges each element in its appropriate position within the list.

The efficiency of an algorithm can be assessed based on the duration required to finish the sorting process; a longer completion time indicates a suboptimal time complexity that may necessitate alternative sorting methods. Insertion sort exhibits a time complexity of O(n²), which reflects the maximum number of operations in relation to n. For this reason, it is generally unsuitable for large datasets due to its poor performance. However, when dealing with smaller datasets, insertion sort proves to be more efficient than more complex algorithms like quicksort and mergesort.

Insertion sort demonstrates greater efficiency compared to other quadratic sorting algorithms such as selection sort and bubble sort. In its optimal scenario, the time complexity reaches O(n), which is linear. This occurs when the input array is already arranged in a sorted manner. Nevertheless, the average-case time complexity for the execution of insertion sort remains quadratic.

We will now examine a variety of scenarios involving input and output.

Imagine an array containing elements arranged in a random sequence, which means it is unsorted. We can organize these elements using the insertion sort algorithm. Therefore, let us examine the following.

Input = [24, 22, 26, 10, 12]; 
Output = 10, 12, 22, 24, 26

How does the insertion sort algorithm work?

The operation of the insertion sort algorithm can be better understood through a concrete example. Take the array arr = [24, 22, 26, 10, 12].

First Pass

At the beginning of the insertion sort algorithm, a comparison is made between the first two elements of the array.

In this instance, 22 is less than 24; consequently, the values are not arranged in ascending order, which means that 24 is not positioned appropriately. As a result, it is necessary to exchange the locations of 22 and 24. Here, 24 is presently held within a subarray.

Second Pass

Now, compare the next two elements in the array.

In this scenario, the figures 24 and 26 are in ascending order because 26 exceeds 24. Therefore, no swapping will take place.

In addition, 24 was included in the sub-array that contained 22.

Third Pass

At this moment, the sub-array consists of the two values: 22 and 24. Next, we will proceed to evaluate the subsequent pair of elements, which are 10 and 26.

As 10 is smaller than 26, Swap both the values.

Despite the exchange of 10 and 24, the array remains unsorted; therefore, a second swap is necessary.

Again 10 and 22 are not sorted, so swap again.

Now, 10 is at the correct position.

Fourth Pass

The values present in the ordered subarray include 10, 22, and 24.

The subsequent two elements under comparison are 26 and 12.

Since they are not sorted, swap both values.

Now, 12 is smaller than 24. Thus, swap them.

In this scenario, the number 12 is less than 22, and since they are not arranged in order, it is necessary to exchange their positions.

And at last, the array is perfectly sorted.

Algorithm

To sort an array of size n in ascending order utilizing the insertion sort algorithm, one needs to follow the following steps:

• ✅ If the element considered is the first one, then it is already sorted. It returns 1.
• ✅ Choose the next element.
• ✅ Compare this element with all elements in the already sorted sub-list.
• ✅ Shift all elements in the sorted sub-list that are greater than the current value to the right.
• ✅ Put the current value into its correct place.
• ✅ Repeat this step until the list is sorted.

If data is ordered, it makes finding the best solutions to complex problems. Some examples of these operations include:

• ✅ Finding a specific value.
• ✅ Finding the minimum or maximum value.
• ✅ Checking for uniqueness and eliminating duplicates.
• ✅ Counting the occurrences of a given value and more.

Demonstration 1

Below is a demonstration of the insertion sort algorithm.

<!DOCTYPE html> 
<html> 
   <title>Example for insertion sort in JavaScript</title> 
<head> 
   <script> 
      function example(Array, length) { 
         for (let a = 2; a < length; a++) { 
            let item = Array[a]; 
            let y = a - 1; 
            while (y >= 0 && Array[y] > item) { 
               Array[y + 1] = Array[y]; 
               y = y - 1; 
            } 
            Array[y + 1] = item; 
         } 
      } 
      document.write("Here is the final array: ");  
      function FinalArray(Array, length) { 
         for (let a = 0; a < length; a++) 
         document.write(Array[a] + " "); 
      }  
      let Array = [5, 8, 1, 23, 4]; 
      let length = Array.length; 
      example(Array, length); 
      FinalArray(Array, length); 
   </script>   
</head> 
<body> 
</body> 
</html>

Output

Demonstration 2

Utilizing the unshift method

This technique is utilized to add extra items to the start of an array. It provides the new length of the array after the insertion.

<html> 
<head> 
   <script> 
      function iSort(arr) { 
         for (var a = 0; a < arr.length; a++) { 
            if (arr[a] < arr[0]){ 
               arr.unshift(arr.splice(a,1)[0]); 
            } 
            else if (arr[a] > arr[a-1]) { 
               continue; 
            } 
            else { 
               for (var q = 1; q < a; q++) { 
                  if (arr[a] > arr[q-1] && arr[a] < arr[q]){ 
                     arr.splice(q,0,arr.splice(a,1)[0]); 
                  } 
               } 
            } 
         } 
         return arr; 
      } 
      document.write(iSort([10,-3,6,16,9,0,1])); 
   </script> 
</head> 
</html>

Output

Conclusion

Insertion Sort is a simple, stable, and in-place comparison sorting algorithm. Despite its time complexity of O(n²), which renders it relatively inefficient for large datasets, it demonstrates remarkable effectiveness when dealing with small input arrays. In these cases, it can outperform many commonly used divide-and-conquer sorting algorithms. This efficiency is why JavaScript adopts a hybrid methodology, integrating Insertion Sort with either Merge Sort or Quicksort in its native sorting functionalities.

When dealing with larger arrays, Insertion Sort shows better efficiency in comparison to several other quadratic sorting algorithms, including Bubble Sort, Gnome Sort, and Selection Sort.