Insertion Sort Algorithm in C++
Insertion sort algorithm was developed using comparison algorithm. This algorithm splits the array into two sub-arrays namely sorted
and un-sorted sub arrays. Initially the sorted sub array contains only one element in other words the first item of a main array was considered
as a sorted array and the rest of the items was considered as a un-sorted array. Take a leftmost element in a un-sorted array to
find the suitable place in the sorted array and finally place the number in a suitable place holder till there is no elements exist
in the un-sorted sub array. Insertion sort is an easiest way of sorting technique, but it's not an efficient on large data sets.
Moreover, Insertion sort is more efficient and advanced algorithm than the Quick sort, Heap sort or merge sort.
Time Complexity
- Best complexity: n
- Average complexity: n^2
- Worst complexity: n^2
Insertion Sort Implementation in C++
C++ Input Screen
#include <iostream>
using namespace std;
class InsertionSortExample
{
// Access specifier
public:
void insertionSort(int arr[], size_t size) {
for(size_t i = 1; i < size; i++) {
int temp = arr[i];
int holePosition = i;
while(holePosition > 0 && arr[holePosition - 1] > temp) {
arr[holePosition] = arr[holePosition - 1];
holePosition--;
}
arr[holePosition] = temp;
}
}
void printArray(const int arr[], size_t size) {
for(size_t i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
};
int main(int argc, const char * argv[])
{
// Declare an object of class geeks
InsertionSortExample obj;
int arr[] = { 15, 3, 12, 6, -9, 9, 0 };
const size_t SIZE = sizeof(arr) / sizeof(*arr);
cout << "Before Sorting: ";
obj.printArray(arr, SIZE);
obj.insertionSort(arr, SIZE);
cout << "After Sorting: ";
obj.printArray(arr, SIZE);
return 0;
}
C++ Output Screen
Before Sorting: 15 3 12 6 -9 9 0
After Sorting: -9 0 3 6 9 12 15
Insertion sort implementation steps:
Let's take the input array as { 15, 3, 12, 6, -9, 9, 0 } and we can see how the Insertion sort is sorting the array.
- Split the array into two sub arrays namely sorted and un-sorted arrays,
- The first array was partitioned from a main array with only one element. It contains only the 0th indexed element, in other words the first item of a main array and it's always considered as a sorted array.
- The second array was partitioned from a main array and it has the remaining element except the first element (i.e. index position 0 to length - 1) and it's always considered as a un-sorted array.
- Transfer the leftmost item in a un-sorted array to a temporary variable and mark the position as empty and attach this empty position to the end of the sorted array
- Compare the temporary variable with an element in a sorted array from the right to left direction.
- Shift the position by one on the right hand side (i.e. shift the value to the empty place holder)
immediately only if the element is greater than the temporary variable and mark the place as an empty
and continue the comparison process till the temporary variable is greater than the items in the sorted item.
- Place the value of the temporary variable to the recently marked empty place holder.
- Apply the steps 2 and 3 until there is no more elements in un-sorted array.
Insertion Sort Implementation in C++ with explanation
C++ Input Screen
#include <iostream>
using namespace std;
class InsertionSortExample
{
// Access specifier
public:
void insertionSort(int arr[], size_t size) {
// Un-sorted array from position 1 to length -1
for(size_t i = 1; i < size; i++) {
// Take the left most item in an un-sorted array to temp variable
int temp = arr[i];
// Mark the left most position as empty or hole
int holePosition = i;
// Traverse the sorted array from right to left direction
// Move the item from the sorted array to the empty position (i.e. holePosition) only if the temp variable is less then
// Mark the current item's position as empty by decrementing the value by one
while(holePosition > 0 && arr[holePosition - 1] > temp) {
arr[holePosition] = arr[holePosition - 1];
holePosition--;
}
// Once the comparison done, move the value in temp variable to the lastly marked empty position
arr[holePosition] = temp;
}
}
void printArray(const int arr[], size_t size) {
// Loop the item and print each item in the console with white space seperated
for(size_t i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
};
int main(int argc, const char * argv[])
{
// Declare an object of class geeks
InsertionSortExample obj;
int arr[] = { 15, 3, 12, 6, -9, 9, 0 };
const size_t SIZE = sizeof(arr) / sizeof(*arr);
cout << "Before Sorting: ";
obj.printArray(arr, SIZE);
obj.insertionSort(arr, SIZE);
cout << "After Sorting: ";
obj.printArray(arr, SIZE);
return 0;
}
C++ Output Screen
Before Sorting: 15 3 12 6 -9 9 0
After Sorting: -9 0 3 6 9 12 15
BBMINFO
