Сначала кажется, что сортировка - это тривиально. В Excel жмешь "Sort Smallest to Largest" и все хорошо. Ну или sorted() в питоне. Всё само делается.

Серьезное знакомство с сортировкой у меня произошло на курсах Яндекс.Практикума (Алгоритмы и структуры данных) года три назад. Хороший курс кстати. Тогда я начал постепенно осознавать что не все так просто.

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

Сортировка - один из самых фундаментальных алгоритмов на Земле.

Интересно, что сортировка - самая недавняя важная концепция в моём списке. Ранее в нем уже были: Множества, Плоские таблицы, Графы, Иерархии, Комбинаторика, Матрицы.

Ниже я описываю свой взгляд на сортировку. Надеюсь это позволит более широко посмотреть на "Её величество Сортировку".

Будет весело, поехали! :)

Содержание

База
Сортировка и ранг (rank)
Частичная сортировка
Многоуровневая сортировка
Соединение отсортированных списков (оптимизация)
Стабильность сортировки
Key vs сompare function
Total ordering
Нет транзитивности - беда
Топологическая сортировка
Сортировка по смыслу
Объединение сортировок в одну общую (усреднение сортировок)
Оценка качества предсказанной сортировки (RAG)
LLM пишет сортировку на VBA (учёт data types)
Линеаризация (поставить объекты в ряд)
Мера отсортированности списка
Множества (ordered set, sorted set)
Две заключительные мысли

1. База

Сортировка предполагает расположить набор объектов линейно (в ряд) в порядке возрастания/убывания. Поэтому часто в python или excel мы даже не задумываемся, что происходит при проведении сортировки.

Самый простой случай - сортировка строк (str), целых чисел (int), дробных чисел (float).

Сравнение строк (str) сводится к многоуровневой сортировке целых чисел, каждый символ строки приводится к его индексу (напр., через UTF-8). Ещё это называют лексикографическая сортировка.

ord('R')  # 82. Это номер символа в таблице кодировок UTF-8
ord('Ж')  # 1046
'R' < 'Ж'  # поэтому True
'ЖRЖ' < 'ЖЖЖ'  # True, уровни сравниваются последовательно слева направо
'P' < 'PP'  # True. Особое правило: наличие любого объекта больше, чем его отсутствие

Сравнение дробных чисел (float) логически тоже сводится к целым числам. Т.к. для компьютера дробных чисел конечное количество и их можно сопоставить с целыми числами (один-к-одному).

Сортировка целых чисел тривиальна. Интересно сказал Raymond Hettinger (youtube):

Бог изобрел целые числа, float уже люди напридумывали :)

Надо упомянуть, что сортировка бывает "по возрастанию (ascending - часто дефолт)" и "по убыванию (descending)".

Если у нас есть N объектов, то количество вариантов сортировок равно N! (факториал). Учитывая, что сортировка - это размещение (permutation) объектов, то иногда мы будем встречать комбинаторные понятия в контексте сортировок.

Ещё сортировка достаточно сильно связана с понятиям бинарного отношения на множестве (binary relation, wiki). Ниже в статье мы встретимся и с этой областью математики.

Понятия min/max - логически равны взятию первого/последнего элемента отсортированного списка. Хотя алгоритмы тут более легкие используются.

Обычно асимптотическая сложность сортировки O(N*logN). Хотя при наивной реализации становится O(N**2). Алгоритм сортировки ассиметричный в плане сложности. Т.к. проверить, что лист отсортирован можно за линейное время O(N).

Итак, всё просто. Или... нет, всё довольно-таки сложно! об этом ниже)

2. Сортировка и ранг (rank)

Иногда можно встретить функцию, которая возвращает ранг (rank) для каждого объекта в списке - df["some columns"].rank().

По сути, мы сортируем список. Далее нумеруем его, обычно с 1. Если в списке были дубликаты, они будут рядом. Далее, возможны разные подходы для получения ранга, см. код ниже (pandas rank):

import pandas as pd
l = [4, 1, 1, 1, 3, 3, 3, 5]  # изначальный список

#   [1, 1, 1, 3, 3, 3, 4, 5]  отсортированный список
#   [1, 2, 3, 4, 5, 6, 7, 8]  нумерация начиная с 1 в отсортированном списке

pd.Series(l).rank(method='average').values.tolist()
# [7.0, 2.0, 2.0, 2.0, 5.0, 5.0, 5.0, 8.0]  просто берем среднее всех позиций

pd.Series(l).rank(method='min').values.tolist()
# [7.0, 1.0, 1.0, 1.0, 4.0, 4.0, 4.0, 8.0]  берем минимальное

pd.Series(l).rank(method='max').values.tolist()
# [7.0, 3.0, 3.0, 3.0, 6.0, 6.0, 6.0, 8.0]  максимальное

pd.Series(l).rank(method='first').values.tolist()
# [7.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 8.0]  сохраняем позиции как есть

pd.Series(l).rank(method='dense').values.tolist()
# [3.0, 1.0, 1.0, 1.0, 2.0, 2.0, 2.0, 4.0]  особая, следующая группа +1 к предыдущей

Еще интересный момент, в numpy нет функции/метода rank. Но его можно имитировать. Мне не сразу удалось понять, почему это работает, см. код ниже:

import numpy as np

arr = np.array([4, 1, 1, 1, 3, 3, 3, 5])
np.argsort(np.argsort(arr))  # двойной argsort
# array([6, 0, 1, 2, 3, 4, 5, 7], dtype=int64)

