Сортировка массива структур по второму полю в C - PullRequest
Новая
       13

Сортировка массива структур по второму полю в C

0 голосов
/ 13 сентября 2018

Мой профессор рекомендовал нам использовать qsort() для сортировки массива структур.Тем не менее, я должен прийти, чтобы выяснить, что это не является стабильным.Я знаю, что есть другие посты на эту тему, но ни один из них не может легко исправить ситуацию.Есть ли способ, которым я мог бы использовать qsort() для второго поля данных?

Вот мой код: 

#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);
    }
}

Теперь вывод: 

-3 : 3
1 : 9
3 : 2
4 : 8
4 : 1
5 : 5
5 : 4
7 : 6
25 : 0
88 : 7

Как мне сохранить порядок дубликатов?Я потратил много времени, пытаясь выяснить qsort(), и поэтому я хотел бы сохранить его, если это возможно.

РЕДАКТИРОВАТЬ Я не понял, какой вывод я пытаюсь получить.Перед сортировкой массив структур содержит значение и индекс этого значения.Итак, исходный массив структур выглядел так: 

 25 : 0
  4 : 1
  3 : 2
 -3 : 3
  5 : 4
  5 : 5
  7 : 6
 88 : 7
  4 : 8
  1 : 9

После сортировки мой код распечатал вышеприведенное.Однако я надеялся на следующее: 

-3 : 3
1 : 9
3 : 2
4 : 1
4 : 8
5 : 4
5 : 5
7 : 6
25 : 0
88 : 7

Где, если значения в первом поле равны, их нужно отсортировать по значениям во втором поле, которые никогда не будут равны, потому что ониэто индексы.

1 Ответ

0 голосов
/ 13 сентября 2018

Поскольку структура имеет член position, который представляет начальный порядок массива, вы можете легко эмулировать стабильную сортировку. В функции сравнения, если два члена value равны, тогда вернуть порядок, основанный на членах position, например: 

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);
}
...