Сортировка массива структур по нескольким полям

#c #алгоритм #сортировка #инспекция_кода

Решил задачу, вопрос на которую ранее сам задавал, хочу поделиться.

Задача: есть структура. У структуры три поля: фамилия (char) , имя(char), год рождения
(int).

Массив таких структур нужно отсортировать по каждому полю. Т.е. сначала все элементы
сортируем по фамилии, затем их сортируем по имени, и потом по году. 
Сначала у нас идут все элементы с фамилией на А, именем на А и минимальным годом
рождения среди тех у кого фамилия и имя на А... затем все с фамилией на В, именем на
В и минимальным годом рождением среди тех у кого имя и фамилия на В... Это общий принцип.

Массив структур автомобилей:

struct Car
{
    int idCar = 0; //порядковый номер элемента массива структур (id) 
    int size = 0; //размер элемента структур
    char regNum[7]; //поле с регистрационным номером
    char markCar[10];//марка автомобиля
    char modelCar[10]; //модель автомобиля
    int mileAge = 0; //пробег автомобиля
    int isEmpty = 0; //индикатор, если поля марка, модель, рег. номер и пробег пустые,
то  == 0
};


Функция по расширению, добавлению нового элемента в конец массива структур:

void addCar(Car *cars)
{

    int N = cars->size;
    N += 1;
    int id = N - 1;
    *cars = *(Car*)realloc(cars, (N+1) * sizeof(Car));
    for (int i = 0; i < N; i++)
    {
        (cars+i)->size = N;
    }
    (cars + id)->idCar = id;
    (cars + id)->isEmpty = 0;
    for (int i = 0; i<10; i++) (cars + id)->markCar[i] = '\0';
    (cars + id)->mileAge = 0;
    for (int i = 0; i<7; i++)(cars + id)->regNum[i] = '\0';
    for (int j = 0; j<10; j++) (cars + id)->modelCar[j] = '\0';
}


Функция по поиску структурированной переменной с наименьшим значением поля пробег:

void minMileAge(Car *cars)
{
    int min = INT_MAX;
    for (int i = 0; i < cars->size; i++)
    {
        if (min > (cars + i)->mileAge) min = (cars + i)->mileAge;
    }
    for (int j = 0; j < cars->size; j++)
    {
        if (min == (cars + j)->mileAge && (cars + j)->mileAge != 0)
        {
            printf("%d\n", (cars + j)->idCar);
            printf("Регистрационный номер: %s\n", (cars + j)->regNum);
            printf("Марка автомобиля: %s\n", (cars + j)->markCar);
            printf("Пробег автомобиля: %d\n", (cars + j)->mileAge);
        }
    }
}


Функции для сравнения структурированных переменных типа Car:

int my_strcmp(char *s1, char *s2)
{
    for (; *s1 != '\0' && *s2 != '\0' && (*s1 == *s2); s1++, s2++);
    return *s1 - *s2;
}
int cmpCar(Car *t1, Car *t2)
{
    int result;
    if ((result = my_strcmp(t1->markCar, t2->markCar))) return result;
    if((result = my_strcmp(t1->modelCar, t2->modelCar))) return result;
    if (result = (t1->mileAge - t2->mileAge)) return result;
    return my_strcmp(t1->regNum, t2->regNum);
}


Функция сортировки массива структур типа Car по 4 полям (методом вставок):

void sortCar(Car *cars)
{
    for (int i = 1; i < cars->size; ++i)
    {
        Car x = *(cars+i);
        int j = i;
        while (j > 0 && cmpCar((cars + j - 1), &x)>0)
        {
            *(cars+j) = *(cars + j - 1);
            j = j - 1;
        }
        *(cars + j) = x;
    }
    for(int l = 0; lsize; l++)
    {
        printf("ID номер автомобиля %d\n", (cars + l)->idCar);
        printf("Марка автомобиля: %s\n", (cars + l)->markCar);
        printf("Модель автомобиля: %s\n", (cars + l)->modelCar);
        printf("Пробег автомобиля: %d\n", (cars + l)->mileAge);
        printf("Регистрационный номер: %s\n", (cars + l)->regNum);
    }
}


И функция поиска элемента из массива структур, по полю,  содержащему искомую подстроку:

void allCar(Car *cars)
{
    int result;
    char sbm[10];
    printf("%s", "Введите значение для поиска: ");
    scanf("%s", &sbm);
    for (int i = 0; i < cars->size; i++)
    {
        if ((strstr((cars + i)->markCar, sbm)!=NULL || (strstr((cars + i)->modelCar,
sbm))!=NULL || (strstr((cars + i)->regNum, sbm)!=NULL)))
        {
            printf("id автомобилей содержащих значение %d\n", (cars + i)->idCar);
        }

    }
}

    

Ответы

Ответ 1

Реализация на C  - обычный qsort, только функция сравнения должна быть немного сложнее,
только и всего. Для типа наподобие

typedef struct Person {
    char f[20];
    char n[20];
    int y;
} Person;


имеем

int comp(const void * ptr1, const void * ptr2)
{
    Person * p1 = (const Person*)ptr1;
    Person * p2 = (const Person*)ptr2;

    int cmp = strcmp(p1->f, p2->f);
    if (cmp) return cmp;

    int cmp = strcmp(p1->n, p2->n);
    if (cmp) return cmp;

    return p1->y - p2->y;
}


Примерно так. Писал "на коленке", не комппилируя - просто показать принцип. Сравниваете
по первому полю, при равенстве - по второму, при равенстве - по третьему.

И никаких трех сортировок...


Ответ 2

Понятно, что нужно три функции, одна всех отсортирует по фамилии, вторая отсортирует
всех по фимени и третья всех по году.


Нет. Нужна одна функция, которая сортирует сразу по всему.


  Как реализовать сами функции сортировки понятно, а как задать последующие границы
сортировки по остальным полям?


В Си есть функция qsort, позволяющая сортировать массив переданным компаратором.
Подроблнее про компараторы (правда, на javascript) можно почитать в этом ответе. Только
отмечу, что вариант с || в си работать не будет, так что надо писать полностью.

Компаратор есть в ответе  @Harry.



Кстати, если бы надо было воспользоваться именно тремя сортировками, то надо было
бы, во-первых, использовать функцию стабильной сортировки (в си++ есть stable_sort,
в си, вроде, ничего нет), а во-вторых, применять сортировки в порядке, обратном желаемому:
сначала отсортировать всё по году, потом всё по имени (с равными именами останутся
упорядоченными по году), а потом по фамилии (с равными фамилиями останутся урпорядоченными
по имени и году).