Sorting Race — ставка на более быстрый алгоритм
Два алгоритма сортировки бегут по одному и тому же массиву. Ставьте на победителя: лучшая сложность проигрывает чаще, чем кажется.
Шесть забегов. Один массив, два алгоритма — выберите того, кто, по-вашему, финиширует первым.
Как играть
- Две сортировки, один массив. Поставьте на ту, что финиширует первой, и смотрите.
- Побеждает та, что потратила меньше операций — сравнений плюс перемещений, — а не та, у которой лучше учебная сложность.
- Смотрите на размер и форму. Ниже примерно двадцати столбиков выигрывают простые; на почти отсортированном массиве вставки обгоняют всех.
- Верная ставка приносит 50, неверная стоит 50. Шесть забегов, начинаете со 100.
Как это работает
Два алгоритма сортировки бегут по одному и тому же массиву, нарисованному столбиками, а вы ставите на того, кто финиширует первым. Каждый раунд сводит сортировку O(n log n) с сортировкой O(n²), так что явный фаворит есть всегда — и явный фаворит ошибается примерно в половине случаев. На самом деле всё решают размер массива и его форма: сортировка вставками заканчивает почти отсортированный массив за двадцатую часть операций, которые нужны наивной быстрой сортировке, а ниже примерно двадцати элементов константы перевешивают асимптотику — именно поэтому настоящие библиотеки сортировки на таких размерах переключаются на вставки. Победитель определяется числом операций, а не секундомером, поэтому результат одинаков на любой машине. Всё работает на вашем устройстве, никуда ничего не отправляется, регистрироваться негде.
Операции — это сравнения плюс перемещения данных, где обмен считается за одну, посчитанные на учебных реализациях. Настоящие библиотечные сортировки гибридные и выигрывали бы почти каждый забег — в этом и суть.
Частые вопросы
Разве лучший алгоритм не всегда быстрее?
На таких размерах — нет. O-нотация описывает, как растёт стоимость, а не какая она, и полностью скрывает константу. Измерено на 400 забегах: ставка на лучшую теоретическую сложность угадывает 3,19 из 6 против 3,00 при ставке всегда на одну сторону. Два правила — почти отсортированный массив и маленький массив оба играют за простую сортировку — дают около 4,8 из 6.
Как определяется победитель?
Подсчётом сравнений и перемещений, вычисленным до того, как что-либо нарисовано. Анимация проигрывает этот счёт с одинаковой скоростью с обеих сторон, поэтому сторона, которой нужно меньше операций, финиширует первой на экране по той же причине, по которой она выигрывает. Визуализатор, гоняющий два цикла в реальном времени, на быстрой машине давал бы другой ответ, чем на медленной.
Почему быстрая сортировка иногда так плоха?
Она берёт опорным последний элемент — наивный вариант. На уже или почти отсортированном массиве это худший возможный выбор: разбиения вырождаются, и она делает квадратичную работу ровно на тех данных, с которыми сортировка вставками справляется быстрее всего. Настоящие реализации берут медиану трёх или случайный опорный элемент именно поэтому.
Что означают формы массива?
Случайный — перемешанный. Почти отсортированный упорядочен, кроме нескольких соседних перестановок. Обратный — ровно наоборот. Мало значений — всего четыре различных значения, и там разбиение наивной быстрой сортировки разваливается. Пила повторяет один и тот же подъём несколько раз.