# интересно, что это эквивалентно именно rank(method='first') в pandas
# только индексация с 0 получается

3. Частичная сортировка

Сортировка настолько часто встречается, что в numpy реализована оптимизированная функция np.partition. Эта функция обеспечивает, что только индексk будет содержать корректный объект с т.з. сортировки. Всё что слева - точно меньше, а справа больше. Но левая и правая часть не будут отсортированы внутри.

import numpy as np

arr = np.array([4, 1, 1, 1, 3, 3, 3, 5])

np.sort(arr)
array([1, 1, 1, 3, 3, 3, 4, 5])
array([0, 1, 2, 3, 4, 5, 6, 7])  # просто индекс

np.partition(arr, 6)
array([3, 1, 1, 1, 3, 3, 4, 5])
array([0, 1, 2, 3, 4, 5, 6, 7])  # просто индекс

# заметим, что по индексу 6 у нас стоит цифра 4
# это соответствует отсортированному состоянию

В ряде случаев, нам важно получить TOP 5 объектов, и нам не важна их сортировка. Этот алгоритм работает быстрее, чем полная сортировка.

4. Многоуровневая сортировка

Часто требуется сделать сортировку последовательно по нескольким уровням. Например, в таблице сначала сортируем по возрасту, если возраст совпадает, сортируем по имени.

В pandas максимально удобно это делать. Мы указываем набор столбцов в порядке сортировки [Возраст, Имя], далее указываем метод сортировки[ascending, descending].

Если мы работаем с list of tuples и хотим применить функцию sorted для многоуровневой сортировке, то поступают так:

# моделируем таблицу, как list of tuples
# 4 строки, 3 столбца (индекс везде с нуля)
l = [(1, 2, 3), 
     (1, 5, 8), 
     (9, 3, 7), 
     (1, 9, 66)]

# сортировка будет проводиться по лексикографическому подходу (многоуровневая)
sorted(
 l, 
 key=lambda el: (el[1], el[2]),  # сортируем сначала по столбцу с индексом 1, затем 2
 reversed=False,  # все сортировки по возрастанию!
)

# особенность: reversed настройка указывается сразу для всех уровней
# а если нам надо колонку 2 сортировать по убыванию?
# можно поставить знак минус (если тип данных числовой)
sorted(l, key=lambda el: (el[1], -el[2]), reversed=False)

# либо можно опираться на стабильность сортировки
# в этом случае делаем её в обратном порядке, двумя последовательными операциями
sorted(l, key=lambda el: el[2], reversed=True)
sorted(l, key=lambda el: el[1], reversed=False)

# в более сложных случаях я бы посмотрел в сторону pandas (если знак минус не спасает)
# либо можно использовать compare function (позволяет реализовать более сложные логики сортировки)
# compare function позволяет реализовать более сложные логики сортировки

В Excel часто удобнее бывает опираться на стабильность сортировки для сортировки таблиц. В Excel все сортировки - стабильные. Как было показано в примере выше, можно сортировать в обратном порядке, что в итоге даст многоуровневую сортировку. Хотя в Excel есть встроенный отдельный инструмент многоуровневой сортировки, достаточно удобный.

5. Соединение отсортированных списков (оптимизация)

Например, у нас есть 2 и более отсортированных python lists, и надо получить один общий, который также будет отсортирован.

Решение в лоб - просто объединить листы и заново отсортировать. Но мы не используем тот факт, что листы уже были отсортированы. Это не эффективно.

Эффективный алгоритм делает примерно так:

Допустим оба листа отсортированы по возрастанию
Создаем два указателя, ставим их в начале каждого листа
Сравниваем указатели (объекты из листов, на которых указатели)
Добавляем в новый лист меньший элемент
Передвигаем указатель вправо, т.к. этот объект уже использован
Повторяем

В python также есть модуль bisect, который содержит ряд полезных функций в этом контексте.

6. Стабильность сортировки

Давайте отсортируем числа по возрастанию [3, 1, 2]. Получается [1, 2, 3]. Тут просто.

Хорошо, а давайте отсортируем числа [3, 1, 1]. Получается [1, 1, 3]. А вот тут надо понимать, что два числа "один" - это разные объекты. Поэтому результат, вообще говоря, не однозначный. Единички могут размещаться двумя разными способами, хотя в данном случае этого не видно - [1, 1, 3], [1, 1, 3].

Может возникнуть вопрос. Если разницы не видно, то зачем это знать? Ответ прост: это важно, т.к. часто мы сортируем один список, на базе другого. Например, в Excel таблице, если мы делаем сортировку по одному столбцу, то ожидаем, что вся таблица будет отсортирована. Тут уже разница будет видна!

Небольшая демонстрация стабильности сортировки:

l = [
    (1, 'B'),
    (2, 'A'),
    (1, 'C'),
]

# ключ показывает, что хотим сортировать по элементу с индексом 0
sorted(l, key=lambda el: el[0])  

# -> [
#     (1, 'B'), # "B" идет до "С", как и в исходном списке. И это гарантируется!
#     (1, 'C'), 
#     (2, 'A')
# ]

Можно заметить, что теперь становиться важно, в каком порядке будут элементы "B", "C". Видим, что они сохранили порядок, относительно исходного списка. И это достаточно фундаментальный момент.

Если алгоритм сортировки гарантирует, что порядок одинаковых элементов не изменится - она стабильная. Интуитивно все ожидают стабильную сортировку (хотя редко кто так говорит). Поэтому в высокоуровневых средах программирования (excel, power query, power pivot и т.д.) сортировка обычно стабильная по умолчанию, и изменить это невозможно. Уже в python все не так однозначно, появляются варианты.

