Generi c реализация InsertionSort с использованием пустых указателей

Question

Я работаю над этим проектом ADT, и мне нужно реализовать алгоритм сортировки вставок и убедиться, что он работает нормально в соответствующей тестовой функции, которая применяет алгоритм к массиву типа double, строке и структуре.

Я использую в качестве руководства этот псевдокод:

procedure InsertionSort(a, n)
   for i <- 1, (n-1) do
       j <- 1
       while (j>0) and (a[j] < a[j-1]) do
         Swap(a, j-1, j)
       end while
   end for
end procedure

Я не могу понять, в чем проблема. Тестовая функция выдает мне ошибку при первом assert () [in test_sort_algorithm (...) ], поэтому сообщает, что алгоритм не работает должным образом. Но я не могу понять, где ошибка. Я попытался воссоздать алгоритм для обычного массива, не используя указатель void, и все работает. Поэтому я думаю, что моя проблема в том, что я не понимал использование пустых указателей. Может кто-нибудь помочь мне понять, что не так с моим алгоритмом сортировки вставок?

Спасибо.

Это моя попытка:

/**
 * \brief Sorts the given array according to the insertion sort algorithm.
 *
 * \param base Pointer to the start of the input array.
 * \param n Number of elements in the input array.
 * \param size The size (in bytes) of each element of the array.
 * \param cmp Pointer to the comparison function used to sort the array in
 *  ascending order.
 *  The comparison function is called with two arguments that point to the
 *  objects being compared and must return an interger less than, equal to, or
 *  greater than zero if the first argument is considered to be respectively
 *  less than, equal to, or greater than the second.
 */
void upo_insertion_sort(void *base, size_t n, size_t size, upo_sort_comparator_t cmp)
{
    size_t i, j;

    unsigned char *ptr = base;

    for (i = 1; i <= n-1; i++)
    {
        j = i;

        while ( (j > 0) && (cmp(ptr+j*size, ptr+(j-1)*size) < 0) )
        {
            swap(ptr+(j-1)*size, ptr+j*size, size);
            j = j - 1;
        }
    }
}

void swap(void *a, void *b, size_t n)
{
    void *tmp = malloc(n);
    if (tmp == NULL) { abort(); }
    memmove(tmp, a, n);
    memmove(a, b, n);
    memmove(b, tmp, n);
    free(tmp);
}

upo_sort_comparator_t cmp - указатель на функцию сравнения. Объявление:

/** \brief Type definition for comparison functions used to compare two elements */
typedef int (*upo_sort_comparator_t)(const void*, const void*);

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

Код:

#define N 9

struct item_s
{
    long id;
    char *name;
};
typedef struct item_s item_t;

static double da[] = {3.0,1.3,0.4,7.8,13.2,-1.1,6.0,-3.2,78};
static double expect_da[] = {-3.2,-1.1,0.4,1.3,3.0,6.0,7.8,13.2,78.0};
static const char *sa[] = {"The","quick","brown","fox","jumps","over","the","lazy","dog"};
static const char *expect_sa[] = {"The","brown","dog","fox","jumps","lazy","over","quick","the"};
static item_t ca[] = {{9,"john"},{8,"jane"},{7,"mary"},{6,"anthony"},{5,"stevie"},{4,"bob"},{3,"ann"},{2,"claire"},{1,"alice"}};
static item_t expect_ca[] = {{1,"alice"},{2,"claire"},{3,"ann"},{4,"bob"},{5,"stevie"},{6,"anthony"},{7,"mary"},{8,"jane"},{9,"john"}};

/* Comparators */

static int double_comparator(const void *a, const void *b);
static int string_comparator(const void *a, const void *b);
static int item_comparator(const void *a, const void *b);

/* Test cases */
void test_sort_algorithm(void (*sort)(void*,size_t,size_t,upo_sort_comparator_t));
static void test_insertion_sort();


int double_comparator(const void *a, const void *b)
{
    const double *aa = a;
    const double *bb = b;

    return (*aa > *bb) - (*aa < *bb);
}

int string_comparator(const void *a, const void *b)
{
    const char **aa = (const char**) a;
    const char **bb = (const char**) b;

    return strcmp(*aa, *bb);
}

int item_comparator(const void *a, const void *b)
{
    const item_t *aa = a;
    const item_t *bb = b;

    return (aa->id > bb->id) - (aa->id < bb->id);
}

void test_sort_algorithm(void (*sort)(void*,size_t,size_t,upo_sort_comparator_t))
{
    int ok = 1;
    size_t i = 0;
    double *da_clone = NULL;
    char **sa_clone = NULL;
    item_t *ca_clone = NULL;

    ok = 1;
    da_clone = malloc(N*sizeof(double));
    assert( da_clone != NULL );
    memcpy(da_clone, da, N*sizeof(double));
    sort(da_clone, N, sizeof(double), double_comparator);
    for (i = 0; i < N; ++i)
    {
        ok &= !double_comparator(&da_clone[i], &expect_da[i]);
    }
    free(da_clone);
    assert( ok );

    ok = 1;
    sa_clone = malloc(N*sizeof(char*));
    assert( sa_clone != NULL );
    memcpy(sa_clone, sa, N*sizeof(char*));
    sort(sa_clone, N, sizeof(char*), string_comparator);
    for (i = 0; i < N; ++i)
    {
        ok &= !string_comparator(&sa_clone[i], &expect_sa[i]);
    }
    free(sa_clone);
    assert( ok );

    ok = 1;
    ca_clone = malloc(N*sizeof(item_t));
    assert( ca_clone != NULL );
    memcpy(ca_clone, ca, N*sizeof(item_t));
    sort(ca_clone, N, sizeof(item_t), item_comparator);
    for (i = 0; i < N; ++i)
    {
        ok &= !item_comparator(&ca_clone[i], &expect_ca[i]);
    }
    free(ca_clone);
    assert( ok );
}

void test_insertion_sort()
{
    test_sort_algorithm(upo_insertion_sort);
}

int main()
{
    printf("Test case 'insertion sort'... ");
    fflush(stdout);
    test_insertion_sort();
    printf("OK\n");

    return 0;
}