Templates and Sorting

[chili5]

C++ Templates

Templates allow you to write a function once that works on any data type. The idea of templates is used in the container classes in the STL.

Why would this be useful?

Consider you create a function selectSort that sorts an array of items using the selection sort algorithm. When you define this function you would define the data type that it uses when you write it. Say you write it to sort an array of integers. Great, now you can sort an array of integers using the selection sort. What if you want to sort an array of doubles? You would have to define a second function called selectSort2 that sorts an array of floats.

So you would have to define lots of sort methods. Now say your program doesn't run fast off with the 0(n^2) selection sort and you want to use the quick sort instead. You would have to modify all of those functions. This becomes impossible to maintain. Another problem, say you want to sort a vector? You would then have to write the function to sort a vector. This becomes imposssible to manage when you start creating array of objects.

This is where templates are useful. You write the function once and let the compiler compile several different versions of the function that are needed. This makes modification so much easier.


The Selection Sort

Let us first take a look at the selection sort. This is a very basic algorithm.

Input: a sequence of n items
Output: a sequence of n items such that arr[0] < arr[1] < arr[2] ... arr[n-1]

How does this work? The selection sort makes n-1 passes through the array. On each pass through the array it finds the next smallest item in the array and keeps track of the index of the smallest item.

Once we get to the end of the inner loop, if iMin is equal to i, then we know that the smallest item is at the beginning of the loop, so we don't do any swapping of items. Otherwise we introduce a temporary variable that is used to store one of the previous items, so we can swap the items in the array.

Here is the code for the selection sort for an array of integers.

/**
@param	arr	
			The array of data to be sorted in ascending order. It contains n items.
@param	n	
			The number of items in the array.
*/
void selectSort(int arr[], int n) {
     int iMin, nTemp;
     
     for (int i=0;i<n-1;i++) {
         iMin = i;
         for (int j=i+1;j<n;j++) {
             if (arr[j] < arr[iMin]) {
                iMin = j;         
             }    
         }    
         
         if (iMin != i) {
            // the smallest item is somewhere else in the array so move it to this position
            nTemp = arr[i];
            arr[i] = arr[iMin];
            arr[iMin] = nTemp;           
         }
     }     
}

Use this code to test the function:

int nums[6] = {3,2,4,5,6,7};
    
selectSort(nums, 6);
    
for (int i=0;i<6;i++) {
    cout << nums[i] << " ";    
}
cout << endl;

This code simply sorts the array and outputs the array.

Let us take a look at how this actually works.

Consider this array:

3 2 5 7 -1 4

We are going to use the above sorting algorithm on this array. So the function call for this array would be:

int arr[6] = {3,2,5,7,-1,4};

selectSort(arr,6);

First pass: we start at index 0 and locate the smallest item which we find at index 4. So we swap the item at index 4 with the item at index 0.

This gives us the array:
{-1,2,5,7,3,4}

On the second pass when i = 1 we look through the array ranges [i+1,n). I set iMin = to 1 and compare each item with the value at index iMin. If I find a smaller item, I move the index of the smaller item into iMin. On this comparison we find that iMin is 1. Since iMin is the same as the current i, the smallest item is already in the correct place. You can confirm this by looking at the array. Is 2 in the correct spot in the sorted array?

Third pass:

we identify that 3 (located at index 4) is the smallest item in the aray, and we swap it with the value at index 2. Our new array becomes:

{-1,2,3,7,5,4}

Pass four:

Looking at the last 3 items we notice that 4 is the smallest item is at index 5 so we swap index 5 and index 3. This gives us this array:

{-1,2,3,4,5,7}

Pass five:

We look at index 4 and find the smallest item in the subset {5,7}. We notice that 5 is already in the correct place, so we do not move it.

Now we are done. Wait! We didn't look at the last item? Well think about why should we? If we looked at item at index 5, we would have a subset of {7}. There is only one number in the subset. Thus a subset of 1 is already sorted.

This tutorial is not about analysis but if we did an analysis we would note that the running time is 0(n^2).

Writing a generic function

The problem with the above function was mentioned earlier. It only works on integer arrays. To get around this we are going to write a template function that works with any data type (provided it supports the < operator). All primitives should support this and if objects overload the operator < then we can use them also.

The template function begins with a line

template<typename T>

This line declares that we are using a template parameter called T that the compiler should replace with an appropriate type at runtime. The only changes that will be made in the implementation of the function are the parameter list and the change of data type for the temporary variable.

Instead of declaring an array of type int, we will declare an array of type T. This is what allows the method to accept an array of any data type. So we get this line:

