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