Objective

Write qsort with the signature the C standard gives it: order the nmemb elements of size bytes stored at base, comparing any two of them with cmp, and move whole elements byte by byte because size is only known at run time.

Steps

• base points at the first element. There are nmemb of them, each exactly size bytes wide, laid out back to back, so element i starts at (char *)base + i * size.
• cmp takes the addresses of two elements. It returns a negative value when the first one belongs before the second, a positive value when it belongs after, and 0 when neither does. That sign is all you get, and a comparator is free to order things any way it likes, descending included.
• Rearrange the elements in place so that for every neighbouring pair, cmp(left, right) is at most 0. The function returns nothing.
• size is a run time value, so no typed temporary can hold an element. Swap through char * or unsigned char *, size bytes at a time. That is what carries the fields the comparator never reads along with the one it does.
• An nmemb of 0 or 1 is already ordered. Leave the buffer exactly as you found it and return.
• Read and write only the first nmemb elements. Whatever sits after them comes out byte for byte as it went in.
• qsort is not stable. Two elements the comparator calls equal may come out in either order, and nothing in Grademe observes that order: no test uses duplicate keys except one, where every key is identical and only the total of an uncompared field is checked.
• Grademe supplies the comparators and calls you with a size of 1 (char), 3 (fixed width tags), 4 (int), 8 (long) and 12 (a three field struct). An implementation that assumes one element width fails the moment the width changes.
• The largest test passes 100 elements, which any correct method clears in an instant.
• Name the function qsort, exactly as the standard does. Grademe renames it at compile time, so your definition never collides with the one already in the C library.

Objective

Write qsort with the signature the C standard gives it: order the nmemb elements of size bytes stored at base, comparing any two of them with cmp, and move whole elements byte by byte because size is only known at run time.

Steps

• base points at the first element. There are nmemb of them, each exactly size bytes wide, laid out back to back, so element i starts at (char *)base + i * size.
• cmp takes the addresses of two elements. It returns a negative value when the first one belongs before the second, a positive value when it belongs after, and 0 when neither does. That sign is all you get, and a comparator is free to order things any way it likes, descending included.
• Rearrange the elements in place so that for every neighbouring pair, cmp(left, right) is at most 0. The function returns nothing.
• size is a run time value, so no typed temporary can hold an element. Swap through char * or unsigned char *, size bytes at a time. That is what carries the fields the comparator never reads along with the one it does.
• An nmemb of 0 or 1 is already ordered. Leave the buffer exactly as you found it and return.
• Read and write only the first nmemb elements. Whatever sits after them comes out byte for byte as it went in.
• qsort is not stable. Two elements the comparator calls equal may come out in either order, and nothing in Grademe observes that order: no test uses duplicate keys except one, where every key is identical and only the total of an uncompared field is checked.
• Grademe supplies the comparators and calls you with a size of 1 (char), 3 (fixed width tags), 4 (int), 8 (long) and 12 (a three field struct). An implementation that assumes one element width fails the moment the width changes.
• The largest test passes 100 elements, which any correct method clears in an instant.
• Name the function qsort, exactly as the standard does. Grademe renames it at compile time, so your definition never collides with the one already in the C library.