Insertion Sort
Insertion Sort Algorithm in C++ (Complete Implementation)
BeginnerTopic: Sorting & Searching Programs
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;
}Output
Original array: 64 34 25 12 22 11 90 Sorted array: 11 12 22 25 34 64 90
Understanding Insertion Sort
Insertion Sort builds the sorted array one item at a time. It's much like sorting playing cards in your hands. Time Complexity: O(n²) worst case, O(n) best case. Space Complexity: O(1). It's stable, in-place, and efficient for small datasets or nearly sorted arrays.
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.