Subscribe to our RSS
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 < 26 No SWAP
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.
for ( unsigned i = 1; i < vec.size(); i++ )
{
temp = vec[i];
for ( int j = i – 1; j >= 0; j-=1 )
{
if ( temp < vec[j] )
swap(vec[j+1], vec[j]);
else
break;
}
}
(5 votes, average: 4.20 out of 5)
June 24th, 2009 at 8:35 am
Slight typo: j- should presumably be j–
June 30th, 2009 at 10:53 pm
Thank you for mentioning it as a typo. Apparently the syntax highlighter doesn’t allow ‘–’ so I’ll see if the posted alternative works.
Thanks.