C++ Program to Implement Insertion Sort using Templates

In this post, we will discuss how to implement insertion sort using templates.

Insertion sort is an in-place sorting algorithm. The array is divided into two-part. One sorted and other unsorted. The elements from unsorted parts are inserted into the sorted part one by one.

The advantage of implementing insertion sort using function templates is that we don’t have to write a separate function for different types of array.

Program

#include<iostream>
#include<vector>
using namespace std;

// insertion sort template function
// to sort array in ascending order
// n is the size of array
template <class T>
void InsertionSort(T arr[], int n)
{
	int i, j;
	T temp;

	for (int i = 1; i < n; ++i)
	{

		temp = arr[i];
		j = i - 1;

		while (j >= 0 && arr[j] > temp)
		{
			arr[j + 1] = arr[j];
			j = j - 1;
		}

		arr[j + 1] = temp;

	}
}

// template function to print array
// n: size of array
template <class T>
void PrintArray(T arr[], int n)
{
	for (int i = 0; i < n; ++i)
	{
		cout << arr[i] << ' ';
	}
	cout << endl;
}

int main()
{
	int intArray[] = { 5,8,4,2,8,9,10,34,0,32,2,1 };
	int n = sizeof(intArray) / sizeof(int);

	cout << "Integer Array Before Sort: ";
	PrintArray(intArray, n);

	InsertionSort(intArray, n);

	cout << "Integer Array After Sort: ";
	PrintArray(intArray, n);

	cout << "\n";

	char charArray[] = { 'A','Z','F','S','B','C','Q','O' };
	n = sizeof(charArray) / sizeof(char);

	cout << "Char Array Before Sort: ";
	PrintArray(charArray, n);

	InsertionSort(charArray, n);

	cout << "Char Array After Sort: ";
	PrintArray(charArray, n);

}

Output

C++ insertion sort template function

Read
C++ Find all subsets of an array
C/C++ Program to Transpose a Matrix
Matrix Addition using Recursion

Leave a Comment

Your email address will not be published. Required fields are marked *