# Insertion Sort Algorithm

## Insertion Sort Algorithm C++

Insertion sort algorithm removes an element from the sorting list, and placing it into the correct position in the already sorted part of the list, until no input elements left. The insertion sort algorithm complexity depends on the input list. If the list is already sorted we have best case, which has linear complexity O(n). If the list is reversed then we have worst case, quadratic running time O(n^2). And the average case is also quadratic running time O(n^2), which make the insertion sort not practical algorithm of choice for large n( where n is number of element in the data structure), however insertion sort is one of the fastest algorithms for sorting very small arrays.

### Insertion Sorting Algorithm Complexity

1. Worst case performance O(n^2)
2. Best case performance O(n)
3. Average case performance O(n^2)

### Insertion Sorting Algorithm Best, worst, and average cases

The best case input is an array that is already sorted. In this case insertion sort has a linear running time (i.e., Θ(n)). During each iteration, the first remaining element of the input is only compared with the right-most element of the sorted subsection of the array.

The simplest worst case input is an array sorted in reverse order. The set of all worst case inputs consists of all array where each element is the smallest or second-smallest of the elements before it. In these cases every iteration of the inner loop will scan and shift the entire sorted subsection of the array before inserting the next element. This gives insertion sort a quadratic running time (i.e., O(n2)).

The average case is also quadratic, which makes insertion sort impractical for sorting large array. However, insertion sort is one of the fastest algorithms for sorting very small arrays, even faster than quicksort; indeed, good quicksort implementations use insertion sort for arrays smaller than a certain threshold, also when arising as subproblems; the exact threshold must be determined experimentally and depends on the machine, but is commonly around ten.

### Example:

The following table shows the steps for sorting the sequence of insertion sort {3, 7, 4, 9, 5, 2, 6, 1}. In each step, the item under consideration is underlined. The item that was moved (or left in place because it was biggest yet considered) in the previous step is shown in bold.

3 7 4 9 5 2 6 1

3 7 4 9 5 2 6 1

3 7 4 9 5 2 6 1

3 4 7 9 5 2 6 1

3 4 7 9 5 2 6 1

3 4 5 7 9 2 6 1

2 3 4 5 7 9 6 1

2 3 4 5 6 7 9 1

1 2 3 4 5 6 7 9

### Implementation of Insertion Sort Algorithm

```/*
* File : insertion_sort.cpp
* Author: MyCodingLab
* Code : Insertion Sort Algorithm
*/

#include <cstdlib>
#include <iostream>

using namespace std;

//member function
void insertion_sort(int arr[], int length);
void print_array(int array[],int size);

int main() {

int array= {5,4,3,2,1};
insertion_sort(array,5);

return 0;
}//end of main

void insertion_sort(int arr[], int length) {
int i, j ,tmp;
for (i = 1; i < length; i++) {
j = i;
while (j > 0 && arr[j - 1] > arr[j]) {
tmp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = tmp;
j--;
}//end of while loop
print_array(arr,5);
}//end of for loop
}//end of insertion_sort.

void print_array(int array[], int size){

cout<< "sorting: ";
int j;
for (j=0; j<size;j++)
for (j=0; j<size;j++)
cout <<" "<< array[j];
cout << endl;
}//end of print_array

```

### Program Output

```
insertion sort steps: 4 5 3 2 1
insertion sort steps: 3 4 5 2 1
insertion sort steps: 2 3 4 5 1
insertion sort steps: 1 2 3 4 5

```