Generic Ordering Function For Structures in C

user_11783370 0
Viewed 101

So I have this problem. I am supposed to create some ordering functions to be used in a generic sort routine in C. I have all but one function working. This function is supposed to be used as an ordering function for structures. The code should put the list in order by year.

Here is code for two helper functions that have been pre-written and used for the sorting routine:

static
void swap(void **left, void **right) {
    void *temp = *left;
    *left = *right;
    *right = temp;
}

void sort_array(void *Array[], unsigned size, int (*ordered)(void *, void *))
{
    int i;
    int have_swapped = 1;

    while (have_swapped) {
        have_swapped = 0;
        for (i = 0; i < size - 1; ++i ){
            if (ordered(Array[i], Array[i+1])) {
                swap(&Array[i], &Array[i+1]);
                have_swapped = 1;
            }
        }
    }
}

Then there is this function, also pre-written used in main to test.

int main() {
    int i;
    int status = EXIT_SUCCESS;

    sort_array((void**)data, data_size, &ordered_structures);

    for (i = 0; i < data_size - 1; ++i) {
        if (data[i]->year > data[i+1]->year) {
            fprintf(stderr,
                    "\"%s\" and \"%s\" are out of order\n",
                    data[i]->name,
                    data[i+1]->name);
            status = EXIT_FAILURE;
        }
    }

    return status;
}

The structure is simple.

struct automobile {
    const char *name;
    unsigned year;
    unsigned price;
};

So these are the helper functions that are used. All I have to do is to write a function that will be used in ordering structures using these helper functions.

My solution compiles, however it is not achieving the desired results, my solution is still out of order. Here is what I have.

int ordered_structures(void *left, void *right) {
     const int *x = left;
     const int *y = right;
     if (x < y)
         return 0;
     else 
         return 1;
}

Any help is greatly appreciated

function-pointers pointers structure c
2 Answers

Your function will be called with 2 pointers to struct automobile objects and you are supposed to compare the year member of these objects:

// return true if swapping should occur. ie: if automobile structures
// are not ordered by their year member (name is inconsistent with semantics)
int ordered_structures(void *left, void *right) {
     const struct automobile *x = left;
     const struct automobile *y = right;
     return (x->year > y->year);
}

Note these remarks:

  • the name ordered_structures is inconsistent with the expected semantics: it returns true if the pointers should be swapped, that is if the objects are not ordered.
  • casting an array of pointers to struct automobile as (void **) (a pointer to an array of void pointers) is not portable. It will not work on architectures where pointers to different types have a different representation. Fortunately these architectures are extremely rare.
  • the & in &ordered_structures is redundant.
  • the types of data_size, i and the size argument in sort_array should be consistent. size_t seems a better choice.
  • the sorting algorithm (bubble sort) is inefficient for large arrays. The C library has a qsort function which uses a much more efficient method, but would take a different sorting function (different arguments and different return value semantics).
user_45932670

You're just comparing the pointers, not the values in the objects they're pointing to.

Use

if (*x < *y) {
    return 0;
}
else {
    return 1;
}

Incidentally since the comparison operators do return a boolean you can just write

return *x >= *y;

But you're saying these are

struct automobile {...}

then you need to convert the pointers to struct automobile * instead and compare members therein, so I guess perhaps

const struct automobile *x = left;
const struct automobile *y = right;
return x->price > y->price;

which would sort in ascending price order... and

const struct automobile *x = left;
const struct automobile *y = right;
return x->year > y->year;

for ascending year...

P.S. the prewritten code looks really bad, starting from the (void **) cast which just cannot be right - i.e. if that cast is needed for it to compile then the code is wrong, and if it is not needed then why it is there in the first place. And the sorting algorithm is bubble sort which is called the "generic bad sorting algorithm"...

user_9189590
Related