Insertion Sort With Real Life Examples
What is Insertion sorting?
a simple & effective comparison based sorting algorithm. It virtually splits the given array into sorted and unsorted parts.
How Insertion Sort Works?
The algorithm divides the array into a sorted and unsorted region. Values from the unsorted part are picked and placed at the correct position in the sorted part.
Real-Life Example:
Think of it as sorting a bookshelf. You pick a book and slide it over others until it sits next to its peers in order.
The Algorithm Steps
Step 1 : If it is the first element, it is already sorted.
Step 2 : Pick next element
Step 3 : Compare with all elements in the sorted sub-list
Step 4 : Shift all the elements in the sorted sub-list that is greater than the value to be sorted
Step 5 : Insert the value
Step 6 : Repeat until list is sorted
Code
Here’s the code in C programming on Insertion sort.
Complexity and Performance
Insertion sort has an average and worst-case time complexity of O(n²), where n is the number of items. However, it’s efficient for small datasets and mostly sorted arrays.
Advantages and Disadvantages
Advantages: Simple implementation, efficient for small data, adaptive and stable.
Disadvantages: Inefficient for large data sets and has a quadratic time complexity.
Applications of Insertion Sort
Real-Life Example: A librarian might use it to quickly insert a few returned books back into their nearly sorted shelves instead of reorganizing the entire section.
Explore other common sorting algorithms:
Sorting Algorithm
