Что такое рассорка пары?

Что такое «рассорка пары»?

Под «рассоркой пары» понимается упорядочивание набора упорядоченных пар (например, координат точек, записей вида (ключ, значение)) таким образом, чтобы сначала шли пары с меньшим первым компонентом, а при равных первых компонентах – с меньшим вторым.

Почему цепочки?

Цепочка (или связный список) позволяет эффективно вставлять и перемещать элементы без необходимости копировать большие блоки памяти. При сортировке пар цепочка даёт следующие преимущества:

• Линейная сложность O(n) при условии, что ключи находятся в ограниченном диапазоне (сортировка подсчётом через цепочки).
• Минимальные дополнительные затраты памяти – достаточно одного указателя на следующий элемент.
• Простота реализации в языках без встроенных динамических массивов (например, на C).

Алгоритм сортировки пар цепочками (вариант «сортировка подсчётом»)

Предположим, что первый компонент пары – целое число из диапазона [0, K]. Мы создадим массив из K+1 цепочек, где каждая цепочка хранит все пары с одинаковым первым компонентом, отсортированные по второму компоненту.

Шаги алгоритма

1. Инициализация: создать массив heads[0..K], заполненный NULL (начало каждой цепочки).
2. Распределение: пройти по всем парам (a_i, b_i) и вставить каждую пару в цепочку heads[a_i]. Вставка выполняется в конец цепочки (или в начало – не важно, так как позже будем сортировать внутри цепочки).
3. Сортировка внутри цепочек: для каждой непустой цепочки выполнить простую сортировку вставками по второму компоненту (так как длина цепочки обычно мала).
4. Сборка результата: пройти по массиву heads от 0 до K и вывести все элементы цепочек последовательно.

Псевдокод

function sortPairsByChains(pairs, K):
 // pairs – массив пар (first, second)
 // K – максимальное возможное значение первого компонента
 heads[0..K] = NULL

 // 1. Распределение по цепочкам
 for each (f, s) in pairs:
 node = new Node(f, s)
 node.next = heads[f]
 heads[f] = node // вставляем в начало цепочки

 // 2. Сортировка внутри каждой цепочки по второму компоненту
 for i from 0 to K:
 heads[i] = insertionSortBySecond(heads[i])

 // 3. Сборка результата
 result = empty list
 for i from 0 to K:
 cur = heads[i]
 while cur != NULL:
 append cur to result
 cur = cur.next
 return result

Функция сортировки вставками по второму компоненту

function insertionSortBySecond(head):
 if head == NULL or head.next == NULL:
 return head
 sorted = NULL
 cur = head
 while cur != NULL:
 next = cur.next
 sorted = sortedInsert(sorted, cur, bySecond)
 cur = next
 return sorted
function sortedInsert(sorted, node, bySecond):
 if sorted == NULL or bySecond(node) < bySecond(sorted):
 node.next = sorted
 return node
 else:
 cur = sorted
 while cur.next != NULL and bySecond(cur.next) <= bySecond(node):
 cur = cur.next
 node.next = cur;next
 cur.next = node
 return sorted

Пример на Python (используем простые классы для узлов)

Ниже демонстрируется работа алгоритма на наборе пар.

class Node:
 def __init__(self, first, second):
 self.first = first
 self.second = second
 self.next = None

def sort_pairs_by_chains(pairs, max_first):
 heads = [None] * (max_first + 1)

 # распределение
 for f, s in pairs:
 node = Node(f, s)
 node.next = heads[f]
 heads[f] = node

 # сортировка вставками внутри каждой цепочки
 def insertion_sort(head):
 sorted_head = None
 cur = head
 while cur:
 nxt = cur.next
 # вставляем cur в отсортированный список
 if sorted_head is None or cur.second < sorted_head.second:
 cur.next = sorted_head
 sorted_head = cur
 else:
 tmp = sorted_head
 while tmp.next and tmp.next.second <= cur.second:
 tmp = tmp.next
 cur.next = tmp.next
 tmp.next = cur
 cur = nxt
 return sorted_head

 for i in range(max_first + 1):
 heads[i] = insertion_sort(heads[i])
 # сборка результата
 result = []
 for i in range(max_first + 1):
 cur = heads[i]
 while cur:
 result.append((cur.first, cur.second))
 cur = cur.next
 return result

pairs = [(3, 5), (1, 2), (3, 1), (2, 4), (1, 3)]
sorted_pairs = sort_pairs_by_chains(pairs, max_first=3)
print(sorted_pairs)

Когда цепочки неэффективны?

Если диапазон первого компонента велик (например, до 10^9), создание массива цепочек становится непрактичным из‑за памяти. В таких случаях лучше использовать:

• Сортировку слиянием (O(n log n)) напрямую по парам.
• Дерево поиска (AVL, красно‑чёрное) или хеш‑таблицу с последующей сортировкой bucket‑ов.

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

Самое главное помнить, что выбор структуры данных должен соответствовать ограничениям задачи: если диапазон ключей мал – цепочки идеальны; если нет – обращайтесь к более универсальным методам сортировки.