Selection sort (C Plus Plus)

From LiteratePrograms

Other implementations: C | C++ | C# | Erlang | Haskell | Java | Python, arrays

This is an implementation of selection sort in the C++ language using templates. Selection sort is a simple but inefficient sort which operates by repeatedly extracting the minimum from the list of remaining unsorted elements until none are left. Visit the article Selection sort (C) discusses several other implementations that also compile as C++.

Contents 1 Arrays 2 Random access containers 3 Files 4 Test driver 5 Performance

Arrays

Assuming you're already familiar with the algorithm and the first basic implementation in Selection sort (C), generalizing these using templates is simple: we just replace the element type by a template parameter T:

<<template array sort with one template parameter>>=
template < typename T >
void selection_sort_array(T a[], int num_elements)
{
    for(int sorted_size=0; sorted_size < num_elements; sorted_size++)
    {
        int min_element_index = sorted_size;
        T min_element_value = a[sorted_size];
        for(int i=sorted_size+1; i<num_elements; i++)
        {
            if (a[i] < min_element_value)
            {
                min_element_index = i;
                min_element_value = a[i];
            }
        }
        a[min_element_index] = a[sorted_size];
        a[sorted_size] = min_element_value;
    }
}

More generally, we can pass a comparator as a second template parameter allowing us to sort any type using any strict weak ordering, permitting the ordering of the same data in multiple ways:

<<template array sort>>=
template < typename T, typename compare_less >
void selection_sort_array(T a[], int num_elements)
{
    for(int sorted_size=0; sorted_size < num_elements; sorted_size++)
    {
        int min_element_index = sorted_size;
        T min_element_value = a[sorted_size];
        for(int i=sorted_size+1; i<num_elements; i++)
        {
            if (compare_less(a[i], min_element_value))
            {
                min_element_index = i;
                min_element_value = a[i];
            }
        }
        a[min_element_index] = a[sorted_size];
        a[sorted_size] = min_element_value;
    }
}

We can now sort an integer array by simply passing an array and a number of elements, and the compiler will determine the necessary template parameters:

int a[] = {5, 2, 4, 1, 3};
selection_sort_array(a, 5);

Random access containers

The above is fine for sorting arrays, but what if you want to sort a std::vector, or some other random access container? In this case, our best bet is to use the same interface as std::sort, taking a begin iterator, an end iterator, and a comparator. We take advantage of the fact that any two random access iterators can be subtracted to compute the number of elements, and we take advantage of the fact that we can add an arbitrary offset to any random access iterator to index by replacing "a[i]" with "*(start + i)":

<<template generic sort>>=
template < typename RandomIterator, typename compare_less >
void selection_sort(RandomIterator start, RandomIterator end)
{
    int num_elements = end - start;
    for(int sorted_size=0; sorted_size < num_elements; sorted_size++)
    {
        int min_element_index = sorted_size;
        for(int i=sorted_size+1; i<num_elements; i++)
        {
            if (compare_less(*(start + i), *(start + min_element_index)))
            {
                min_element_index = i;
            }
        }
        std::swap(*(start + min_element_index) = *(start + sorted_size));
    }
}

Also, since we no longer have access to the element type T, we can't easily declare a temporary variable of this type. We get around this by just comparing to the array element in place and relying on std::swap to exchange the elements, which requires the algorithm header:

<<type definition headers>>=
#include <algorithm>

For convenience, we define an overload of the template with only one template parameter that explicitly uses "<":

<<template generic sort with one template parameter>>=
template < typename RandomIterator >
void selection_sort(RandomIterator start, RandomIterator end)
{
    int num_elements = end - start;
    for(int sorted_size=0; sorted_size < num_elements; sorted_size++)
    {
        int min_element_index = sorted_size;
        for(int i=sorted_size+1; i<num_elements; i++)
        {
            if (*(start + i) < *(start + min_element_index))
            {
                min_element_index = i;
            }
        }
        std::swap(*(start + min_element_index), *(start + sorted_size));
    }
}

We can now sort an array or vector using this same template:

int a[5];
vector<int> v;
//...
selection_sort(a, a + 5);
selection_sort(v.begin(), v.end());

Files

We can wrap these two implementations up in a header file for reuse. Templates always go entirely in header files, since they don't define anything until they're instantiated.

<<selection_sort.hpp>>=
#ifndef SELECTION_SORT_HPP_
#define SELECTION_SORT_HPP_
type definition headers
template array sort
template generic sort
template generic sort with one template parameter
#endif

This completes the implementation.

Test driver

This test drivers sorts a small array and a small vector using the second implementation. It tests the result to ensure that it is ordered.

<<selection_sort_test.cpp>>=
#include <iostream>
#include <vector>
#include <stdlib.h>   // for atoi(), rand()
#include "selection_sort.hpp"
using std::cout;
using std::endl;
int main(int argc, char* argv[])
{
    int num_elements = atoi(argv[1]);
    int* a = new int[num_elements];
    for (int i=0; i<num_elements; i++)
    {
        a[i] = rand();
    }
    selection_sort(a, a + num_elements);
    for (int i=1; i<num_elements; i++)
    {
        if (a[i] < a[i-1])
        {
            cout << "ERROR" << endl;
        }
    }
    std::vector<int> v;
    for (int i=0; i<num_elements; i++)
    {
        v.push_back(rand());
    }
    selection_sort(v.begin(), v.end());
    for (int i=1; i<num_elements; i++)
    {
        if (v[i] < v[i-1])
        {
            cout << "ERROR" << endl;
        }
    }
    return 0;
}

Performance

Performance can be expected to be comparable to the results listed at Selection sort (C)#Performance, since the implementation used there was very similar and also specialized for a certain type. The general conclusion is that C++'s std::sort outperforms it for all but the smallest lists (<1000 elements), and for the smallest lists it is still outperformed by the equally simple insertion sort. Don't use it.

Download code