C++ Program to Implement QuickSort using Templates

In this post, we will see how to implement quicksort using templates. The advantage of using templates function is that we don’t have to write a separate function to sort arrays of different datatypes. A single template function can be used to sort all types of arrays.

Program

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

// template function to find the position of pivot element
// last element is taken as pivot
template <typename T>
int Partition(T arr[], int start, int end){
	
	int pivot = end;
	int j = start;
	for(int i=start;i<end;++i){
		if(arr[i]<arr[pivot]){
			swap(arr[i],arr[j]);
			++j;
		}
	}
	swap(arr[j],arr[pivot]);
	return j;
	
}

// template function to perform quick sort on array arr
template <typename T>
void Quicksort(T arr[], int start, int end ){

	if(start<end){
		int p = Partition(arr,start,end);
		Quicksort(arr,start,p-1);
		Quicksort(arr,p+1,end);
	}
	
}

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

int main() {
	
	int arr[] = { 1 , 10 , 11 , 9 , 14 , 3 , 2 , 20 , 19, 43, 57, 3, 2 };
	int n = sizeof(arr)/sizeof(int);
	
	cout<<"Array Before Sorting: "<<endl;
	PrintArray(arr, n);
	
	Quicksort(arr,0,n-1);
	
	cout<<"Array After Sorting: "<<endl;
	PrintArray(arr, n);
		
}

Output

quicksort using template function in c++

Leave comment if you face any problem

Leave a Comment

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