Insertion Sort Implementation in C++ [Sorting Algorithms]

Insertion Sort is sorting algorithm similar to Bubble Sort simply because they are basic sorting algorithms. The difference, is that Insertion Sort iterates through the data structure selects an element and inserts it into its correct location until no elements are left to sort.

Insertion Sort Visual Example

26

5

12

-6

First Iteration
The element 5 in position 1 is inserted into its appropriate location (position 0).

5

26

12

-6

26 vs 5 equals SWAP

Second Iteration
The element 26 in position 2 is inserted into its appropriate location (position 1).

5

12

26

-6

26 > 12 equals SWAP

Third Iteration
The element 26 in position 3 is in its appropriate position since it is greater than all the elements before it.

5

12

26

-6

12 <>

Fourth Iteration
The element -6 in position 3 is inserted into its appropriate position (position 0).

5

12

-6

26

26 > -6 SWAP

5

-6

12

26

12 > -6 SWAP

-6

5

12

26

5 > -6 SWAP

Insertion Sort Implementation in C++

Below is the implementation of Insertion Sort in C++. The algorithm merely consists of inserting an element into its appropriate position by swapping it with the previous elements in the vector until it no longer is smaller than the element before it. Once inserted into its appropriate position, we look at the following element.

int temp;

for ( unsigned i = 1; i < class="me1">size(); i++ )
{
temp = vec[i];

for ( int j = i - 1; j >= 0; j– )
{
if ( temp < class="br0">[j] )
swap(vec[j+1], vec[j]);
else
break;
}

}