Сортировка списка

Зачем сортировать список

Сортировка упорядочивает записи по ключу: id, course, score или их комбинации. Для массива есть qsort, но для связного списка удобнее сортировать перецепкой узлов или сортировкой вставками.

В этой статье — два практичных подхода: вставками и слиянием. Оба могут быть устойчивыми: при равных ключах сохраняется исходный порядок.

Сортировка вставками

Идём по исходному списку и вставляем каждый узел в новый отсортированный список:

typedef struct
{
    int id;
    int course;
    double score;
} Student;

typedef struct Node
{
    Student data;
    struct Node *next;
} Node;

int less(Student a, Student b)
{
    if (a.score != b.score)
    {
        return a.score > b.score;   /* по убыванию */
    }
    return a.id < b.id;             /* tie-breaker */
}

Node *insert_sorted(Node *head, Node *node)
{
    if (head == NULL || less(node->data, head->data))
    {
        node->next = head;
        return node;
    }

    Node *p = head;
    while (p->next != NULL && !less(node->data, p->next->data))
    {
        p = p->next;
    }

    node->next = p->next;
    p->next = node;
    return head;
}

Node *insertion_sort(Node *head)
{
    Node *sorted = NULL;
    Node *p = head;

    while (p != NULL)
    {
        Node *next = p->next;
        sorted = insert_sorted(sorted, p);
        p = next;
    }

    return sorted;
}

Сложность — O(n²), но для учебных списков это нормально. Важно: узлы не копируются, а перецепляются.

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

Для больших списков лучше слияние: O(n log n). Список делится на две части, каждая сортируется, затем сливается.

Node *merge(Node *a, Node *b)
{
    Node dummy;
    Node *tail = &dummy;
    dummy.next = NULL;

    while (a != NULL && b != NULL)
    {
        if (less(a->data, b->data))
        {
            tail->next = a;
            a = a->next;
        }
        else
        {
            tail->next = b;
            b = b->next;
        }
        tail = tail->next;
    }

    tail->next = (a != NULL) ? a : b;
    return dummy.next;
}

Node *merge_sort(Node *head)
{
    if (head == NULL || head->next == NULL)
    {
        return head;
    }

    Node *slow = head;
    Node *fast = head->next;
    while (fast != NULL && fast->next != NULL)
    {
        slow = slow->next;
        fast = fast->next->next;
    }

    Node *right = slow->next;
    slow->next = NULL;

    Node *left_sorted = merge_sort(head);
    Node *right_sorted = merge_sort(right);

    return merge(left_sorted, right_sorted);
}

Составной ключ

Ключ задаётся функцией сравнения. Например, сортировка по course по возрастанию, затем по score по убыванию, затем по id:

int less(Student a, Student b)
{
    if (a.course != b.course)
    {
        return a.course < b.course;
    }
    if (a.score != b.score)
    {
        return a.score > b.score;
    }
    return a.id < b.id;
}

Если ключи равны, устойчивая сортировка сохраняет исходный порядок.

Сортировка двусвязного списка

Двусвязный список можно сортировать теми же идеями, но при перецепке нужно обновлять prev. Проще сначала расцепить список в односвязный, отсортировать, затем восстановить prev, но в учебной работе достаточно аккуратно обновлять оба указателя.

Частые ошибки

Документация

• Структуры
• Указатели
• malloc
• free

Что запомнить

1. Сортировка списка — это перецепка узлов, а не копирование данных.
2. Вставками — O(n²), слиянием — O(n log n).
3. Устойчивость сохраняет порядок при равных ключах.
4. Составной ключ задаётся функцией сравнения.
5. В двусвязном списке не забывайте prev.