Insertion sort function with order switch

Question

I tried to write an insertion sort function that will switch between ascending and descending based on the sign of its argument (order). It works, but it doesn't look right because the conditional operator I used as a switch will add some overhead to each iteration of the inner loop. So I'd like to ask for your advice on how I could write a better version of my function.

void Array::sort(int order) //Array is a struct that contains a vector of pointers named vect, as well as this function.
{
  if (order==0) return;
  bool ascending = (order>0);
  int i,j;
  Data* buffer; //Data is a struct containing some variables, including the key that has to be sorted.
  for (i=1; i<_size; i++)
  {
    buffer = vect[i]; //A vector of pointers to Data objects declared in the Array struct.
    j=i-1;
    while ( j>=0 && (ascending?(vect[j]->key > buffer->key):(vect[j]->key < buffer->key)))
    {
      vect[j+1] = vect[j];
      j--;
    }
    vect[++j] = buffer;
  }
}

Answer 1

You essentially want to write two functions, each of which knows its sort order statically (ie, at compile time), and choose which one to call dynamically.

The simplest change is this:

// original code, templated
template <bool Ascending>
void Array::sort() {
  int i,j;
  Data* buffer;
  for (i=1; i<_size; i++) {
    buffer = vect[i];
    j=i-1;
    while (j>=0 && (Ascending?(vect[j]->key > buffer->key):(vect[j]->key < buffer->key)))
    {
      vect[j+1] = vect[j];
      j--;
    }
    vect[++j] = buffer;
  }
}

// original prototype
void Array::sort(int order) {
  if (order > 0)
    sort<true>();
  else if (order < 0)
    sort<false>;
}

Note that although there is still a ternary statement in the inner loop, it can easily be optimised away since Ascending is constant (just a different constant in each instantiation).

A cleaner way is to remove the ternary statement entirely, and and instead pass some kind of comparison function into the inner function template. We could pass a function pointer, or a lambda - I'm using the built-in function objects since they already do what we want.

// Comparitor is some type you can call to compare two arguments
template <typename Comparitor>
void Array::sort(Comparitor comp) {
  int i,j;
  Data* buffer;
  for (i=1; i<_size; i++) {
    buffer = vect[i];
    j=i-1;
    while (j>=0 && comp(vect[j]->key, buffer->key)) {
      vect[j+1] = vect[j];
      j--;
    }
    vect[++j] = buffer;
  }
}

// std::greater and less come from <functional>
void Array::sort(int order) {
  typedef decltype(vect[0]->key) KeyType; // or use the real type directly
  if (order > 0)
    sort(std::greater<KeyType>());
  else if (order < 0)
    sort(std::less<KeyType>());
}

Answer 2

One option is to use a template, and redefine your function as

template<class T> void Array::sort(T op)
{
    ...
    while ( j>=0 && op(vect[j]->key,buffer->key))
    ...
}

then you can call your sort with the appropriate sorting object

struct LessThan : public std::binary_function<int, int, bool>   {
    bool operator() (int x, int y) const { return x < y; }
};
struct GreaterThan : public std::binary_function<int, int, bool>    {
    bool operator() (int x, int y) const { return x > y; }
};

Array::sort(LessThan());

Answer 3

If you really want performance, you could write two functions, instead of one. But leads to duplication. This is where C++ shines with templates.