What is an insertion sort in C++ and how is it implemented?

Table of Contents

• Introduction
• How Insertion Sort Works
  • Algorithm Steps:
  • Time Complexity:
  • Space Complexity:
• Implementation of Insertion Sort in C++
  • Explanation of the Code:
  • Output:
• Practical Examples of Insertion Sort
  • Example 1: Sorting a List of Test Scores
  • Example 2: Sorting an Array of Characters
• Conclusion

Introduction

Insertion sort is a simple and intuitive sorting algorithm that builds a sorted array one element at a time. It works similarly to how people sort playing cards in their hands. The algorithm divides the array into a sorted and an unsorted part. It repeatedly takes one element from the unsorted part, compares it with the sorted part, and inserts it into the correct position.

Insertion sort is efficient for small datasets and nearly sorted arrays but has a time complexity of O(n²), making it less efficient for large datasets.

How Insertion Sort Works

Algorithm Steps:

1. Start from the second element (index 1), treating the first element as a sorted portion.
2. Compare the current element with the elements in the sorted portion and shift all elements larger than the current element to the right.
3. Insert the current element into its correct position.
4. Repeat this process for all elements until the array is sorted.

Time Complexity:

• Worst-case: O(n²) (when the array is sorted in reverse order)
• Best-case: O(n) (when the array is already sorted)
• Average-case: O(n²)

Space Complexity:

• Space Complexity: O(1) (in-place sorting)

Implementation of Insertion Sort in C++

Here’s how to implement insertion sort in C++:

Explanation of the Code:

1. insertionSort Function:
   • The outer loop starts from the second element (i = 1) because the first element is considered sorted.
   • The key stores the value of the element to be inserted into the sorted portion.
   • The inner while loop compares the key with elements in the sorted portion and shifts larger elements one position to the right.
   • The key is then placed in its correct position.
2. printArray Function:
   • This function prints the contents of the array.

Output:

Practical Examples of Insertion Sort

Example 1: Sorting a List of Test Scores

You can use insertion sort to organize student test scores in ascending order.

Output:

Example 2: Sorting an Array of Characters

Insertion sort can also be applied to arrays of characters to sort them in alphabetical order based on their ASCII values.

Output:

Conclusion

Insertion sort is a straightforward algorithm that is easy to understand and implement. It works well for small or nearly sorted datasets, where it can perform optimally with a time complexity of O(n). However, for larger datasets, its O(n²) worst-case time complexity makes it less efficient compared to other algorithms like quicksort or mergesort. In C++, insertion sort is implemented using a simple loop structure and performs well when minimal memory usage is a priority due to its O(1) space complexity.