Какой алгоритм сортировки использовать где?

Question

Существуют различные алгоритмы сортировки. Алгоритм сортировки с временной сложностью O(n^2) может быть более подходящим, чем O(nlogn), потому что он на месте или стабилен. Например:

• Для некоторых сортированных вещей вставка сортировки хороша.
• Применение быстрой сортировки к почти отсортированному массиву - глупость.
• Сортировка кучи хороша с O(nlogn), но не стабильна.
• Сортировка слиянием не может использоваться во встроенных системах, так как в худшем случае она требует O(n) пространственной сложности.

Я хочу знать, какой алгоритм сортировки подходит в каких условиях.

• Какой алгоритм сортировки лучше всего подходит для сортировки имен в алфавитном порядке?
• Какой алгоритм сортировки лучше всего подходит для сортировки меньше целых чисел?
• Какой алгоритм сортировки лучше всего подходит для сортировки меньшего числа целых чисел, но может иметь большой диапазон (98767 - 6734784)?
• Какой алгоритм сортировки лучше всего подходит для сортировки миллиардов целых чисел?
• Какой алгоритм сортировки лучше всего подходит для сортировки во встроенных системах или системах реального времени, где пространство и время являются ограничениями?

Пожалуйста, предложите эти / другие ситуации, книги или веб-сайт для такого типа сравнений.

Answer 1

Ну, нет серебряной пули - но вот несколько практических правил:

1. Radix sort / Counting sort обычно хорош, когда диапазон элементов (пусть будет U) относительно невелик по сравнению с количеством элементов (U<<n) (может соответствовать вашему случаю 2,4)
2. Сортировка вставок хороша для малых n<30) списки, даже быстрее, чем O(nlogn) алгоритмы (эмпирически). На самом деле, вы можете оптимизировать O(nlogn) нисходящий алгоритм путем переключения на сортировку вставки, когда n<30
3. Вариант радикальной сортировки также может быть хорошим выбором для сортировки строк по алфавиту, так как O(|S|*n)в то время как обычный алгоритм сравнения на основе O(|S|*nlogn) [где |S| это длина вашей строки]. (соответствует вашему случаю 1)
4. Там, где отсортированный ввод очень большой, слишком большой, чтобы поместиться в объединение, способ сделать это - с помощью внешней сортировки - которая является вариацией или сортировкой слиянием, она минимизирует количество операций чтения / записи на диск и гарантирует, что они выполняются последовательно - потому что это резко повышает производительность. (может соответствовать случаю 4)
5. Для общей сортировки случаев быстрая сортировка и тимсорт (используемые для java) дают хорошую производительность.

Answer 2

Сортировка слиянием не может использоваться во встроенных системах, так как в худшем случае она требует O(n) пространственной сложности.

Вы можете быть заинтересованы в stable_sort функция из C++. Он пытается выделить дополнительное пространство для обычной сортировки слиянием, но если это не удается, он выполняет устойчивую сортировку на месте с меньшей сложностью по времени (n * ((log n)^2) вместо n * (log n)). Если вы можете читать C++, вы можете посмотреть на реализацию в вашей любимой стандартной библиотеке, в противном случае, я думаю, вы найдете подробности, объясненные где-то в не зависящих от языка терминах.

Существует масса научной литературы о стабильной сортировке на месте (и, в частности, слиянии на месте).

Так что в C++ практическое правило легко std::stable_sort если вам нужна стабильная сортировка, в противном случае используйте std::sortMsgstr ". Python снова делает это еще проще, практическое правило" использовать sorted".

В общем, вы обнаружите, что многие языки имеют довольно умные встроенные алгоритмы сортировки, и вы можете использовать их большую часть времени. Редко, когда вам нужно реализовать свою собственную, чтобы побить стандартную библиотеку. Если вам нужно реализовать свои собственные, то на самом деле ничто не заменит вытягивание учебников, реализацию нескольких алгоритмов с таким количеством хитростей, которые вы можете найти, и тестирование их друг против друга для конкретного случая, который вас беспокоит для чего вам нужно побить библиотечную функцию.

