#include <iostream>
using namespace std;
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// Move elements greater than key one position ahead
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original array: ";
printArray(arr, n);
insertionSort(arr, n);
cout << "Sorted array: ";
printArray(arr, n);
return 0;
}Output
Original array: 64 34 25 12 22 11 90 Sorted array: 11 12 22 25 34 64 90
This program teaches you how to implement the Insertion Sort algorithm in C++. Insertion Sort is an intuitive sorting algorithm that works similarly to how you might sort playing cards in your hands - you pick up each card and insert it into its correct position among the already sorted cards. It's efficient for small datasets and nearly sorted arrays.
1. What This Program Does
The program sorts an array of integers using the Insertion Sort algorithm. For example:
- Input array: [64, 34, 25, 12, 22, 11, 90]
- Output array: [11, 12, 22, 25, 34, 64, 90]
Insertion Sort builds the sorted array incrementally by inserting each element into its correct position in the already sorted portion.
2. Header File Used
#include <iostream>
This header provides:
- cout for displaying output
- cin for taking input from the user
3. Understanding Insertion Sort
Algorithm Concept:
- Maintains a sorted subarray at the beginning
- Takes next element and inserts it in correct position
- Shifts larger elements to make room
- Similar to sorting cards in hand
Visual Example:
Initial: [64, 34, 25, 12, 22, 11, 90]
Step 1: [34, 64, 25, 12, 22, 11, 90] (insert 34 before 64) Step 2: [25, 34, 64, 12, 22, 11, 90] (insert 25 at beginning) Step 3: [12, 25, 34, 64, 22, 11, 90] (insert 12 at beginning) Step 4: [12, 22, 25, 34, 64, 11, 90] (insert 22 after 12) Step 5: [11, 12, 22, 25, 34, 64, 90] (insert 11 at beginning) Step 6: [11, 12, 22, 25, 34, 64, 90] (90 already in place)
4. Function: insertionSort()
void insertionSort(int arr[], int n) { for (int i = 1; i < n; i++) { int key = arr[i]; int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
How it works:
- Outer loop (i): iterates from 1 to n-1 (each element to insert)
- key: current element to be inserted
- Inner while loop: shifts larger elements right
- Inserts key in correct position
5. Step-by-Step Algorithm
For each element arr[i] (starting from i=1):
Step 1: Store Current Element
- key = arr[i] (element to be inserted)
Step 2: Find Insertion Position
- Compare key with elements in sorted portion (arr[0] to arr[i-1])
- Shift elements greater than key one position right
- Continue until correct position found
Step 3: Insert Element
- Place key in correct position
- Sorted portion grows by one element
Example (inserting 22 when sorted portion is [12, 25, 34, 64]):
- key = 22
- Compare: 64 > 22 → shift 64 right
- Compare: 34 > 22 → shift 34 right
- Compare: 25 > 22 → shift 25 right
- Compare: 12 < 22 → stop
- Insert 22 after 12
6. Understanding the Inner While Loop
while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; }
How it works:
- j starts at i - 1 (last element of sorted portion)
- Condition: j >= 0 (within bounds) AND arr[j] > key (need to shift)
- arr[j + 1] = arr[j] shifts element right
- j-- moves to previous element
- Stops when correct position found
Why j >= 0?:
- Prevents accessing arr[-1]
- Ensures we stay within array bounds
- Stops at beginning of sorted portion
7. Time and Space Complexity
Time Complexity:
- Worst case: O(n²) - array in reverse order
- Best case: O(n) - array already sorted
- Average case: O(n²)
Space Complexity: O(1)
- Only uses constant extra space
- Sorts in-place (modifies original array)
Stability: Stable
- Equal elements maintain their relative order
- Important for sorting objects with multiple fields
8. When to Use Insertion Sort
Best For:
- Small datasets (< 50 elements)
- Nearly sorted arrays
- Online algorithms (sorting as data arrives)
- Simple implementation needed
Not Recommended For:
- Large datasets (use Quick Sort, Merge Sort)
- Random data (better algorithms available)
- Performance-critical applications
9. Important Considerations
Starting Index:
- Outer loop starts at i = 1 (not 0)
- First element (arr[0]) is already "sorted"
- Each iteration adds one element to sorted portion
Shifting Elements:
- Elements are shifted right, not swapped
- More efficient than swapping
- Preserves relative order
Key Variable:
- Store arr[i] in key before shifting
- Prevents losing the value during shifts
- Insert key after finding position
10. return 0;
This ends the program successfully.
Summary
- Insertion Sort builds sorted array incrementally, one element at a time.
- Time complexity: O(n²) worst/average, O(n) best case.
- Space complexity: O(1) - sorts in-place.
- Stable algorithm - maintains relative order of equal elements.
- Efficient for small datasets and nearly sorted arrays.
- Similar to sorting playing cards - intuitive and easy to understand.
- Shifts elements right to make room for insertion.
- Understanding Insertion Sort is foundation for learning other sorting algorithms.
This program is fundamental for beginners learning sorting algorithms, understanding incremental sorting, and preparing for more efficient algorithms in C++ programs.