3

Let's say I have structure like this:

typedef struct MyStruct{
  char *string1;
  int number1, number2, number3;
  char string2[11], string3[9];
  char *string4;
  char *string5;
}MyStruct;

Programs prompts user to choose by what field it should sort the data. I am having trouble thinking of a way to sort array effectively. Do I really need to write separate sorting functions for each field? There must be some other way, because writing 8 functions, where 2 would suffice, doesn't look rational.

Improve this question
3
  • Use stdlib's qsort function. Commented Jun 5, 2013 at 7:03
  • Sorry for not being clear. I am looking for a way to sort the array by not writing 8 functions for each seperate field. I mean, I could write one function to sort strings and one to sort integers and it could work for all the structure fields. I don't want to write 8 separate comparison functions. Commented Jun 5, 2013 at 7:11
  • 1
    @jamesdlin: he wants the user to be able to select which of the eight fields to sort on. Commented Jun 5, 2013 at 7:18

5 Answers 5

Reset to default
6

Look up qsort() from <stdlib.h>. It takes a comparator function. You can write separate comparator functions for the different sort orders, but still use the standard library qsort() to do the sorting.

For example:

int ms_cmp_string1(const void *vp1, const void *vp2)
{
    const MyStruct *ms1 = vp1;
    const MyStruct *ms2 = vp2;

    int cmp = strcmp(ms1->string1, ms1->string2);
    if (cmp != 0)
        return cmp;
    else if (ms1->number1 < ms2->number1)
        return -1;
    else if (ms1->number1 > ms2->number1)
        return +1;
    //...other comparisons as required...
    else
        return 0;
}

This is a decent outline for comparators. This one sorts on string1 and then by number1. You can either write variants that sort on different fields, or devise a scheme that applies the various possible tests in an order of your choosing. But the basic outline works pretty well and is suitable for passing to qsort() without any casts necessary.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

+1, of course. I'd make it static since it's often very locally scoped, too.
@unwind: yes, I would usually make the function static too, precisely because it is often unneeded outside its own source file.
I don't want to sort the array by each field of structure. I want to sort by just one of the fields, which is selected by an user.
OK; you can have a single comparison in a comparator function — that isn't a problem. I can think of various ways of writing a single comparator that includes all possible comparisons and chooses the correct one at run time. However, you should be aware that the comparator is often the expensive operation in the sort process, so it may be worth using 8 small specialized functions rather than one generalized function that uses a global variable of some sort to choose which comparison to execute. OTOH, if you need arbitrary sequences of the 8 comparisons, then you'd use a global array for that.
4

You don't need to write 8 functions if only 2 are needed. Build your own qsort function and send a last parameter containing the member offset to the compare function, then, in your compare function, cast pointer + offset to the right type.

Something like:

int comp_int(const void *pa, const void *pb, size_t offset)
{
    const int *a = (const int *)((const char *)pa + offset);
    const int *b = (const int *)((const char *)pb + offset);

    return *a - *b;
}

int comp_string(const void *pa, const void *pb, size_t offset)
{
    const char *a = (const char *)pa + offset;
    const char *b = (const char *)pb + offset;

    return strcmp(a, b);
}

void swap(void *v[], int a, int b)
{
    void *temp;

    temp = v[a];
    v[a] = v[b];
    v[b] = temp;
}

void sort(void *v[], int left, int right, size_t offset, int (*comp)(const void *, const void *, size_t))
{
    int i, last;

    if (left >= right) return;
    swap(v, left, (left + right) / 2);
    last = left;
    for (i = left + 1; i <= right; i++) {
        if ((*comp)(v[i], v[left], offset) < 0)
            swap(v, ++last, i);
    }
    swap(v, left, last);
    sort(v, left, last - 1, offset, comp);
    sort(v, last + 1, right, offset, comp);
}

offsetof can help

Improve this answer

Comments

1

Here is a sample of using qsort from my another answer:

struct stringcase { char* string; void (*func)(void); };

void funcB1();
void funcAzA();

struct stringcase cases [] = 
{ { "B1", funcB1 }
, { "AzA", funcAzA }
};

struct stringcase work_cases* = NULL;
int work_cases_cnt = 0;

// comparator function
int stringcase_cmp( const void *p1, const void *p2 )
{
  return strcasecmp( ((struct stringcase*)p1)->string, ((struct stringcase*)p2)->string);
}

// prepare the data for searching
void prepare() {
  // allocate the work_cases and copy cases values from it to work_cases
  qsort( cases, i, sizeof( struct stringcase ), stringcase_cmp );
}
Improve this answer

Comments

1

If you're using the GNU C library, there's an extension called qsort_r() that lets you pass an extra parameter to the comparison function.

Improve this answer

2 Comments

+1, good point, #define _GNU_SOURCE before #include <stdlib.h>
Note that BSD-based versions of Unix (macOS too) also have a qsort_r(), but the order of the arguments to both the qsort_r() function and the comparator that it calls are different. That's not to say you shouldn't use qsort_r(); you just need to be careful when porting to different systems, and there may be systems without either variant of the function.
1

Using some macros:

#include <stdio.h>
#include <stdlib.h>

struct data {
    int x, y, z;
};

#define comp(member) comp_##member
#define comp_build(member)                          \
int comp_##member(const void *pa, const void *pb)   \
{                                                   \
    const struct data *a = pa, *b = pb;             \
    return (a->member < b->member)  ? -1 : (a->member > b->member); \
}

comp_build(x)
comp_build(y)
comp_build(z)

int main(void)
{
    #define ROWS 3

    struct data v[] = {
        {3, 2, 1},
        {1, 3, 2},
        {2, 1, 3}
    };
    int i;

    puts("Unsorted");
    for (i = 0; i < ROWS; i++) printf("%d %d %d\n", v[i].x, v[i].y, v[i].z);
    qsort(v, ROWS, sizeof(struct data), comp(x));
    puts("Sorted by x");
    for (i = 0; i < ROWS; i++) printf("%d %d %d\n", v[i].x, v[i].y, v[i].z);
    puts("Sorted by y");
    qsort(v, ROWS, sizeof(struct data), comp(y));
    for (i = 0; i < ROWS; i++) printf("%d %d %d\n", v[i].x, v[i].y, v[i].z);
    puts("Sorted by z");
    qsort(v, ROWS, sizeof(struct data), comp(z));
    for (i = 0; i < ROWS; i++) printf("%d %d %d\n", v[i].x, v[i].y, v[i].z);

    return 0;
}
Improve this answer

1 Comment

Note that in general, if the values in the integer array can be very large and very small (large magnitude but negative), then the subtraction can give signed arithmetic overflow. That's not a problem with the sample data shown, of course. One way of avoiding overflow is: return (a->member > b->member) - (a->member < b->member); instead. That returns 1 if a->member is greater than b->member, -1 if the opposite is true, and 0 if the values are the same.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.