Например, чтобы гарантировать стабильность сортировки в pandas dataframe, надо явно об этом попросить df.sort_values('some column', kind='stable'). Иначе применяется quick sort, которая не является стабильной!

sort_values в pandas - НЕстабильная по дефолту!

Один из алгоритмов который я писал на pandas, требовал, чтобы сортировка перед ним была стабильная, а я по привычки думал, что это дефолтное поведение. Пришлось разобраться.

Built in python функция sorted гарантирует стабильность.

Если сортировка не гарантирует сохранение порядка - она нестабильная. Алгоритмы таких сортировок обычно быстрее. Кстати, нестабильные сортировки вообще ничего не гарантируют, т.е. порядок может быть сохранен, а может быть и нет.

Алгоритмов сортировок множество. Например, "Quick sort" нестабильный, "Merge sort" стабильный.

Вообще, стабильность сортировки позволяет делать интересные вещи:

# возьмем тестовый набор данных
l = [(1, 2, 3), 
     (2, 5, 8), 
     (2, 3, 7), 
     (2, 3, 66)]

# стабильная сортировка в данном случае ничего не меняет
sorted(l, key=lambda el: el[0])
# [(1, 2, 3), 
#  (2, 5, 8), 
#  (2, 3, 7), 
#  (2, 3, 66)]

# изменяем порядок на противоположный, только для одинаковых элементов
sorted(reversed(l), key=lambda el: el[0])
# [(1, 2, 3), 
#  (2, 3, 66), 
#  (2, 3, 7), 
#  (2, 5, 8)]

# перемешиваем только одинаковые элементы
import random
sorted(random.sample(l, k=len(l)), key=lambda el: el[0])
# [(1, 2, 3), 
#  (2, 3, 7), 
#  (2, 3, 66), 
#  (2, 5, 8)]

7. Key vs сompare function

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

Достаточно часто на практике встречаются случаи, когда очевидных ключей нет. Но зато есть функция, которая принимает два объекта (X, Y) и возвращает -1 (X меньше), 0 (X и Y равны), 1 (X больше). Такая функция и называется cmp (comparator/compare function).

В python редко, но встречается такой код:

from functools import cmp_to_key
# раньше я думал, что cmp_to_key какую-то магию делает
# т.е. казалось, что эта функция берет cmp и возвращает key function
# на самом деле cmp_to_key оборачивает объекты в искуственный класс
# а в методы сравнения помещает буквально нашу функцию - compare function
# т.е. это скорее просто технический момент. Чудес нет((

def my_cmp(X, Y):
    ...  # тут пишем нашу функцию сравнения

my_key = cmp_to_key(my_cmp)

sorted([...], key = my_key)  # сортировка будет сделана исходя из my_cmp логике
max([...], key = my_key)  # ключи актуальны и для min/max, конечно

Сортировка через функцию сравнения - более сложный случай. Давайте сформулируем условия, при которых это вообще возможно:

Любые два объекта из списка можно дать функции и получить результат -1, 0, 1.
Выполняется транзитивность (т.е. если объект A>B and B>C => A>C). Важное условие, которое часто может не выполняться.
Например, три объекта из популярной игры: камень, ножницы, бумага - нельзя отсортировать по их "силе". Т.к. не выполняется транзитивность. См. код ниже:

from functools import cmp_to_key
l = ['Paper', 'Rock', 'Scissors']  # три наши объекта

def compare_function(X, Y):  # принимаем два объекта, левый и правый
    # print(X, Y)
    if X == 'Rock':
        if Y == 'Scissors': return 1  # левый больше и т.д.
        elif Y == 'Paper': return -1  # правый больше
    elif X == 'Paper':
        if Y == 'Rock': return 1
        elif Y == 'Scissors': return -1
    elif X == 'Scissors':
        if Y == 'Paper': return 1
        elif Y == 'Rock': return -1

sorted(l, key=cmp_to_key(compare_function))  # запускаем
# ['Scissors', 'Rock', 'Paper']  # сортируется! удивляемся =)

# на самом деле python работает на основании допущения о транзитивности
# вообще говоря, он сделает только два сравнения, остальные будут выведены логически
# в этом можно убедиться поставив print в самом начале функции
# функция будет вызвана ровно 2 раза:
# Rock Paper
# Scissors Rock

# важно подчеркнуть, что Python НЕ проверяет, что транзитивность выполняется!
# Python верит вам на слово, что транзитивность выполняется :)
# Exception, raise Error НЕ будет! 
# код молча вернет первый попавшийся ответ
# И неважно, что он логически неверный

8. Total ordering

Возможно в python вы встречали такое from functools import total_ordering.

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

from functools import total_ordering 
  
@total_ordering
class num:  # игрушечный класс "Число"
    def __init__(self, value): 
        self.value = value 
    def __lt__(self, other):  # метод левое число больше
        return self.value < other.value 
    def __eq__(self, other):  # метод левое число равно правому
        return self.value == other.value 
          
print(num(2) < num(3))  # конечно True

Интересно, что название total_ordering взято не случайно (раньше я думал что, это как бы "тотальная мега сортировка, ну прямо вообще!"). На самом деле, "Total order" - это набор свойств бинарного отношения на множестве (wiki), который необходим, чтобы вывести остальные операции сравнения из двух данных. Рассмотрим эти свойства:

