JavaScript Program to Implement the Insertion Sort Algorithm

Introduction

Insertion Sort is a simple and efficient sorting algorithm. It works by building a sorted section of the array one element at a time. At each step, the algorithm picks the next element and inserts it into its correct position within the already sorted portion of the array. This algorithm is efficient for small datasets and is often used as an introductory algorithm to sorting.

Problem Statement

Create a JavaScript program that:

• Accepts an array of numbers.
• Sorts the array using the Insertion Sort algorithm.
• Returns and displays the sorted array.

Example:

• Input: [5, 2, 9, 1, 5, 6]

• Output: [1, 2, 5, 5, 6, 9]

• Input: [12, 11, 13, 5, 6]

• Output: [5, 6, 11, 12, 13]

Solution Steps

1. Read the Input Array: Provide an array of numbers either as user input or directly within the code.
2. Sort the Array: Implement the Insertion Sort algorithm to sort the array in ascending order.
3. Display the Result: Print the sorted array.

JavaScript Program

// JavaScript Program to Implement the Insertion Sort Algorithm
// Author: https://www.javaguides.net/

function insertionSort(arr) {
    // Step 1: Loop through the array starting from index 1
    for (let i = 1; i < arr.length; i++) {
        let key = arr[i];
        let j = i - 1;

        // Step 2: Compare the key with previous elements and move them if they are larger
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }

        // Step 3: Insert the key into its correct position
        arr[j + 1] = key;
    }
    
    // Step 4: Return the sorted array
    return arr;
}

// Example input
let array = [5, 2, 9, 1, 5, 6];
let sortedArray = insertionSort(array);
console.log(`The sorted array is: [${sortedArray}]`);

Output

The sorted array is: [1, 2, 5, 5, 6, 9]

Example with Different Input

let array = [12, 11, 13, 5, 6];
let sortedArray = insertionSort(array);
console.log(`The sorted array is: [${sortedArray}]`);

Output:

The sorted array is: [5, 6, 11, 12, 13]

Explanation

Step 1: Loop Through the Array

• The outer loop starts from index 1 because the element at index 0 is considered to be already sorted.
• The variable key stores the current element to be inserted in the correct position.

Step 2: Compare and Move Elements

• The inner while loop compares the key with the elements to its left (those already sorted). If an element is larger than the key, it is shifted one position to the right.

Step 3: Insert the Key

• Once the correct position is found, the key is inserted, and the sorted section grows by one element.

Step 4: Return the Sorted Array

• The sorted array is returned and printed using console.log().

Conclusion

This JavaScript program demonstrates how to implement the Insertion Sort algorithm, which is efficient for small datasets and nearly sorted data. The algorithm builds the sorted section incrementally and is easy to understand, making it a great choice for learning sorting techniques. It has a time complexity of O(n²) in the worst case but can perform well on small or nearly sorted datasets.