We are going to talk about the idea behind the Insertion sort algorithm. Basically, It’s a simple sorting algorithm that sorts the array by shifting the elements one at a time. The essential advantage of the insertion sort is that it’s stable. Therefore the algorithm is more effective than the bubble sort and selection sort algorithms.
Visual diagram of the Insertion sort algorithm
Implementation of the algorithm in C++
// Insertion sort algorithm implementation in C++ #include <iostream> using namespace std; int main() { // Sorting Elements of an array in ascending order using insertion sort algorithm int data[100]; int n,temp; int i,j; cout << ("Enter number of terms(should be less than 100): "); cin >> n; cout << "Enter elements: "; for(i=0;i<n;i++) { cin >> data[i]; } for(i=1;i<n;i++) { temp = data[i]; j=i-1; while(temp<data[j] && j>=0) { data[j+1] = data[j]; --j; } data[j+1]=temp; } cout << "In ascending order: \n"; for(i=0; i<n; i++) cout << data[i] << "\n"; return 0; }