reflexive - для наших целей не очень интересно
antisymmetric - для любой пары объектов, X и Y, выполняется ровно одно из трёх утверждений: X больше, Y больше, либо они равны
transitive - важное свойство, мы встречали его в разделе выше (A>B and B>C => A>C)
connected - любые два объекта X и Y можно сравнить (нет пар, которые не сравниваются)

Самое опасное свойство - транзитивность. Именно оно часто не выполняется.

9. Нет транзитивности - беда

Обычно, конечно, транзитивность есть. Но в ряде особых случаев, её нет. И это не теория, это встречается на практике:

У нас есть 1000 текстов, надо отсортировать их от самого позитивного. Хотим сделать это хорошо и быстро. Используем LLM (llama, qwen и т.д.). LLM видит одновременно 2 текста и говорит, кто позитивнее.
Та же сортировка текстов по позитивности при помощи кросс-энкодеров (bert-like нейросети).
Нам дали 1000 фотографий котят, их надо как-то отсортировать. Сложно придумать ключ (хотя можно, конечно). Скорее, мы будем делать попарные сравнения (side-by-side). Возникнут логические противоречия.

Причем понятно, что объекты более-менее можно отсортировать, но будут ошибки, которые как-то надо поправлять. В этом смысле, можно сортировать несортируемое)

Вариант 1. Последовательно сравнивают объекты. После каждого сравнения делают транзитивное замыкание (transitive closure). Это позволяет сразу же указывать все сравнения, которые следуют из уже найденных сравнений. Наглядно это видно в примере выше - игра "камень, ножницы, бумага". Python сделал два сравнения, третье сравнение следовало из них, значит его уже не надо делать явно. Конечно данный подход недетерминированн (зависит от порядка сравнений), но лучше чем ничего.

Вариант 2. Можно еще сделать полный направленный граф сравнений. В нем будут циклы (противоречия, т.к. транзитивность иногда не выполняется). Цель - убрать циклы, удалив (=перевернув) минимальное количество ребер. В этом может помочь графовый алгоритм feedback_arc_set из библиотеки igraph (к сожалению, в networkx я такого не нашел).

Вариант 3. Просто взять гамильтонов путь полного направленного графа таких сравнений. Даже если там есть противоречия, путь все равно будет. Это свойство турнирного графа (tournament graph).

Сама по себе проверка на транзитивность может быть проведена так:

Проверка на транзитивность (itertools, networkx)

import itertools as it
import networkx as nx

l = [3, 1, 2, 9, 5, 5, 5]  # тестовый список

# Шаг 1 (обычно тут проблем нет)
# Надо проверить, что отношения эквивалентности выполняется без противоречий
# Т.е. что равные объекты образуют полный подграф (complete graph)
# мы используем тот факт, что комплимент полного графа - пустой
# иначе ошибка, т.е. отношение эквивалентности нарушено
H = nx.Graph()
for X, Y in it.combinations(l, 2):
    if X == Y: H.add_edge(X, Y)  # добавляем ребра, если объекты равны
for cc in nx.connected_components(H):  # отдельно смотрим каждую компоненту связности
    assert nx.is_empty(nx.complement(H.subgraph(cc)))

# Шаг 2
# теперь мы можем убрать дубликаты
# строим направленный граф
l = list(set(l))
G = nx.DiGraph()  # создаем пустой направленный граф
for X, Y in it.combinations(l, 2):
    if X > Y: G.add_edge(X, Y)
    elif X < Y: G.add_edge(Y, X)
nx.draw_networkx(G)  # см. ниже скрин

# убираем все транзитивные зависимости
# должен остаться DAG, где самый длинный путь - это все наши объекты
G = nx.transitive_reduction(G)
assert nx.is_directed_acyclic_graph(G)
assert nx.dag_longest_path_length(G) == len(l) - 1
nx.draw_networkx(G)  # см. ниже скрин

после удаления транзитивных зависимостей

10. Топологическая сортировка

Если у нас есть DAG (направленный ациклический граф), то может возникнуть задача выстроить все его вершины в плоский список (~отсортировать).

В результате должен получиться список с определенными свойствами. Если мы возьмем два элемента из списка X, Y (причем X левее, чем Y), то либо между ними нет направленного пути, либо существует путь именно от X к Y, а не наоборот.

Топологическую сортировку можно встретить в разных необычных местах:

Когда Excel считает формулы в ячейках, он делает это последовательно. Ему надо выстроить все ячейки в плоский список. В этом ему помогает гигантская топологическая сортировка. Ячейки - вершины графа, формульные связи - ребра графа.
Когда мы пишем код Power Query, внутри конструкции let ... in порядок выполнения строк кода определяется не "сверху-вниз", а путем топологической сортировки (да, это необычно для кода).

11. Сортировка по смыслу

На практике могут встречаться задачи сортировки текстов по смыслу (обычно коротких, например, названия, заголовки, тезисы). Под смыслом понимаем семантические вектора из Bert. Т.е. мы должны расположить тексты в каком-то логичном порядке от начала до конца.

Как вариант, можно делать кластеризацию (K-means, HDBSCAN и т.д.). Но тогда еще надо сами кластера сортировать как-то. Плюс внутри кластера нет очевидного порядка, не изящно получается.

Более простой и прямой способ - снижение размерности векторов до 1-D (dimensionality reduction: PCA, T-SNE, TruncatedSVD) после чего он станет автоматически отсортированным. Этот способ немного напоминает снижение размерности векторов до 2-D для целей визуализации (scatter plot).

12. Объединение сортировок в одну общую (усреднение сортировок)

