Sorting array of structs by second field in C

Question

My professor recommended us to use qsort() to sort an array of structs. However, I have to come to find out that it is not stable. I know there are other posts about this topic, but none seem to give an easy fix to stabilize my sort. Is there a way that I could use qsort() for a second data field?

Here is my code:

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

struct Map * collect_values(int n, int *arr);
void sort_values(struct Map *ptr, int n);
void print(struct Map *print_struct, int n);

struct Map{
    int value, position;
};

int compare(const void *aptr, const void *bptr){
    int a = ((struct Map*)aptr)->value, b = ((struct 
Map*)bptr)->value;
return (a > b) - (a < b);
}

int main(){
    int size, i;
    scanf("%d", &size);
    int *arr = (int*) malloc(size*sizeof(int));
    struct Map *p = collect_values(size,arr);
    qsort(p,size,sizeof(struct Map),compare);
    print(p,size);
    free(p);
    free(arr);
    return 0;
}

struct Map * collect_values(int n, int *arr){
    int i, position = 0;
    struct Map *array = calloc(n,sizeof(*array));
    for(i = 0; i < n; i++){
        scanf("%d",&arr[i]);
        array[i].value = arr[i];
        array[i].position = position;
        position++;
    }
    return array;

}

void print(struct Map * print_struct, int n){
    int i;
    for (i = 0; i < n; i++){
        printf("%d : %d\n", print_struct[i].value, 
print_struct[i].position);
    }
}

The output now is:

How can I maintain the order of the duplicates? I spent a lot of time trying to figure out qsort() and so I'd like to keep it if possible.

EDIT I wasn't clear on the output I'm trying to get. Before sorting, the array of structs contains a value and the index of that value. So, the original array of structs looked like this:

After sorting, my code printed the above. However, what I was hoping for was this:

Where if the values in the first field are equal, then they need to be sorted by values in the second field, which will never be equal because they are the indexes.

Quicksort is not a stable sort, there's really no good way to bypass that fact. See e.g. this comparison table to find stable sorting algorithms. You have to implement it yourself though (unless you find a library which does it for you). — Some programmer dude
– Some programmer dude, Commented Sep 13, 2018 at 8:28
You will need to extend your compare function to include the second struct fields. — YesThatIsMyName
– YesThatIsMyName, Commented Sep 13, 2018 at 8:29
I don't think a stable sort is what you want, but rather you want to sort based on multiple fields: 3-way compare the first fields like a normal qsort comparision. If the fields are equal, return the result of comparing the second fields, otherwise return the result of comparing first fields. — Shawn
– Shawn, Commented Sep 13, 2018 at 8:31
Sorry, no. I just want to sort by multiple fields. How can I do that? — quazi_moto
– quazi_moto, Commented Sep 13, 2018 at 8:58

user3386109 · Accepted Answer · 2018-09-13 09:05:05Z

6

Since the struct has a position member that represents the initial array ordering, you can easily emulate a stable sort. In the comparison function, if the two value members are equal, then return an ordering based on the position members, like this:

int compare(const void *ptr1, const void *ptr2)
{
    const struct Map *aptr = ptr1;
    const struct Map *bptr = ptr2;

    if (aptr->value == bptr->value)
        return (aptr->position > bptr->position) - (aptr->position < bptr->position);
    else
        return (aptr->value > bptr->value) - (aptr->value < bptr->value);
}

answered Sep 13, 2018 at 9:05

user3386109

35k7 gold badges52 silver badges69 bronze badges

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

1 Comment

WhozCraig Over a year ago

You know, you're absolutely right. After you stated that I did some research, and even though GNU recommended that technique for mimicking stable-sort with their qsort, what you pointed out makes sense. I'll retract that comment. And thanks for making me think about it.

Collectives™ on Stack Overflow

Sorting array of structs by second field in C

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related