Math
Гонка сортировок
Три сортировки бегут по одному массиву с одинаковой скоростью в сравнениях, и первой финиширует та, которая спросила меньше. Решает гонку не размер, а беспорядок: на отсортированном входе вставки берут 63 сравнения, а быстрая — 2016.
Что происходит
Три дорожки, один массив и один общий бюджет работы: все три сортировки продвигаются на одно и то же число сравнений — или перемещений, если переключить единицу, — поэтому первой финиширует та, которой нужно меньше этой единицы, а не та, что нарисована быстрее. На всех дорожках один язык: два сравниваемых ключа обведены золотом, только что записанный ключ вспыхивает зелёным, опорный элемент отмечен красным, обрабатываемый участок взят в скобку, элементы на своём окончательном месте получают зелёную подставку, а ключ, который держит сортировка вставками, висит над щелью, куда опустится. Предскажите победителя до кнопки «Старт» или ведите гонку по одной единице. Попробуйте входы: на отсортированном массиве вставки финишируют почти сразу, а быстрая сортировка с последним опорным попадает в свой худший случай; обратный порядок — худший случай вставок; с повторяющимися ключами цвет — это место во входе, и слияние сохраняет порядок равных ключей, а быстрая их перемешивает. Каждая дорожка показывает и настоящее время прогона на этом компьютере — третью величину, никогда не единицу гонки.
Уравнения модуля
Уравнения n элементов, а гонка идёт по числу СРАВНЕНИЙ - именно о нём говорят формулы сортировка вставками ПЕРЕМЕЩАЕТ элемент ровно столько раз, сколько в массиве инверсий: тождество для КАЖДОЙ перестановки, проверено по всем n! при n <= 8 сравнений при вставках = инверсии + (n − 1) − (префиксные минимумы при i >= 1); в среднем = n(n−1)/4 + n − H_n ТОЧНО: n = 8 -> 19.282142857142858; n = 64 -> 1067.2561090962943 быстрая сортировка (Ломуто, последний элемент - опорный) в среднем = 2(n+1)H_n − 4n ТОЧНО: n = 8 -> 16.921428571428571; n = 64 -> 360.70581748175005 сортировка слиянием в худшем случае = n·ceil(lg n) − 2^ceil(lg n) + 1 - это формула, а не оценка: 321 при n = 64, против ceil(lg n!) = 296, нижней границы для ЛЮБОЙ сортировки сравнениями эти два значения равны при n <= 4 и расходятся дальше; сортировка слиянием к тому же записывает n·lg n элементов при любом входе - 384 при n = 64 64 элемента, все места перемешаны: 1001 инверсия; вставки 1057 сравнений / 1001 перемещение, слияние 307 / 384, быстрая 352 / 306 64 элемента, отсортированный вход: вставки 63, слияние 192, быстрая 2016 - а 2016 это n(n−1)/2, НАИХУДШИЙ случай быстрой сортировки слияние обгоняет вставки при 15 перемешанных местах из 64 (269 против 246): порог определяется беспорядком, а не размером - на случайном входе слияние впереди начиная с n = 4 равные ключи, 64 элемента на 8 значений: пар, оставшихся в обратном порядке - вставки 0, слияние 0, быстрая 77
