×

Search anything:

# QuickSort using template in C++

#### C++ quick sort Algorithms Get this book -> Problems on Array: For Interviews and Competitive Programming

In this article, we have designed and implemented Quick Sort algorithm in C++ Programming Language to use the concept of template to make Quick Sort generic/ independent of input datatype.

1. Introduction
2. QuickSort algorithm
3. QuickSort with STL
##### 1. Introduction

There are few algorithms for sorting, QuickSort is one of the fastest way to do so. It's logic uses a partition function to split an array into two parts having the elements from the left part less than a "dividing line" and the second part having elements greater than that.

Computing a "dividing line", how C.A.R Hoare named it in his paper at the age of 22 when he was a student, will have some impact in the performance of the algorithm.

##### 2. QuickSort algorithm

The algorithm uses divide et impera technique, and calls the function recursively for the two parts spplited by the partition/pivot function.

Pseudocode

``````array A[n]
p <- 1
u <- n

QuickSort(A,p,u)
if p<u then
k <- pivot(A,p,u)
QuickSort(A,p,k-1)
QuickSort(A,k+1,u)
end if
end QuickSort

Pivot(A,p,u)
i <- p
j <- u
cp <- 0
cu <- -1

loop
if i < j
A[i] <-> A[j]
cp <-> -cu
end if
i <- i + cp
j <- j + cu
end loop

return j
end Pivot
``````

Study case: array = {5,3,2,8,7,1} A way of implementation
For the next implementation I have used a class which has at its private members a pointer to the array to be sorted and the partition/pivot function and, as public members a constructor which initializes the pointer and the quicksort function.

``````#include <iostream>

using namespace std;

class Sort
{
private:
int *array;

int pivot(int p, int u)
{
int i=p, j=u, count_p=0, count_u =-1;
int temp1, temp2;

while(i<j)
{
if(array[i] > array[j])
{
temp1 = array[i]; array[i] = array[j] ; array[j] = temp1;

temp2 = count_p; count_p = - count_u; count_u = - temp2;
}

i+= count_p;
j+= count_u;
}

return j;
}
public:
Sort(int *array)
{
this->array = array;
}

void quickSort( int p, int u)
{
if(p<u)
{
int k = pivot(p,u);
quickSort(p, k-1);
quickSort(k+1,u);
}
}
};

int main()
{
int a[] = {-142,100,-183,229,-10,225,-100,0,-1,1,10,5,-12,-1,0};
int length = 15;

Sort s(a);
s.quickSort(0,length-1);

for(int i=0;i<length; i++)
cout << a[i] << " ";

return 0;
}
``````

Output:

-183 -142 -100 -12 -10 -1 -1 0 0 1 5 10 100 225 229

#### 3. QuickSort with STL

An STL or a Standard Template Library is a way to work with different data types without changing the declaration of an object or function.
There are two types of templates

1. template functions
``````    template <class identifier> function_declaration;
template <typename identifier> function_declaration;
``````
1. class template
``````    template <class T>
class mypair {...};
``````

A way of implementation
For this tutorial I've used for simplicity the class template option as I already have a definition of a class, and the only thing that needs to be changed is the type of the array.

``````#include <iostream>

using namespace std;

template<class myType>
class Sort
{
private:
myType *array;

int pivot(int p, int u)
{
int i=p, j=u, count_p=0, count_u =-1;
int temp1, temp2;

while(i<j)
{
if(array[i] > array[j])
{
temp1 = array[i]; array[i] = array[j] ; array[j] = temp1;

temp2 = count_p; count_p = - count_u; count_u = - temp2;
}

i+= count_p;
j+= count_u;
}

return j;
}
public:
Sort(myType *array)
{
this->array = array;
}

void quickSort( int p, int u)
{
if(p<u)
{
int k = pivot(p,u);
quickSort(p, k-1);
quickSort(k+1,u);
}
}
};

int main()
{
int a[] = {-142,100,-183,229,-10,225,-100,0,-1,1,10,5,-12,-1,0};
int length = 15;

Sort<int> s(a);
s.quickSort(0,length-1);

for(int i=0;i<length; i++)
cout << a[i] << " ";

return 0;
}
``````

Output:

-183 -142 -100 -12 -10 -1 -1 0 0 1 5 10 100 225 229

The downsize of the previous example is that it works only for int type because at some point we will need to interchange the elements of the array and the comparation sign ">" works only for numbers.What if we will compare strings, or any other object ?

The next implementation will move forward the power of using template, and will answer to our question.
So, basically we will need to find a way to compare elements regarding of their data types.
My solution was to declare a pointer to a function pf as a member of our class that will point later to a comparation function defined separately for each case, maxNumber for numbers comparation and maxString for the string comparation. Of course it can be added any kind of rule of comparation as long as it will respect the logic: something needs to be less than something else.

A way of implementation

``````#include <iostream>

using namespace std;

template<class myType>
class Sort
{
private:
myType *array;
bool (*pf)(myType *a, myType *b);

int pivot(int p, int u )
{
int i=p, j=u, count_p=0, count_u =-1;

myType temp1;

int temp2;

while(i<j)
{
if( pf( &array[i] , &array[j]) )
{
temp1 = array[i]; array[i] = array[j] ; array[j] = temp1;

temp2 = count_p; count_p = - count_u; count_u = - temp2;
}

i+= count_p;
j+= count_u;
}

return j;
}
public:
Sort(myType *array)
{
this->array = array;
}

void quickSort( int p, int u)
{
if(p<u)
{
int k = pivot(p,u);
quickSort(p, k-1);
quickSort(k+1,u);
}
}

void setMaxFunction(bool (*pf)(myType *a, myType *b))
{
this->pf = pf;
}
};

bool maxNumber(int *a, int *b)
{
return *a > *b;
}

bool maxString(string *a, string *b)
{
return a->compare(*b)>0 ? true : false;
}

int main()
{
int a[] = {-142,100,-183,229,-10,225,-100,0,-1,1,10,5,-12,-1,0};
int length = 15;

Sort<int> s1(a);
s1.setMaxFunction(maxNumber);
s1.quickSort(0,length-1);

for(int i=0;i<length; i++)
cout << a[i] << " ";

cout<<endl;

string ss[] = {"Ana","has","blue","eyes"};
length = 4;

Sort<string> s2(ss);
s2.setMaxFunction(maxString);
s2.quickSort(0,length-1);

for(int i=0;i<length; i++)
cout << ss[i] << " ";

return 0;
}
``````

Output:

-183 -142 -100 -12 -10 -1 -1 0 0 1 5 10 100 225 229
Ana blue eyes has

With this article at OpenGenus, you must have the complete idea of implementing Quick Sort in C++ Programming Language using the concept of template.