Является ли сортировка a, b, c эквивалентной сортировке c; сортировать б; сортировать?
В C ++ я должен реализовать конструктор запросов «Excel / Access-like» (цитата), чтобы разрешить пользовательскую сортировку набора данных. Если вы сортируете по столбцам A, B и C в Excel, используя построитель запросов или «ORDER BY a, b, c» в SQL, вы получите все по порядку «As», все B в каждой группе идентичных по порядку «As», и все C внутри каждой группы идентичных B по порядку, что большинство людей понимают под «сортировка / упорядочение по a, b, c». Похоже, это то же самое, что выполнить «сортировать по c», затем «отсортировать по b», затем «отсортировать по a» — т.е. сортировка по отдельности для каждого столбца в обратном порядке — при условии, что вы используете stable_sort. Вот как я реализовал это в моей программе. Пользователь говорит: «сортировать по a, b, c», программа делает stable_sort по c, stable_sort по b, stable_sort по a — тот же результат со всеми наборами данных, которые я использовал до сих пор. У меня вопрос, является ли это общеизвестная эквивалентность, которая верна для любого набора данных (при условии использования алгоритма стабильной сортировки) и любая комбинация столбцов, и есть ли даже математическое доказательство для этого? До сих пор я не нашел таких доказательств через Google или другие средства (спрашивая программистов, статистиков и математиков).
Решение
Да, это правильно. «Доказательство» находится в самом определении стабильного вида:
Алгоритм сортировки стабилен, если всякий раз, когда есть две записи R и S с одинаковым ключом, и R появляется перед S в исходном списке, тогда R всегда будет появляться перед S в отсортированном списке.
Рассмотрим ваш алгоритм реализации «сортировать по aзатем b«сортируя по b а затем сортировать по a, Первый сорт (на b) оставляет все записи с нижним b опережать рекорды с более высоким b — в силу того, что алгоритм сортировки (стабильность не требование для первого сорта).
Второй род (на a) необходимо обратить внимание на b только когда aс одинаковы. В силу того, что стабильный, этот вид оставляет записи с идентичными aв том же порядке, в котором они были до сортировки, а именно: b, Это именно то, что вы достигаете, когда вы сортируете aзатем b,
Одно и то же доказательство можно распространить на сортировку по более чем двум ключам, наблюдая, что добавление большего количества шагов сортировки сохраняет результаты предыдущих шагов в исходном порядке, который является именно тем порядком, который мы хотим иметь в группах равенства ключей с более высокий приоритет сортировки.
Другие решения
Других решений пока нет …
detector