1

I have a lot of records formed by 4 parameters each one (id, field1, field2, field3). Records are contained in a pointer called records. My goal is to create an InsertionSort function in order to sort these records. The sorting will be done for every parameter of the record (through multiple calling). The trouble is that the function must be general. What can I write in parameters of InsertionSort function so that the pointer works?

main.c

struct fields{
    int id;
    char field1[20];
    int field2;
    float field3;
};

int main() {
struct fields *records = malloc(100000 * sizeof *records);

/* Here , I fill *records with values */

InsertionSort(records,field1,100000);     // I order by parameter "field1"
InsertionSort(records,id,100000);      // I order by parameter "id"
InsertionSort(records,field2,100000);     // I order by parameter "field2"
}

InsertionSort function

void InsertionSort(fields *records, char parameter ,int sizeofrecords) {
        int i, j;
        void* temp;
        for (i = 1; i < size; i++) {
            temp = records[i].parameter;   //this command doesn't work (records[i])
            j = i - 1;
            while (j >= 0 && records[j].parameter> temp) {
                records[j + 1].parameter= records[j].parameter;
                j--;
            }
            records[j + 1].parameter= temp;
        }
    }
Joshua
  • 40,822
  • 8
  • 72
  • 132
Peppino
  • 31
  • 8
  • Shouldn't it be `InsertionSort(struct fields *records, ...` instead of `InsertionSort(fields *records, ...`? Also why do you use a `void*`? And what is `parameter` in `records[i].parameter`? And why do you debug your code with 100000 records? Put 3 or 4 records for debuigging, it will make your life much easier. Anyway the question is very unclear, you are already passing a pointer into `InsertionSort`. – Jabberwocky Nov 09 '20 at 16:32
  • @Jabberwocky — I think the idea is that what is passed in `parameter` should identify the structure member which should be used when comparing the two records. As you know (but the OP probably does not), that is not possible in C. And even if it were, under the normal rules, you can't usefully compare strings with the `>` operator, so the `field1` comparison would not work well. I agree that 100,000 records is about four orders of magnitude too large for preliminary debugging work on the function. That's for stress-testing the implementation. – Jonathan Leffler Nov 09 '20 at 16:37
  • Yes, I used parameters for that motivation. Size is set to 100000 because I have to read a csv file with 20.000.000 records. It was just an example. Btw the trouble is that if I pass a pointer in this way , it doesn't work @JonathanLeffler – Peppino Nov 09 '20 at 16:53
  • You'd have to show the code to explain what doesn't work when you pass a pointer — I can't begin to guess what you're thinking of. However, I think my answer shows what you should do. It is certainly my best effort at helping you. Other options likely to be inferior — unless someone comes up with something devastatingly brilliant. – Jonathan Leffler Nov 09 '20 at 16:56
  • @Joshua — that's quite a rewrite of the title! – Jonathan Leffler Nov 09 '20 at 17:33
  • @JonathanLeffler: After determining that "pointer" referred to "parameter" I changed it so it clearly wasn't trying to pass `&fields[i].field1` or some other struct member. – Joshua Nov 09 '20 at 17:35

2 Answers2

3

Look at the design of standard C (and POSIX) qsort(). Pass a pointer to a comparator function to your InsertionSort() function in place of the char parameter argument. When you need to compare in the sort function, invoke the comparator on the two records to be compared. Write different comparators to sort on the different fields. A standard (qsort-compatible) comparator has the signature int comparator(const void *p1, const void *p2). You might be able to use const fields * as the argument type, but then you'd not be able to use the standard qsort() function.

Without debugging any other issues in your sort (I'm not sure whether there are any), you might end up with:

void InsertionSort(fields *records, int (*cmp)(const void *p1, const void *p2), int size)
{
    for (int i = 1; i < size; i++)
    {
        void *temp = &records[i];
        int j = i - 1;
        while (j >= 0 && (*cmp)(&records[j].parameter, temp) > 0)
        {
            records[j + 1].parameter = records[j].parameter;
            j--;
        }
        records[j + 1].parameter = temp;
    }
}

You can write just cmp(records[j].parameter, temp). I learned C long enough ago to prefer the older, more explicit notation for invoking a function via a function pointer. (I learned C in an era when the simpler notation was not an option.)

Your comparator functions might look like these (the other two are trivial variants on cmp_id):

static int cmp_id(const void *p1, const void *p2)
{
    const fields *v1 = p1;
    const fields *v2 = p2;
    // +1 if v1 > v2; -1 if v1 < v2; else 0
    return (v1->id > v2->id) - (v1->id < v2->id);
}

static int cmp_field1(const void *p1, const void *p2)
{
    const fields *v1 = p1;
    const fields *v2 = p2;
    return strcmp(v1->field1, v2->field1);
}

The numeric comparator (cmp_id) avoids overflow and branching. You could write:

if (v1->id > v2->id)
    return +1;
if (v1->id < v2->id)
    return -1;
return 0;

as the body of the function. It is simpler to understand. It can also be extended to deal with tie-breakers, so that if the id values are the same, you can compare the field1 strings or the values in field2 or field3. You simply add extra comparisons after the if statements and before the return 0;.

Warning: this code has not been anywhere near a compiler, much less tested. Caveat Lector.

Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
  • Incidentally there's a way to actually _do_ what he asked but it won't help him because not all parameters are the same type. – Joshua Nov 09 '20 at 16:47
  • @Joshua — are you thinking of using `offsetof()`, or something else. Ultimately, I think the comparator function is the best (most nearly correct) way to go in C. Most of the alternatives I can think of either end up with a number identifying which field(s) to compare and writing elaborate comparison code in the sort function, or in a function called from the sort function. – Jonathan Leffler Nov 09 '20 at 16:54
  • Exactly , this is my problem.. @Joshua – Peppino Nov 09 '20 at 16:54
  • Yes I'm thinking of `offsetof` but as I said I can't make it work because of the differing types so I'd use the comparator too. – Joshua Nov 09 '20 at 16:55
  • BTW his idea of tie breakers is to use a stable sort so that ties end up not swapped relative to each other. – Joshua Nov 09 '20 at 17:08
  • @Joshua I thought you were thinking of macros, e.g.: `#define InsertionSort(records, field, size) InsertionSort_((records), cmp_##field, (size))`. – Ian Abbott Nov 09 '20 at 17:54
  • @IanAbbott: Feel free to write it. – Joshua Nov 09 '20 at 17:55
  • @Joshua It wouldn't really gain much apart from not having to prefix the field name with `cmp_` in the function call. Hardly seems worth it! – Ian Abbott Nov 09 '20 at 17:57
2

So Peppino wants to know how to actually do it. Well, kinda. The problem is while we can pass the member, we can't pass the member's type so this will run incorrectly. If we had all the members being the same type instead this would work:

#include <stddef.h>

struct fields{
    int id;
    char field1[20];
    char field2[11];
    char field3[20];
};

void InsertionSort(fields *records, size_t parameter ,int size) {
    int i, j;
    struct fields temp;
    for (i = 1; i < size; i++) {
        temp = records[i];
        j = i - 1;
        while (j >= 0 && strnatsort((char *)records[i] + parameter, (char *)records[i] + parameter) > 0) {
            records[j + 1] = records[j];
            j--;
        }
        records[j + 1] = temp;
    }
}

InsertionSort(records,offsetof(fields, field1),100000);

where strnatsort does natural sort: How to implement a natural sort algorithm in c++?

Joshua
  • 40,822
  • 8
  • 72
  • 132