The best programs are written so that computing machines can perform
them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist
who works with traditional aesthetic and literary forms as well as mathematical concepts, to
communicate the way that an algorithm works and to convince a reader that the results will be correct.
― Donald E. Knuth

Problem :-
Implement the Insertion sort algorithm.

Solution :-
This algorithm works by taking elements from an unsorted array one by one and inserting them in their proper position in the new sorted array.
This invloves comparison and shifting operation. Complexity of the
algorithm is O(n^{2}).
Consider the following array { 7, 2, 5, 3, 4 }. Let's see how Insertion sort technique works :-

First Iteration :: { 7, 2, 5, 3, 4 } -> { 2, 7, 5, 3, 4 } ( 2 is placed in its proper position and 7 is shifted )

Second Iteration :: { 2, 7, 5, 3, 4 } -> { 2, 5, 7, 3, 4 } ( 5 is placed in its proper position and 7 is shifted )

Third Iteration :: { 2, 5, 7, 3, 4 } -> { 2, 3, 5, 7, 4 } ( 3 is placed in its proper position and 5 & 7 are shifted )

Fourth Iteration :: { 2, 3, 5, 7, 4 } -> { 2, 3, 4, 5, 7 } ( 4 is placed in its proper position and 5 & 7 are shifted )

#include<iostream>using namespace std;
// Display the Arrayvoid displayArray(int arr[], int size) {
int i;
for (i=0;i<size;i++) {
cout<<arr[i]<<" ";
}
}
// swap elements in the arrayvoid swap(int arr[],int idx1,int idx2) {
int temp;
temp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = temp;
}
// insertion sortvoid insertionSort(int arr[],int size) {
int i,j;
// select elements one by one and insert them in
// their proper position in the sorted arrayfor (i=1;i<size;i++) {
j = i;
// iterate and shift leftwards till we find the
// first element less than the selected elementwhile (j > 0 && arr[j] < arr[j-1]) {
swap(arr,j,j-1);
j--;
}
}
}
// mainint main() {
int arr[] = {7,4,5,2,3,19,11,6,9,12,8};
int size = sizeof(arr)/sizeof(arr[0]);
cout<<"\nOriginal Array :: ";
displayArray(arr,size);
insertionSort(arr,size);
cout<<"\nSorted Array :: ";
displayArray(arr,size);
cout<<endl;
return 0;
}

#include<iostream>using namespace std;
// Display the Arrayvoid displayArray(int arr[], int size) {
int i;
for (i=0;i<size;i++) {
cout<<arr[i]<<" ";
}
}
// swap elements in the arrayvoid swap(int arr[],int idx1,int idx2) {
int temp;
temp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = temp;
}
// insertion sortvoid insertionSort(int arr[],int size) {
int i,j;
// select elements one by one and insert them in
// their proper position in the sorted arrayfor (i=1;i<size;i++) {
j = i;
// iterate and shift leftwards till we find the
// first element less than the selected elementwhile (j > 0 && arr[j] < arr[j-1]) {
swap(arr,j,j-1);
j--;
}
}
}
// mainint main() {
int arr[] = {7,4,5,2,3,19,11,6,9,12,8};
int size = sizeof(arr)/sizeof(arr[0]);
cout<<"\nOriginal Array :: ";
displayArray(arr,size);
insertionSort(arr,size);
cout<<"\nSorted Array :: ";
displayArray(arr,size);
cout<<endl;
return 0;
}