Функция сортировки вставок с переключателем порядка

Question

Функция сортировки вставок с переключателем порядка

Я попытался написать функцию сортировки вставки, которая будет переключаться между возрастанием и убыванием на основе знака ее аргумента (order). Это работает, но выглядит неправильно, потому что условный оператор, который я использовал в качестве переключателя, добавит некоторые издержки к каждой итерации внутреннего цикла. Поэтому я хотел бы попросить вашего совета о том, как написать лучшую версию своей функции.

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;
}
}

-1

algorithm c++insertion-sort sorting

Решение

Другие решения

Одним из вариантов является использование шаблона и переопределение вашей функции как

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

тогда вы можете вызвать свой сортировку с соответствующим объектом сортировки

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());

1

Если вы действительно хотите производительность, вы можете написать две функции вместо одной. Но приводит к дублированию. Здесь C ++ сияет шаблонами.

0

Источник

Accepted Answer

По сути, вы хотите написать две функции, каждая из которых знает свой порядок сортировки статически (т.е. во время компиляции) и выберите, какой из них вызывать динамически.

Самое простое изменение заключается в следующем:

// 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>;
}

Обратите внимание, что хотя во внутреннем цикле все еще есть троичное выражение, его можно легко оптимизировать, так как Ascending является постоянной (просто разные константы в каждом экземпляре).

Более чистый способ — полностью удалить троичное выражение и вместо этого передать какая-то функция сравнения во внутренний шаблон функции. Мы могли бы передать указатель на функцию или лямбду — я использую объекты встроенной функции, так как они уже делают то, что мы хотим.

// 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>());
}

2