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

Question

В этой задаче функция, которая получает указатель void на массив, число элементов и целое число, указывающее тип элементов, должна сортировать массив.Есть ли уловки, чтобы избежать написания того же кода 4 раза, как в следующем решении?

//type 1:short, 2:int, 3:float, 4:double
void Sort(void *values, int nValues, int type) {
    int i, j, temp;

    switch(type) {
    case 1: //short
    {
        short *ptr = (short *)values;
        for (i = 0; i < nValues - 1; i++)
            for (j = i; j < nValues; j++)
                if (ptr[i] > ptr[j]) {
                    temp = ptr[i];
                    ptr[i] = ptr[j];
                    ptr[j] = temp;
                }
        break;
    }
    case 2: // int
    {
        int *ptr = (int *)values;
        for (i = 0; i < nValues - 1; i++)
            for (j = i; j < nValues; j++)
                if (ptr[i] > ptr[j]) {
                    temp = ptr[i];
                    ptr[i] = ptr[j];
                    ptr[j] = temp;
                }
        break;
    }
    case 3: // float
    {
        float *ptr = (float *)values;
        for (i = 0; i < nValues - 1; i++)
            for (j = i; j < nValues; j++)
                if (ptr[i] > ptr[j]) {
                    temp = ptr[i];
                    ptr[i] = ptr[j];
                    ptr[j] = temp;
                }
        break;
    }
    case 4: // double
    {
        double *ptr = (double *)values;
        for (i = 0; i < nValues - 1; i++)
            for (j = i; j < nValues; j++)
                if (ptr[i] > ptr[j]) {
                    temp = ptr[i];
                    ptr[i] = ptr[j];
                    ptr[j] = temp;
                }
    }
    }
}

Answer 1

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

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

#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 s.С наивным пузырем, вроде algorthm, они останутся на месте, что может или не может быть уместным.При использовании других алгоритмов сортировки или только небольшого отклонения от этого поведение может быть другим, возможно, неопределенным.

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

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

Вот более эффективный подход, в котором алгоритм сортировки оставлен для функции библиотеки 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;
    }
}

Answer 2

Да, есть альтернатива.В стандартной библиотеке 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 - единственное значение, которое сравнивает неравномерно с самим собой, этот дополнительный код не влияет на целочисленную арифметику и должен быть оптимизирован путемкомпилятор.