Insertion Sort
Insertion Sort Algorithm in C++ (Complete Implementation)
C++ Insertion Sort Program
This program helps you to learn the fundamental structure and syntax of C++ programming.
#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;
}Original array: 64 34 25 12 22 11 90 Sorted array: 11 12 22 25 34 64 90
Understanding Insertion Sort
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:
Insertion Sort builds the sorted array incrementally by inserting each element into its correct position in the already sorted portion.
---
2. Header File Used
This header provides:
---
#include <iostream>3. Understanding Insertion Sort
Algorithm Concept
:
Visual Example
:
---
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
:
---
5. Step-by-Step Algorithm
For each element arr[i] (starting from i=1)
:
Step 1: Store Current Element
Step 2: Find Insertion Position
Step 3: Insert Element
Example
(inserting 22 when sorted portion is [12, 25, 34, 64]):
---
6. Understanding the Inner While Loop
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
How it works
:
Why j >= 0?
:
---
7. Time and Space Complexity
Time Complexity
:
Space Complexity
: O(1)
Stability
: Stable
---
8. When to Use Insertion Sort
Best For
:
Not Recommended For
:
---
9. Important Considerations
Starting Index
:
Shifting Elements
:
Key Variable
:
---
10. return 0;
This ends the program successfully.
---
Summary
This program is fundamental for beginners learning sorting algorithms, understanding incremental sorting, and preparing for more efficient algorithms in C++ programs.
Let us now understand every line and the components of the above program.
Note: To write and run C++ programs, you need to set up the local environment on your computer. Refer to the complete article Setting up C++ Development Environment. If you do not want to set up the local environment on your computer, you can also use online IDE to write and run your C++ programs.
Practical Learning Notes for Insertion Sort
This C++ program is part of the "Sorting & Searching Programs" topic and is designed to help you build real problem-solving confidence, not just memorize syntax. Start by understanding the goal of the program in plain language, then trace the logic line by line with a custom input of your own. Once you can predict the output before running the code, your understanding becomes much stronger.
A reliable practice pattern is to run the original version first, then modify only one condition or variable at a time. Observe how that single change affects control flow and output. This deliberate style helps you understand loops, conditions, and data movement much faster than copying full solutions repeatedly.
For interview preparation, explain this solution in three layers: the high-level approach, the step-by-step execution, and the time-space tradeoff. If you can teach these three layers clearly, you are ready to solve close variations of this problem under time pressure.