# Insertion Sort Algorithm with C++ Code | Sorting Algorithms | Data Structures & Algorithms

In this tutorial we understand the working of insertion sort algorithm in data structures.

##### **Insertion Sort –**

- Insertion sort is a simple sorting algorithm that works the way we sort playing cards in our hands.
- Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time.
- Time Complexity: O(n*2)
- Efficient for (quite) small data sets, much like other quadratic sorting algorithms
- More efficient in practice than most other simple quadratic (i.e., O(n2)) algorithms such as selection sort or bubble sort

##### Working –

- null
- Step 1 – Pick next element
- Step 2 – Compare with all elements in the sorted sub-list on the left
- Step 3 – Shift all the elements in the sorted sub-list that is greater than the
- value to be sorted
- Step 4 – Insert the value
- Step 5 – Repeat until list is sorted

**Insertion Sort Algorithm –**

*declare variables – i, key, j**loop : i = 1 to n – 1 // outer loop**key = a[i] //pick the next element**j = i – j; // decrement j value**loop : (j>=0 && a[j]>key) // inner loop**arr[j+1] = arr[j]**j = j – 1*

*end loop // outer loop**arr[j+1] = key*

*end loop // outer loop*

##### **C++ Program to Implement Selection Sort –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | #include < iostream > using namespace std; void insertionSort(int arr[]) { int key; int j = 0; for (int i = 1; i < 5; i++) { key = arr[i]; j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = key; } } int main() { int myarray[5]; cout << "Enter 5 integers in any order" << endl; for (int i = 0; i < 5; i++) { cin >> myarray[i]; } cout << "Before Sorting: " << endl; for (int i = 0; i < 5; i++) { cout << myarray[i] << " "; } insertionSort(myarray); cout << endl << "After Sorting: " << endl; for (int i = 0; i < 5; i++) { cout << myarray[i] << " "; } return 0; } |

**YouTube video tutorials –**