JavaScript: Implement the Insertion Sort Algorithm

1. Introduction

Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as Quick Sort or Merge Sort. However, Insertion Sort provides a more intuitive approach, especially for smaller datasets.

2. Program Overview

For this guide, we will:

1. Initialize an array of numbers.

2. Implement the Insertion Sort algorithm.

3. Display the sorted array.

3. Code Program

let numbers = [12, 11, 13, 5, 6];  // Initializing an unsorted array

function insertionSort(arr) {
    let n = arr.length;
    for (let i = 1; i < n; i++) {
        let key = arr[i];
        let j = i - 1;
        
        // Move elements of arr[0..i-1] that are greater than key to one position ahead of their current position
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

insertionSort(numbers);  // Sorting the array using Insertion Sort

console.log("Sorted array:", numbers);

Output:

Sorted array: [5, 6, 11, 12, 13]

4. Step By Step Explanation

1. Array Initialization: We start with an unsorted array named numbers.

2. Insertion Sort Implementation:

- We iterate through the elements of the array starting from the second element (index 1).

- For each element, we consider it as a key.

- We then compare this key with the previous elements. If the key is smaller than the previous element, we shift the previous element to the right. This process is repeated until we find an element smaller than the key or if there are no more elements to the left.

- Once the correct position for the key is found, we insert it.

3. Displaying the Result: After sorting the array using the insertionSort function, we display the sorted array.