Большинство "очевидных" советов, на которые вы, возможно, надеетесь в ответ на этот вопрос, уже включены во встроенные функции сортировки одного или нескольких распространенных языков программирования. Но чтобы ответить на ваши конкретные вопросы:

Какой алгоритм сортировки лучше всего подходит для сортировки имен в алфавитном порядке?

Радикальная сортировка может исключить стандартные сортировки сравнения, такие как C++ sort, но это может быть невозможно, если вы используете "правильные" правила сопоставления имен. Например, "МакАлистер" имел обыкновение располагаться в алфавитном порядке так же, как "МакАлистер", а "Сент-Джон" как "Сент-Джон". Но затем пришли программисты и захотели просто отсортировать по значению ASCII, а не кодировать множество специальных правил, поэтому большинство компьютерных систем больше не используют эти правила. Я считаю, что пятничный полдень - хорошее время для такого рода функций;-) Вы все еще можете использовать сортировку по основанию, если вы делаете это по буквам "канонизированного" имени, а не по фактическому имени.

"Правильные" правила сопоставления на других языках, кроме английского, также интересны. Например, в немецком "Грюбер" сортируется как "Грюбер", и поэтому следует после "Грубер", но перед "Грюн". В английском языке название "Llewellyn" следует после "Lewis", но я верю в валлийский язык (используя точно такой же алфавит, но с другими традиционными правилами сопоставления), он встречается раньше.

По этой причине легче говорить об оптимизации сортировки строк, чем фактически делать это. "Правильная" сортировка строк требует наличия возможности включать правила сортировки, зависящие от локали, и, если вы отойдете от сортировки сравнения, вам, возможно, придется переписать весь код сортировки.

Какой алгоритм сортировки лучше всего подходит для сортировки меньше целых чисел?

Для небольшого числа маленьких значений может быть сортировка подсчета, но Introsort с переключением на сортировку вставкой, когда данные становятся достаточно маленькими (20-30 элементов), довольно хорош. Timsort особенно хорош, когда данные не случайны.

Какой алгоритм сортировки лучше всего подходит для сортировки меньшего числа целых чисел, но может иметь большой диапазон (98767 - 6734784)?

Большой диапазон исключает счетную сортировку, поэтому для небольшого числа целочисленных целых чисел, Introsort/Timsort.

Какой алгоритм сортировки лучше всего подходит для сортировки миллиардов целых чисел?

Если под "миллиардами" вы подразумеваете "слишком много, чтобы уместиться в памяти", то это немного меняет игру. Вероятно, вы хотите разделить данные на куски, которые умещаются в памяти, Intro/Tim отсортировать каждый из них, а затем выполнить внешнее объединение. Если вы работаете на 64-битной машине, сортирующей 32-битные целые числа, вы можете рассмотреть возможность сортировки.

Какой алгоритм сортировки лучше всего подходит для сортировки во встроенных системах или системах реального времени, где пространство и время являются ограничениями?

Вероятно, Интросорт.

Для некоторых сортированных вещей вставка сортировки хороша.

Правда и Тимсорт пользуется той же ситуацией.

Применение быстрой сортировки к почти отсортированному массиву - глупость.

Ложь. Никто не использует простую быструю сортировку, первоначально опубликованную Hoare, вы можете сделать лучший выбор, который сделает смертельные случаи гораздо менее очевидными, чем "отсортированные данные". Для тщательного рассмотрения плохих случаев существует Introsort.

Сортировка кучи хороша с O(nlogn), но не стабильна.

Правда, но Introsort лучше (и тоже не стабилен).

Сортировка слиянием не может использоваться во встроенных системах, так как в худшем случае она требует O(n) пространственной сложности.

Обращайтесь с этим, допуская несколько более медленное слияние на месте, например std::stable_sort делает.