Insertion Sort Algorithm

Insertion sort is a simple sorting algorithm that works similarly to sorting playing cards in your hands. It is an in-place comparison-based algorithm where elements from the unsorted part are picked and placed at the correct position in the sorted part. Insertion sort is efficient for small datasets or partially sorted arrays, but its time complexity makes it less suitable for large datasets.

How Insertion Sort Works

1. Initialization: The algorithm starts by assuming that the first element is already sorted.
2. Selection: For each iteration, the algorithm picks the next element from the unsorted section.
3. Comparison: This element is compared with the elements in the sorted section, from right to left.
4. Shifting: If the selected element is smaller than an element in the sorted part, all elements greater than the selected element are shifted to the right.
5. Insertion: Once the correct position is found, the element is inserted.

How it works : Steps

1. Take the first value from the unsorted part of the array.
2. Move the value into the correct place in the sorted part of the array.
3. Go through the unsorted part of the array again as many times as there are values.

Manual Run Through

Let’s consider sorting the array [12, 11, 13, 5, 6].

1. Initial Array: [12, 11, 13, 5, 6]
2. Step 1: Pick 11 and compare with 12. Since 11 is smaller, insert it before 12.
   • Array: [11, 12, 13, 5, 6]
3. Step 2: Pick 13. It’s already larger than the previous elements, so no change.
   • Array: [11, 12, 13, 5, 6]
4. Step 3: Pick 5 and insert it before 11 (smallest element in the sorted part).
   • Array: [5, 11, 12, 13, 6]
5. Step 4: Pick 6 and insert it between 5 and 11.
   • Array: [5, 6, 11, 12, 13]

Final sorted array: [5, 6, 11, 12, 13]

Insertion Sort Visualization

Pseudocode

InsertionSort(arr):
  for i from 1 to length(arr) - 1 do
    key = arr[i]
    j = i - 1

    while j >= 0 and arr[j] > key do
      arr[j + 1] = arr[j]
      j = j - 1

    arr[j + 1] = key

Explanation of the Pseudocode:

• The algorithm loops through the array starting from index 1.
• For each element, it compares it with the previous elements in the sorted portion.
• While a larger element is found, it shifts elements to the right.
• Finally, the element is inserted in its correct position.

Flowchart

Here is the flowchart for insertion sort:

1. Start
2. Initialize the sorted portion (first element).
3. Pick next element from the unsorted portion.
4. Compare the picked element with elements in the sorted portion.
5. Shift elements if necessary (those larger than the current element).
6. Insert the current element at the correct position in the sorted portion.
7. Repeat steps 3–6 until all elements are sorted.
8. End

Here is the flowchart for the Insertion Sort algorithm, visually representing the steps.

Now let's move on to the JavaScript code for insertion sort.

JavaScript Code

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let key = arr[i];
    let j = i - 1;

    // Shift elements that are greater than key
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j = j - 1;
    }

    // Insert key at its correct position
    arr[j + 1] = key;
  }
  return arr;
}

// Example usage
const array = [12, 11, 13, 5, 6];
console.log("Sorted Array:", insertionSort(array));

Explanation:

1. The outer loop picks the elements starting from index 1.
2. The inner loop shifts elements greater than the key one position to the right.
3. Finally, the key is inserted in the correct place.

Example Output:

For the input [12, 11, 13, 5, 6], the output will be:

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

This covers the theoretical and practical aspects of insertion sort! Let me know if you'd like any further clarification or additional examples.