Допустим есть множество объектов и по ним сделаны разные сортировки (по разным логикам). Но нам надо сделать общую итоговую сортировку.

Пример из практики: мы делаем RAG систему, подбираем релевантные чанки текста для запроса пользователя. По каждому чанку два вектора: bert и tf-idf. Т.о. все чанки будут отсортированы два раза для одного запроса пользователя. Сортировок может быть и больше, конечно. Как выбрать чанки, если сортировок более чем одна?

Самая первая мысль - сложить все индексы мест для каждого чанка. И сортировать уже по этой сумме.

Мысль вторая - складывать не индексы мест, а сами численные оценки похожести (в случае векторов - косинусные расстояния запрос-чанк). Но тут надо добиться сопоставимости этих оценок. Как это сделать, не всегда очевидно.

Еще один вариант - это Reciprocal Rank Fusion. Используется чуть модифицированная формула (сумма обратных индексов мест плюс корректирующий коэффициент). Интересно, что авторы в статье рекомендуют k=60. По сути, этот коэффициент регулирует силу двух идей:

важно занимать первые места, в других случаях можно последние места
важно занимать хорошие места всегда, пусть и не первые

import numpy as np
from numpy.random import default_rng; rng = default_rng(seed=42)

arr = np.arange(10).reshape(1, -1)
arr = np.repeat(arr, repeats=5, axis=0)
arr = rng.permuted(arr, axis=1)
arr.shape  # 5 соревнований, 10 участников в каждом
# верхняя левая пятерка означает, 
# что в соревновании 0 участник 0 занял 5-ое место
arr  
# array([[5, 6, 0, 7, 3, 2, 4, 9, 1, 8],
#        [4, 8, 2, 6, 5, 9, 7, 3, 0, 1],
#        [0, 9, 8, 4, 7, 2, 3, 5, 6, 1],
#        [6, 1, 2, 7, 9, 5, 8, 4, 0, 3],
#        [3, 2, 6, 5, 1, 4, 8, 9, 0, 7]])

# базовый способ
arr.sum(axis=0).argsort()
# array([8, 0, 2, 9, 5, 4, 1, 3, 6, 7], dtype=int64)
# самый лучший по итогу - участник с индексом 8

k = 200  # обычно 60 ставят
# k позволяет балансировать между двумя условными подходами:
# занял первое место - остальное не важно
# лучше занять два раза второй место

(arr / (1 + k)).sum(axis=0).argsort()  # результат немного другой
# array([8, 2, 0, 9, 5, 4, 1, 3, 6, 7], dtype=int64)

13. Оценка качества предсказанной сортировки (RAG)

Когда мы строим RAG нам надо оценивать качество поиска релевантных частей текста (чанки).

Например у нас есть эталонная сортировка первый 10 документов, релевантных конкретному запросу. Мы можем сравнить их с результатами нашего поиска.

Сравнение считаем через формулу MAP@K (см. сайт evidentlyai). Она позволяет рассчитать метрику качества сортировки с учетом количества объектов на правильных местах и с учетом "важности" позиций (важнее угадать первую позицию, чем вторую и т.д.).

import numpy as np
from numpy.random import default_rng; rng = default_rng(seed=42)

arr = np.arange(10).reshape(1, -1)
arr = np.repeat(arr, repeats=5, axis=0)
arr = rng.permuted(arr, axis=1)
arr  # дано пять сортировок (предсказания модели). Каждая сортировка 10 объектов
# array([[5, 6, 0, 7, 3, 2, 4, 9, 1, 8],
#        [4, 8, 2, 6, 5, 9, 7, 3, 0, 1],
#        [0, 9, 8, 4, 7, 2, 3, 5, 6, 1],
#        [6, 1, 2, 7, 9, 5, 8, 4, 0, 3],
#        [3, 2, 6, 5, 1, 4, 8, 9, 0, 7]])
# верхняя левая пятерка означает, что первая сортировка считает главным 
# документ с индексом 5

ground_true = rng.permuted(arr, axis=1)
ground_true  # допустим, это корректные результаты, корректные пять сортировок
# array([[5, 2, 1, 6, 0, 9, 8, 4, 3, 7],
#        [6, 3, 5, 1, 8, 0, 7, 2, 4, 9],
#        [0, 3, 2, 4, 7, 6, 1, 8, 9, 5],
#        [4, 8, 7, 0, 1, 6, 5, 2, 3, 9],
#        [3, 6, 1, 8, 7, 2, 5, 0, 9, 4]])

# попробуем вычислить качество предсказаний модели
temp = arr == ground_true
temp2 = np.repeat(np.arange(1, 10+1).reshape(1, -1), repeats=5, axis=0)
scores = np.mean(temp * temp.cumsum(axis=1) / temp2, axis=1)

scores  # отдельная оценка по каждой из пяти сортировок
# array([0.1       , 0.01428571, 0.21      , 0.        , 0.1       ])
# лучшая сортировка с индексом 2

14. LLM пишет сортировку на VBA (учёт data types)

В VBA (MS Excel) нет сортировки (вернее есть, если использовать ArrayList, но это external library). Можно еще записывать диапазон на лист, сортировать, потом читать обратно. Но это невероятный костыль.

