Course Task Sorting Example

/**
 * @brief Структура Stack реализует динамический список-стек.
 *
 * Для того, чтобы в стеке можно было хранить любые данные, в качестве типа переменной #inf используется void*.
 */
struct Stack
{
    struct Stack *next; ///< Указатель на следующий элемент
    void *inf;  ///< Информация, хранящаясяя в данном элементе
};

/**
 * @brief Тип FlightInformation предназначен для хранения информации о полёте.
 */
struct FlightInformation
{
    int id; ///< Номер рейса
    size_t cityId; ///< Номер целевого города в кодификаторе
    int distance;   ///< Расстояние от Донецка до целевого города
    int adultTicketCost;    ///< Стоимость взрослого билета
    int childTicketCost;    ///< Стоимость детского билета
    char departureTime[6];  ///< Время отправления
    char arrivalTime[6];    ///< Время прибытия
};

/**
 * @brief Находит длину стека за O(N).
 * @param beg Указатель на начало стека.
 * @return Длина стека.
 */
size_t StackLength(const struct Stack *beg)
{
    size_t size = 0;
    struct Stack *run = beg;
    while (run != NULL) {
        ++size;
        run = run->next;
    }
    return size;
}

enum FieldType { FieldType_Id = 1, FieldType_CityId, FieldType_Distance,
                 FieldType_AdultTicketCost, FieldType_ChildTicketCost,
                 FieldType_DepartureTime, FieldType_ArrivalTime };


/**
 * @brief Сравнивает заданное поле структур #left и #right.
 * @param fieldType Тип поля, которое нужно сравнить.
 * @return True, если заданное поле #left <= заданного поля #right, иначе False.
 */
Bool lessOrEqualThan(const struct FlightInformation *left, const struct FlightInformation *right, enum FieldType fieldType)
{
    int compResult = 0;

    switch (fieldType) {
    case FieldType_Id:
        return left->id <= right->id;
    case FieldType_CityId:
        return left->cityId <= right->cityId;
    case FieldType_Distance:
        return left->distance <= right->distance;
    case FieldType_AdultTicketCost:
        return left->adultTicketCost <= right->adultTicketCost;
    case FieldType_ChildTicketCost:
        return left->childTicketCost <= right->childTicketCost;
    case FieldType_DepartureTime:
        compResult = strcmp(left->departureTime, right->departureTime);
        return compResult <= 0;
    case FieldType_ArrivalTime:
        compResult = strcmp(left->arrivalTime, right->arrivalTime);
        return compResult <= 0;
    }

    return False;
}

/**
 * @brief Сортирует стек рейсов "школьной" сортировкой по заданному полю.
 * @param archiveStack Сортируемый стек.
 * @param fieldType Тип поля, по которому нужно сортировать.
 */
void sortArchiveBySchoolSort(struct Stack *archiveStack, enum FieldType fieldType)
{
    struct Stack *left, *right;

    // Стек уже отсортирован, если в нём 1 или 0 элементов
    if (StackLength(archiveStack) < 2)
        return;

    left = archiveStack;
    right = archiveStack->next;

    for (left = archiveStack; left->next != NULL; left = left->next) {
        for (right = left->next; right != NULL; right = right->next) {
            if (lessOrEqualThan((struct FlightInformation *)right->inf,
                                (struct FlightInformation *)left->inf,
                                fieldType)) {
                void *inf = left->inf;
                left->inf = right->inf;
                right->inf = inf;
            }
        }
    }
}

/**
 * @brief Сортирует стек рейсов сортировкой вставкой по заданному полю.
 * @param archiveStack Сортируемый стек.
 * @param fieldType Тип поля, по которому нужно сортировать.
 */
void sortArchiveBySelectionSort(struct Stack *archiveStack, enum FieldType fieldType)
{
    struct Stack *left, *right;

    // Стек уже отсортирован, если в нём 1 или 0 элементов
    if (StackLength(archiveStack) < 2)
        return;

    left = archiveStack;
    right = archiveStack->next;

    for (left = archiveStack; left->next != NULL; left = left->next) {
        struct Stack *min = left;
        for (right = left->next; right != NULL; right = right->next) {
            if (lessOrEqualThan((struct FlightInformation *)right->inf,
                                (struct FlightInformation *)min->inf,
                                fieldType)) {
                min = right;
            }
        }

        if (min != left) {
            void *inf = left->inf;
            left->inf = min->inf;
            min->inf = inf;
        }
    }
}