функция сортировки для нескольких типов в C с использованием пустого указателя и аргумента типа

1123 Да, есть альтернатива. В стандартной библиотеке C уже есть функция под названием qsort (которая, вероятно, является сокращением быстрой сортировки, но это может быть и любой другой алгоритм сортировки). Чтобы использовать эту функцию, вы передаете ей массив, количество элементов в массиве, размер каждого элемента и функцию сравнения.

Вам просто нужно написать функцию сравнения для каждого типа данных, как показано в примере на этой странице.

Если вы хотите объединить 4 функции сравнения в одну функцию, вам нужно передать некоторую контекстную информацию в функцию сравнения. В этом случае вы больше не можете использовать qsort, но должны использовать qsort_s. Тогда ваша функция сравнения может выглядеть следующим образом:

#define compare(a, b) (((a) > (b)) - ((b) > (a)))
#define compare_ptr(type) (compare(*(type *)(p1), *(type *)(p2)))

static int compare_by_type(const void *p1, const void *p2, void *ctx) {
    int type = *(int *) ctx;
    switch (type) {
    case 1: return compare_ptr(short);
    case 2: return compare_ptr(int);
    case 3: return compare_ptr(float);
    case 4: return compare_ptr(double);
    default: return 0;
    }
}

#undef compare
#undef compare_ptr

int main(void) {
    int iarray[] = {1, 6, 4, 9, 55, 999, -33333};
    int sort_type = 1;

    qsort_s(iarray, 7, sizeof(int), compare_by_type, &type);
}

Это довольно продвинутый материал:

• передача указателей на функции вокруг
• выполнение указателей с указателями на произвольные типы
• с использованием макросов, которые принимают имена типов в качестве макропараметра
• , смешивающие логическую арифметику с целочисленной арифметикой

Но, в конце концов, добавить дополнительные типы в список тривиально До тех пор, пока они поддерживают оператор <.

Обратите внимание, что float и double даже не принадлежат к этой категории, поскольку их оператор < возвращает false, как только одно из чисел равно NaN, что означает «Не число», и приводит к из выражений, таких как 0.0 / 0.0. Как только у вас есть такое значение в массиве, поведение становится неопределенным. Функция сортировки может даже застрять в бесконечном цикле. Чтобы исправить это, измените определение макроса compare:

#define compare(a, b) (((a) > (b)) - !((b) <= (a)))

Теперь это выглядит еще сложнее, но работает для NaN. Например:

compare(NaN, 5)
= (NaN > 5) - !(5 <= NaN)
= false - !(5 <= NaN)
= false - !(false)
= false - true
= 0 - 1
= -1

Это означает, что NaN будет отсортирован в начало массива.

compare(NaN, NaN)
= (NaN > NaN) - !(NaN <= NaN)
= false - true
= -1

Черт возьми. Сравнение двух NaN должно было привести к 0, что означает, что они равны. Таким образом, в этом особом случае необходимо внести поправку:

#define compare(a, b) (((a) > (b)) - ((b) > (a)) - ((a) != (a) || (b) != (b)))

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

Вот два разных подхода к избежанию дублирования кода для вашей проблемы:

Если вы не можете использовать библиотечные функции или хотите сохранить свой алгоритм, вот решение с макросом препроцессора:

#define SORT_TYPE(values, nValues, type) do {\
        type *ptr = (type *)(values);        \
        int i, j, n = (nValues);             \
        for (i = 0; i < n - 1; i++) {        \
            for (j = i + 1; j < n; j++) {    \
                if (ptr[i] > ptr[j]) {       \
                    type temp = ptr[i];      \
                    ptr[i] = ptr[j];         \
                    ptr[j] = temp;           \
                }                            \
            }                                \
        }                                    \
    } while (0)

//type 1:short, 2:int, 3:float, 4:double
void Sort(void *values, int nValues, int type) {
    switch (type) {
      case 1: //short
        SORT_TYPE(values, nValues, short);
        break;
      case 2: // int
        SORT_TYPE(values, nValues, int);
        break;
      case 3: // float
        SORT_TYPE(values, nValues, float);
        break;
      case 4: // double
        SORT_TYPE(values, nValues, double);
        break;
    }
}

Примечания:

• Макрос SORT_TYPE может быть вызван с аргументами, которые имеют побочные эффекты, так как они оцениваются только один раз, но он все еще хрупок: сгенерированный код сломается, если аргументы были выражены в терминах имен переменных ptr, i, j или n. Можно попытаться сделать эти коллизии менее вероятными, назвав блочные переменные ptr__ или каким-либо другим искаженным способом, но это не полностью решает проблему. Макросы должны быть написаны с особой тщательностью и использоваться с осторожностью.

Значения

• NaN в массивах float и double могут обрабатываться неправильно, так как сравнения вернут false, если один или оба аргумента будут иметь значение NaN. С наивным пузырем, вроде algorthm, они останутся на месте, что может или не может быть уместным. С другими алгоритмами сортировки или с небольшим изменением этого, поведение может быть другим, возможно, неопределенным.

• Ваша реализация пузырьковой сортировки должна использовать i = j + 1 для незначительно лучшей производительности.

• Алгоритм пузырьковой сортировки очень неэффективен для больших массивов с временной сложностью O (N ^{2 )} .

Вот более эффективный подход, в котором алгоритм сортировки оставлен для функции библиотеки C qsort, и для каждого типа написана специальная функция сравнения:

int shortCmp(const void *aa, const void *bb) {
    short a = *(const short *)aa;
    short b = *(const short *)bb;
    return (b < a) - (a < b);
}

int intCmp(const void *aa, const void *bb) {
    int a = *(const int *)aa;
    int b = *(const int *)bb;
    return (b < a) - (a < b);
}

int floatCmp(const void *aa, const void *bb) {
    float a = *(const float *)aa;
    float b = *(const float *)bb;
    if (a != a || b != b) {
        /* sort NaN values to the end of the array */
        return (a != a) - (b != b);
    }
    return (b < a) - (a < b);
}

int doubleCmp(const void *aa, const void *bb) {
    double a = *(const double *)aa;
    double b = *(const double *)bb;
    if (a != a || b != b) {
        /* sort NaN values to the end of the array */
        return (a != a) - (b != b);
    }
    return (b < a) - (a < b);
}

//type 1:short, 2:int, 3:float, 4:double
void Sort(void *values, int nValues, int type) {
    switch (type) {
      case 1: //short
        qsort(values, nValues, sizeof(short), shortCmp);
        break;
      case 2: // int
        qsort(values, nValues, sizeof(int), intCmp);
        break;
      case 3: // float
        qsort(values, nValues, sizeof(float), floatCmp);
        break;
      case 4: // double
        qsort(values, nValues, sizeof(double), doubleCmp);
        break;
    }
}