Быстрая стабильная сортировка для небольших массивов (до 32 или 64 элементов)
Общепринятое мнение гласит, что для достаточно маленьких массивов лучше всего использовать сортировку вставок. Например, Timsort использует (двоичную) сортировку вставок для массивов до 64 элементов; из Википедии:
Некоторые алгоритмы "разделяй и властвуй", такие как быстрая сортировка и сортировка слиянием, рекурсивно делят список на меньшие подсписки, которые затем сортируются. Полезная оптимизация на практике для этих алгоритмов заключается в использовании сортировки вставок для сортировки небольших подсписков, поскольку сортировка вставок превосходит эти более сложные алгоритмы. Размер списка, для которого сортировка вставкой имеет преимущество, зависит от среды и реализации, но обычно составляет от восьми до двадцати элементов.
Это действительно правильно? Есть ли лучшие альтернативы?
Если это существенно зависит от платформы, меня больше всего интересует.NET.
4 ответа
Да, это то, что я изучил в моих классах алгоритмов, и это также, как сортировка реализована в C++ STL. Из Википедии:
Июньская стандартная библиотека шаблонов SGI C++ stl_algo.h, реализованная в нестабильной сортировке, использует подход самоанализа Musser с глубиной рекурсии для переключения на heapsort, переданный в качестве параметра, выбор сводной медианы-3 и проход окончательной вставки Sedgewick. Порог элемента для переключения на простой тип вставки был 16.
В прошлом году я провел несколько неофициальных тестов производительности, и C++ STL std::sort был примерно в два раза быстрее, чем Array.Sort в.NET. Я не знаю, как реализован.NET Array.Sort, но в.NET доступ к массиву требует проверки границ, в отличие от C++, которая может в значительной степени учитывать разницу в производительности.
Я обнаружил, что это действительно зависит от того, сколько работы должна выполнить функция сравнения. Например, если я косвенно сортирую строки на листе, и каждое сравнение включает в себя выборку строки и последующее сравнение, возможно, нескольких столбцов, возможно смешивание числовых и строковых сравнений, это может быть медленным.
С другой стороны, если длина массива мала, это зависит от того, сколько раз в секунду вам нужно его отсортировать, потому что даже если он относительно медленный по сравнению с тем, каким он может быть, вы никогда не заметите разницу.
Если у меня есть какие-либо сомнения, я просто кодирую сортировку слиянием и продолжаю. У меня был плохой опыт работы с qsort, который не был стабильным и иногда занимал много времени. Ручная сортировка слиянием проста, надежна и достаточно быстра.
Нет более быстрых алгоритмов O(n log n), чем сортировка вставкой для небольших списков. Тем не менее, есть несколько O(n^2) алгоритмов, которые конкурируют. Примечательно, что сортировка выбора не является одним из них, хотя она хороша в редкой ситуации, когда свопы и ходы стоят дорого. Пузырьковая сортировка и варианты тоже просто плохи.
Сетевая сортировка: алгоритм сортировки, всегда стабильный, без ветвей. В целом у него ужасные характеристики, но отсутствие веток означает звездную производительность в самых маленьких списках. Базовый случай: if(a<b) swap(a,b);
Сортировка вставкой с пакетами: в каждом цикле сортируйте 2-4 элемента, затем вставляйте их вместе. Это уменьшает количество ходов и сравнивает на 25–37 процентов для более длинных списков. Общий эффект - оптимизация списков размером от 16 до 64.
Поскольку.NET - это язык, который не компилируется в необработанный машинный код. Я бы сказал, что вызов функции API (которая использует нативный код), вероятно, самый быстрый способ