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 an Array of Student Scores
  • Example 2: Sorting a Character Array
• Conclusion

Introduction

Insertion sort is a basic sorting algorithm that builds a sorted array or list one element at a time. It mimics the process of sorting playing cards in your hands. The algorithm divides the data into a sorted and an unsorted section and continuously takes elements from the unsorted section and places them in the correct position within the sorted section.

This algorithm is efficient for small datasets and nearly sorted arrays but becomes inefficient for larger datasets due to its quadratic time complexity.

How Insertion Sort Works

Algorithm Steps:

1. Start with the second element (index 1) and assume the first element is sorted.
2. Compare the current element with the elements in the sorted portion.
3. Shift all elements larger than the current element one position to the right.
4. Insert the current element into its correct position.
5. Repeat the process until the entire 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 begins at the second element (i = 1), as the first element is treated as sorted.
   • The key holds the current element to be inserted into the sorted section.
   • The inner while loop shifts all elements larger than the key one position to the right to make room for the key.
   • After the loop, the key is inserted in its correct position in the sorted portion.
2. printArray Function:
   • This function prints the elements of the array.

Output:

Practical Examples of Insertion Sort

Example 1: Sorting an Array of Student Scores

In a scenario where you need to organize student scores, insertion sort can be an effective method.

Output:

Example 2: Sorting a Character Array

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

Output:

Conclusion

Insertion sort is a simple yet effective sorting algorithm, particularly for small or partially sorted datasets. While its O(n²) time complexity makes it less optimal for large datasets, its simplicity and low space overhead (O(1) space complexity) make it a useful option for specific cases. In C, insertion sort can be implemented with a straightforward loop structure and is particularly well-suited for small applications where efficiency is not a primary concern.