Concept

How should a comparator handle an array of structure pointers with NULL values?

ComputerScienceOne / Sorting Pointers to Elements

"This is essentially equivalent to the string scenario: we have an array of pointers to be sorted, our comparator function then needs to deal with pointers to pointers. An example appears in Code Sample 25.5.\n\n/**\n\n* Orders two Student pointers according to the last name/first name\n\n*/\n\nint studentPtrLastNameCmp(const void *s1, const void *s2) {\n\n//we receive a pointer to an individual element in the array\n\n//but individual elements are POINTERS to students thus we cast\n\n//them as (const Student **) then dereference to get a pointer\n\n//to a Student!\n\nconst Student *a = *(const Student **)s1;\n\nconst Student *b = *(const Student **)s2;\n\nint result = strcmp(a->lastName, b->lastName);\n\nif(result == 0) {\n\nreturn strcmp(a->firstName, b->firstName);\n\n} else {\n\nreturn result;\n\n}\n\n}\n\nStudent **roster = (Student **) malloc(sizeof(Student *) * n);\n\n...\n\nqsort(roster, n, sizeof(Student *), studentPtrLastNameCmp);\n\nAnother issue when sorting arrays of pointers is that we may now have to deal with NULL elements. When sorting arrays of elements this is not an issue as a properly initialized array will contain non-null elements (though elements could still be uninitialized, the memory space will be valid). How we handle NULL pointers is more of a design decision. We could ignore it and any attempt to access a NULL structure will result in undefined behavior (or segmentation faults, etc.). Or we could give NULL values an explicit ordering with respect to other elements. That is, we could order all NULL pointers before non-NULL elements (and consider all NULL pointers to be equal). An example with respect to our Student structure is given in Code Sample 25.6.\n\nint studentPtrLastNameCmpWithNulls(const void *s1, const void *s2) {\n\nconst Student *a = *(const Student **)s1;\n\nconst Student *b = *(const Student **)s2;\n\nif(a == NULL && b == NULL) {\n\nreturn 0;\n\n} else if(a == NULL && b != NULL) {\n\nreturn -1;\n\n} else if (a != NULL && b == NULL) {\n\nreturn 1;\n\n}\n\nint result = strcmp(a->lastName, b->lastName);\n\nif(result == 0) {\n\nreturn strcmp(a->firstName, b->firstName);\n\n} else {\n\nreturn result;\n\n}\n\n}"

Related Ideas

How should a comparator handle an array of structure pointers with NULL values? | ComputerScienceOne | Bifalgorithm | Bifalgorithm