Надо писать самому на VBA. Это сильно расстраивает( Я попросил gpt o1-preview сделать это за меня.

Промт был такой:

We write VBA code to process table data.
Table are modeled as collection of dictionaries in VBA. Nested dictionaries have key as columns names. Dictionaries values are table row items.
You task is to write VBA function which takes table as an argument and execute multilevel sorting (on 2 or more columns, ascending or descending). Columns may have different data types. Column may have mixed data type. Columns always have scalar types in them (no arrays, collections etc.)
Function should return sorted table in the form of collection of dictionaries.
Sorting must be stable.

Ответ GPT

'Certainly! Below is a comprehensive VBA solution that addresses your requirements for sorting a table represented
'as a `Collection` of `Dictionaries`. The function `MultiSortTable` allows multi-level sorting on specified columns
'with ascending or descending orders while ensuring stability.
'
'### Overview
'
'1. **Data Structure**:
'    - **Table**: A `Collection` where each item is a `Scripting.Dictionary` representing a row.
'Each dictionary has key-value pairs where keys are column names and values are the corresponding cell data.
'    - **Sort Criteria**: An array of sort specifications, where each specification is a two-element array containing
'the column name and the sort order (`"asc"` or `"desc"`).
'
'2. **Approach**:
'    - **Copy to Array**: Convert the `Collection` to a VBA array for efficient indexing.
'    - **Merge Sort**: Implement a stable merge sort tailored for multi-level sorting with mixed data types.
'    - **Comparison Logic**: Define a robust comparison method that handles different data types and respects the sort order.
'    - **Reconstruct Collection**: Create a new sorted `Collection` from the sorted array.
'
'### Implementation

'Option Explicit

' Function to perform multi-level stable sort on a table represented as a Collection of Dictionaries

Function MultiSortTable(table As Collection, sortCriteria As Variant) As Collection
    ' sortCriteria is expected to be a 1-based array where each element is a 2-element array:
    ' sortCriteria(i)(0) = column name (String)
    ' sortCriteria(i)(1) = sort order ("asc" or "desc")
    
    Dim rowCount As Long
    rowCount = table.Count
    If rowCount <= 1 Then
        ' No sorting needed
        Set MultiSortTable = table
        Exit Function
    End If
    
    ' Copy Collection to Array for sorting
    Dim rows() As Variant
    ReDim rows(1 To rowCount)
    Dim i As Long
    For i = 1 To rowCount
        Set rows(i) = table(i)
    Next i
    
    ' Perform Merge Sort
    MergeSort rows, LBound(rows), UBound(rows), sortCriteria
    
    ' Copy sorted array back to Collection
    Dim sortedTable As New Collection
    For i = 1 To rowCount
        sortedTable.Add rows(i)
    Next i
    
    Set MultiSortTable = sortedTable
End Function

' Merge Sort Implementation
Private Sub MergeSort(arr() As Variant, left As Long, right As Long, sortCriteria As Variant)
    If left < right Then
        Dim mid As Long
        mid = (left + right) \ 2
        MergeSort arr, left, mid, sortCriteria
        MergeSort arr, mid + 1, right, sortCriteria
        Merge arr, left, mid, right, sortCriteria
    End If
End Sub

' Merge procedure for Merge Sort
Private Sub Merge(arr() As Variant, left As Long, mid As Long, right As Long, sortCriteria As Variant)
    Dim n1 As Long, n2 As Long
    n1 = mid - left + 1
    n2 = right - mid
    
    ' Create temporary arrays
    Dim L() As Variant, R() As Variant
    ReDim L(1 To n1)
    ReDim R(1 To n2)
    
    Dim i As Long
    For i = 1 To n1
        Set L(i) = arr(left + i - 1)
    Next i
    For i = 1 To n2
        Set R(i) = arr(mid + i)
    Next i
    
    ' Merge the temporary arrays back into arr
    Dim j As Long, k As Long
    i = 1
    j = 1
    k = left
    
    Do While i <= n1 And j <= n2
        If CompareRows(L(i), R(j), sortCriteria) <= 0 Then
            Set arr(k) = L(i)
            i = i + 1
        Else
            Set arr(k) = R(j)
            j = j + 1
        End If
        k = k + 1
    Loop
    
    ' Copy any remaining elements of L
    Do While i <= n1
        Set arr(k) = L(i)
        i = i + 1
        k = k + 1
    Loop
    
    ' Copy any remaining elements of R
    Do While j <= n2
        Set arr(k) = R(j)
        j = j + 1
        k = k + 1
    Loop
End Sub

' Function to compare two rows based on sort criteria
' Returns:
'   -1 if row1 < row2
'    0 if row1 = row2
'    1 if row1 > row2
Private Function CompareRows(row1, row2, sortCriteria As Variant) As Long
    Dim i As Long
    For i = LBound(sortCriteria) To UBound(sortCriteria)
        Dim colName As String
        Dim sortOrder As String
        colName = sortCriteria(i)(0)
        sortOrder = LCase(sortCriteria(i)(1))
        
        Dim val1 As Variant, val2 As Variant
        val1 = row1(colName)
        val2 = row2(colName)
        
        Dim cmp As Long
        cmp = CompareValues(val1, val2)
        
        If cmp <> 0 Then
            If sortOrder = "asc" Then
                CompareRows = cmp
            ElseIf sortOrder = "desc" Then
                CompareRows = -cmp
            Else
                Err.Raise vbObjectError + 1, "CompareRows", "Invalid sort order: " & sortOrder
            End If
            Exit Function
        End If
        ' If equal, continue to next sort key
    Next i
    ' All sort keys equal
    CompareRows = 0
End Function

' Function to compare two values of potentially different types
' Returns:
'   -1 if val1 < val2
'    0 if val1 = val2
'    1 if val1 > val2
Private Function CompareValues(val1 As Variant, val2 As Variant) As Long
    ' Handle cases where either value is missing or Null
    If IsMissing(val1) Or IsNull(val1) Then
        If IsMissing(val2) Or IsNull(val2) Then
            CompareValues = 0
            Exit Function
        Else
            CompareValues = -1
            Exit Function
        End If
    ElseIf IsMissing(val2) Or IsNull(val2) Then
        CompareValues = 1
        Exit Function
    End If
    
    ' Determine data types
    Dim type1 As Long, type2 As Long
    type1 = VarType(val1)
    type2 = VarType(val2)
    
    ' If same type, compare accordingly
    If type1 = type2 Then
        Select Case type1
            Case vbInteger, vbLong, vbSingle, vbDouble, vbCurrency, vbByte, vbDecimal
                If val1 < val2 Then
                    CompareValues = -1
                ElseIf val1 > val2 Then
                    CompareValues = 1
                Else
                    CompareValues = 0
                End If
            Case vbDate
                If val1 < val2 Then
                    CompareValues = -1
                ElseIf val1 > val2 Then
                    CompareValues = 1
                Else
                    CompareValues = 0
                End If
            Case vbString, vbFixedString, vbWideString
                CompareValues = StrComp(CStr(val1), CStr(val2), vbTextCompare)
            Case vbBoolean
                If val1 = val2 Then
                    CompareValues = 0
                ElseIf val1 = False Then
                    CompareValues = -1
                Else
                    CompareValues = 1
                End If
            Case Else
                ' For other types, convert to string and compare
                CompareValues = StrComp(CStr(val1), CStr(val2), vbTextCompare)
        End Select
    Else
        ' Different types: define a type precedence
        ' Define precedence: Number < Date < String < Boolean < Others
        Dim precedence1 As Long, precedence2 As Long
        precedence1 = TypePrecedence(type1)
        precedence2 = TypePrecedence(type2)
        
        If precedence1 < precedence2 Then
            CompareValues = -1
        ElseIf precedence1 > precedence2 Then
            CompareValues = 1
        Else
            ' Same precedence, attempt to compare as strings
            CompareValues = StrComp(CStr(val1), CStr(val2), vbTextCompare)
        End If
    End If
End Function

' Function to define type precedence for mixed type comparison
Private Function TypePrecedence(vbType As Long) As Long
    Select Case vbType
        Case vbInteger, vbLong, vbSingle, vbDouble, vbCurrency, vbByte, vbDecimal
            TypePrecedence = 1
        Case vbDate
            TypePrecedence = 2
        Case vbString, vbFixedString, vbWideString
            TypePrecedence = 3
        Case vbBoolean
            TypePrecedence = 4
        Case Else
            TypePrecedence = 5
    End Select
End Function

'### How It Works
'1. Function MultiSortTable:
'    - Input:
'        - table: The table to sort, represented as a Collection of Dictionaries.
'        - sortCriteria: An array where each element is a two-element array specifying the column name and sort order.
'    - Process:
'        - Converts the Collection to an array for easier manipulation.
'        - Applies a stable merge sort to the array based on the provided sort criteria.
'        - Reconstructs and returns a new sorted Collection.
'
'2. Merge Sort (MergeSort and Merge):
'    - A recursive implementation that divides the array and merges them back in sorted order.
'    - Utilizes the CompareRows function to determine the order between two rows based on multiple sort levels.
'
'3. Comparison Logic (CompareRows and CompareValues):
'    - CompareRows: Iterates through each sort criterion and compares the corresponding values in two rows.
' If a difference is found, it returns the comparison result adjusted for ascending or descending order.
'    - CompareValues: Handles the comparison between two individual cell values, considering their data types. It ensures that different types are compared in a consistent and predictable manner by defining a type precedence.
'    - TypePrecedence: Assigns a precedence value to different data types to facilitate mixed-type comparisons.
'
'### Usage Example
'
'Here 's how you can use the MultiSortTable function in your VBA project:

'VBA

Sub ExampleUsage()
    Dim table As New Collection
    
    ' Example: Creating sample data
    Set row = CreateObject("Scripting.Dictionary")
    row.Add "Name", "Alice"
    row.Add "Age", 30
    row.Add "JoinDate", #1/15/2020#
    table.Add row
    
    Set row = CreateObject("Scripting.Dictionary")
    row.Add "Name", "Bob"
    row.Add "Age", 25
    row.Add "JoinDate", #3/22/2021#
    table.Add row
    
    Set row = CreateObject("Scripting.Dictionary")
    row.Add "Name", "Charlie"
    row.Add "Age", 30
    row.Add "JoinDate", #2/10/2019#
    table.Add row
    
    ' Define sort criteria: first by Age ascending, then by JoinDate descending
    Dim sortCriteria(1 To 2) As Variant
    sortCriteria(1) = Array("Age", "asc")
    sortCriteria(2) = Array("JoinDate", "desc")
    
    ' Perform multi-level sort
    Dim sortedTable As Collection
    Set sortedTable = MultiSortTable(table, sortCriteria)
    
    ' Display sorted results
    For Each sortedRow In sortedTable
        Debug.Print sortedRow("Name") & ", " & sortedRow("Age") & ", " & sortedRow("JoinDate")
    Next sortedRow
End Sub

'Expected Output:
'Bob , 25, 3 / 22 / 2021
'Alice , 30, 1 / 15 / 2020
'Charlie , 30, 2 / 10 / 2019

'In this example:
'- The table is first sorted by Age in ascending order.
'- For rows with the same Age, it further sorts them by JoinDate in descending order.
'- The sorted output maintains stability, meaning that the original order is preserved where criteria are equal.
'
'### Notes
'- Error Handling: The function raises an error if an invalid sort order is provided.
'Ensure that sort orders are specified correctly as "asc" or "desc".
'- Performance: While this implementation is suitable for small to moderately sized datasets,
'performance might degrade with very large tables due to the nature of VBA and the merge sort implementation.
'- Data Types: The comparison logic handles common data types.
'If your data includes more complex types, you may need to extend the CompareValues function accordingly.
'
'Feel free to integrate and modify this code to better fit the specific nuances of your project!

Несколько интересных моментов:

GPT использует подход compare function (объекты сравнения - строки таблицы). Это универсальный подход. Использование key тут будет практически невозможно, т.к. типы данных колонок заранее не известны
Код на 99% был рабочий (неправильно объявлялись Scripting.Dictionary)
Код учитывал многоуровневость сортировки и ascending/descending параметры
Сортировка, как я и просил, была стабильная (Merge sort алгоритм)
GPT попробовал отработать ситуацию разных data types. Получилось не очень хорошо, но в целом логично

Вопрос сравнения объектов с разными типами данных - сложный. Напомню, основные типы данных VBA:

string - строки любой длины
single - дробные единичной точности
double - дробные единичной точности
date - даты
integer - целое
long - длинное целое
и ряд других

GPT разрешил сравнивать объекты, только если они строго одного типа данных (напр., double только с double). Но, например, integer и long вроде тоже сопоставимы без аномалий, можно было их сравнивать. Ещё можно было сравнивать разные точности дробных чисел и дробные-целые, однако тут могут быть некоторые особенности. Python бы ещё так смогу бы True > 0.5. Если бы я писал, я бы постарался это учесть, т.к. интуитивно человек будет ожидать эту функциональность.

Например, если в pandas series будут int и float объекты, они будут сравниваться, именно как числа.

Если типы данных не совпадают GPT просто установил некоторый, заранее известный порядок типов данных (All number types < Date < String < Boolean < Others).

А если типы данных не совпадают, но находятся на одинаковом уровне приоритета (порядок самих типов данных), то все переводится в строки (str) принудительно и пытается сравниваться. Т.е. на двух объекта 21 Single и 3 Double мы получим совершенно нелогичный результат (т.к. "3" > "21").

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

15. Линеаризация (поставить объекты в ряд)

Часто в разных областях возникает задача перебрать/обойти все объекты. Это не совсем сортировка, но похоже.

Области в которых это можно встретить:

Обходы графа (DFS, BFS)
Обходы дерева (pre-order, in-order, post-order)
MRO (method resolution order) в python определяет порядок вызовов методов в классах с множественным наследованием (алгоритм С3)

16. Мера отсортированности списка

Возьмем список A = [1, 2, 3, 4, 5]. Он отсортирован. Содержит 5 элементов. Количество перестановок 5! = 120.

Теперь возьмем два других списка B = [2, 1, 3, 4, 5] и C = [5, 4, 3, 2, 1]. Очевидно, что B более упорядочен, по сравнению с A. Но как это измерить численно?

Вспоминая, что сортировка - это, по сути, перестановка, то мы можем узнать индекс перестановки. Это возможно, т.к. все 120 перестановок пронумерованы. Хотя есть разные подходы к нумерации 120 перестановок, мы используем классический.

import more_itertools as mit  # мега крутая библиотека, всем рекомендую!

l = [1, 2, 3, 4, 5]

import math; math.factorial(5)
# 120 - всего 120 (индексы от 0 до 119)

mit.permutation_index(l, [1, 2, 3, 4, 5])
# 0 - понятно, что сам список имеет индекс 0 (самый первый)

mit.permutation_index(l, [2, 1, 3, 4, 5])
# 24 - чуть-чуть перемешали, недалеко от 0

mit.permutation_index(l, [5, 4, 3, 2, 1])
# 119 - перемешали сильно, по сути максимально (хотя этот термин и не определен строго)
# максимально далеко от 0

В этом смысле, индекс сортировки может выполнять роль измерения расстояния между двумя перестановками (permutations), в нашем случае, между упорядоченным состоянием и перемешанным. Подробнее про комбинаторные свойства перестановок можно посмотреть в документации sympy.

17. Множества (ordered set, sorted set)

В Python есть отличная структура данных - множество (set). Есть еще multi-set в виде collections.Counter.

Единственное, чего мне всегда не хватало - это наличие упорядоченных множеств и операций между ними (которые гарантируют сохранение упорядоченности/сортировки). Да, его можно реализовать самостоятельно. Но хочется чего-то готового, проверенного. Вот что я обычно использую в таких случаях:

# выручает pandas со своими индексами
# там реализованы базовые difference, intersection, union
# и они сохраняют порядок! ровно то, что нужно
import pandas as pd
pd.Index([1, 2, 3, 5, 6]).difference(pd.Index([2, 3]))
# Index([1, 5, 6], dtype='int64')  сохранение порядка НЕ случайно. Это гарантируется

# есть и другие способы, в целом выдают ожидаемый результат
# pip install ordered-set
# pip install boltons
# pip install collections-extended

18. Две заключительные мысли

Везде математика (выше мы затронули несколько её разделов)
Иногда приходиться вникать в детали (сортировку на VBA пришлось "писать"). Хотя раньше я часто слышал тезис, что это не потребуется в реальной работе

Её величество Сортировка