void selectSort(T arr[], int n) {

This declares that a function called selectSort should be declared and the array can be of any type. When the compiler calls the selectSort method with an int array it creates a function that works on integer arrays. The other change we need to make is the temporary variable. It should be declared as type T not type int. If we call the selectSort function using an array of Cars, we need a temporary Car so we can swap them. The Car is an object and it must overload the < operator or it will not work.

So instead of:

int nTemp;

We write:

T temp;

That is it. Two small changes and you have a selection sort method that works on any array (provided the data type used supports the < operator). The function looks like this:

template<typename T>
void selectSort(T arr[], int n) {
     int iMin;
     // a temporary variable used to sort the array. 
     // Notice it uses the type T that was defined in the template parameters?
     T temp;      
     
     for (int i=0;i<n-1;i++){
         iMin = i;
         for (int j=i+1;j<n;j++) {
             if (arr[j] < arr[iMin]) {
                iMin = j;           
             }
         } 
         if (iMin != i) {
            // the smallest item is somewhere else in the array so move it to this position
            temp = arr[i];
            arr[i] = arr[iMin];
            arr[iMin] = temp;           
         }   
     }
}

Delete the previous function we made that was of type int and replace it with the template version. You can test that the code still works by using this code:

int nums[6] = {3,2,4,5,6,7};
    
selectSort(nums, 6);
    
for (int i=0;i<6;i++) {
    cout << nums[i] << " ";    
}
cout << endl;

Now change the array nums to a float array and change the values and run it again. Try this code:

float nums[6] = {3.2,2.1,4.2,5.6,6.8,7.3};
    
selectSort(nums, 6);
    
for (int i=0;i<6;i++) {
	cout << nums[i] << " ";    
}
cout << endl;

It should still sort it in ascending order.


Sorting Objects

We will use this class to demonstrate how to sort array objects.

#include <iostream>

using namespace std;

class rect {
      public:
             int nArea;
             int nLength;
             int nWidth;
             
             rect::rect(int width = 0, int length = 0) {
                  nWidth = width;
                  nLength = length;
             }
             
             void calcArea() {
                  nArea = nLength * nWidth;     
             }
             
             void output() {
                  cout << nArea << " ";     
             }
			 
			 bool operator<(const rect& r1) const {
                  return nArea < r1.nArea;
             }
};

Place it in a file called rect.h and include it in your main class using #include "rect.h".

Let us see that this function works for sorting objects as well. We will also briefly note operator overloading. Add this code to your file:

// demonstrating sorting an array of objects
rect shapes[6];

shapes[0] = rect(3,2);
shapes[1] = rect(4,3);
shapes[2] = rect(5,3);
shapes[3] = rect(8,3);
shapes[4] = rect(9,4);
shapes[5] = rect(3,1);

We declare an array of 6 rectangles and initialize the object with some values using the constructor. Now we are going to sort this array using the area field. We overloaded the < operator which compares the area of the current object with an area of a second object. If the current objects area is less than the area of a second rectangle's area we return true. This overloaded operator is what allows us to sort the rectangles. When we sort them we are sorting them based on their area.

Try this code after the array is declared:

selectSort(shapes,6);
    
for (int i=0;i<6;i++) {
	cout << "Width: " << shapes[i].nWidth << " Length: " << shapes[i].nLength;  
	cout << " Area: " << shapes[i].nArea << endl;
}
cout << endl;

When you run it you will notice that the rectangles are sorted in ascending order by area. This is similar to using the comparator in Java.

The topic of operator overloading is a topic for another day.

This is more of a practical explanation of templates. You can read more about templates here.

The idea of templates parallels generics in the Java programming language.

Enjoy!

My Dev C++ project is uploaded as a zip file since I can't upload .h files.

[Jordan]

Very informative! +rep

[MathX]

Beautiful. I am wordless indeed

[Vswe]

Nice work. +rep

[WingedPanther]

Excellent job! +rep

[John]

Very nice. It has been a while since I've worked with C++ but you might want to pass the array by reference - I think you create a duplicate copy of the array in memory each time the function is called.

[chili5]

I'm not sure about that. Aren't arrays passed by reference which is why a void method sorts the array. Any changes made in the function are made in the calling function?

[John]

Void is the return type. Which is a good indicator one of the parameters might be mutated, but it does not imply that. I believe in C++ arrays are automatically passed by reference thanks to the compiler.

[WingedPanther]

Arrays can be passed by reference or by value. It does look you aren't getting the results passed back from your function.

[Brandon W]

Very nice tutorial mate, I have down templates yet so this should make it a lot easier when I do

+rep