Энтузиаст создал сортировку имени Сталина

Сортировка Merciful steel — это новый алгоритм сортировки, вдохновленный печально известной сортировкой steel . Во время экспериментов с сортировкой steel в качестве игрового упражнения возникла интригующая идея: вместо того, чтобы отбрасывать элементы, идущие не по порядку, что если мы сохраним элементы, идущие по порядку, и рекурсивно отсортируем остальные ? Логика заключалась в том, что, уменьшив размер массива, требующего сортировки, мы могли бы добиться прироста производительности, особенно на частично отсортированных массивах. Это привело к разработке сортировки Merciful steel.

Разработка и концепция

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

При разработке сортировки Merciful Сталина (см. историю коммитов) первоначальная реализация включала один прямой проход по массиву, сбор элементов в порядке возрастания и рекурсивную сортировку неупорядоченных элементов. Однако этот подход был неэффективен для массивов, отсортированных в обратном порядке, поскольку приводил к обширной рекурсии и низкой производительности.

Чтобы решить эту проблему, алгоритм был улучшен путем добавления обратного прохода . После того, как прямой проход собирает элементы в порядке возрастания, обратный проход проходит по оставшимся элементам в обратном порядке, собирая элементы, которые находятся в порядке убывания. Это добавление значительно улучшило производительность на массивах с обратной сортировкой за счет уменьшения глубины рекурсии и обработки как возрастающих, так и убывающих последовательностей внутри массива.

Обзор алгоритма

Сортировка «Милосердный Сталин» осуществляется в три основных этапа:

1. Прямой проход : итерация по массиву с начала, сохраняя элементы, которые находятся в порядке возрастания. Элементы, идущие не по порядку, собираются в отдельный массив.

2. Обратный проход : Итерация по неупорядоченным элементам с конца, сохранение элементов, которые находятся в убывающем порядке. Оставшиеся элементы собираются в другой массив.

3. Слияние и рекурсивная сортировка : Объединить отсортированные элементы из прямого и обратного проходов. Если остались несортированные элементы, рекурсивно применить к ним сортировку Merciful Сталина и объединить результат с ранее объединенным массивом.

Этот алгоритм уменьшает размер проблемы путем сортировки меньших подмножеств массива и их слияния, аналогично сортировке слиянием. Добавление обратного прохода позволяет алгоритму эффективно обрабатывать как восходящие, так и нисходящие последовательности.

Анализ сложности времени

Лучший случай: O(n)

Лучший сценарий возникает, когда массив уже отсортирован в порядке возрастания или убывания. В этом случае прямой проход или обратный проход соберет все элементы в отсортированный массив без каких-либо оставшихся элементов для рекурсивной сортировки. Алгоритм выполняет один проход по массиву, что приводит к линейной временной сложности.

Средний случай и худший случай: O(n log n)

В среднем и худшем случае массив содержит смесь упорядоченных и неупорядоченных элементов. Алгоритм уменьшает размер проблемы при каждом рекурсивном вызове, собирая упорядоченные элементы во время прямого и обратного проходов. Каждый уровень рекурсии обрабатывает часть массива, а глубина дерева рекурсии логарифмична относительно количества элементов.

При каждом рекурсивном вызове массив разбивается на три части:

• Элементы прямой сортировки : элементы, собранные во время прямого прохода.
• Элементы, отсортированные в обратном направлении : элементы, собранные во время обратного прохода.
• Оставшиеся несортированные элементы : элементы, которые не были собраны ни во время одного из проходов.

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

На каждом уровне рекурсии алгоритм выполняет O(n) работы:

• Каждый проход вперед и назад занимает O(n) времени.
• Объединение отсортированных массивов также занимает O(n) времени.

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

NB: Невозможно, чтобы массив имел все элементы неупорядоченными как в прямом, так и в обратном проходе одновременно. Эта внутренняя конструкция гарантирует, что каждый проход успешно уменьшает размер неотсортированной части массива геометрически, предотвращая время выполнения O(n?) и поддерживая эффективность алгоритма, гарантируя прогресс на каждом рекурсивном шаге.

Эмпирические результаты и анализ

Был проведен комплексный сравнительный анализ для оценки производительности сортировки «Милосердный Сталин» по сравнению с традиционными алгоритмами сортировки: сортировкой слиянием, быстрой сортировкой, пузырьковой сортировкой, сортировкой вставками.

Использовались массивы различных размеров и начальных порядков: случайные массивы, отсортированные массивы, обратно отсортированные массивы, частично отсортированные массивы с 10%, 30% и 50% несортированных элементов.

Подробные результаты сравнительного анализа можно найти в results.txt.

Случайные Массивы

В случайных массивах сортировка Merciful Сталина уступает сортировке Merge Sort и быстрой сортировке. Накладные расходы от прямого и обратного проходов, а также рекурсивные вызовы способствуют ее неэффективности на несортированных данных. График показывает, что с увеличением размера массива время выполнения сортировки Merciful Сталина растет быстрее, чем сортировки Merge Sort и быстрой сортировки. Однако она превосходит сортировку пузырьком и сортировку вставкой, особенно на больших массивах.

Сортированные массивы

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

Массивы с обратной сортировкой

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

Примечание: без обратного прохода этот сценарий был наихудшим случаем для сортировки «Милосердный Сталин», где она даже уступала пузырьковой сортировке и сортировке вставками.

Частично отсортированные массивы

10% Несортированные		е
30% Несортированные 50% Несортированны

Алгоритм показывает улучшенную производительность по мере увеличения степени сортировки. Он выигрывает от начальных проходов, собирающих более крупные сортированные последовательности, уменьшая размер массивов, требующих рекурсивной сортировки. Сортировка Merciful Сталина, похоже, работает лучше с меньшим количеством несортированных элементов. Для массива, содержащего всего 10% несортированных элементов, она даже соперничает с сортировкой слиянием, однако по мере уменьшения сортировки массива она начинает отставать от сортировки слиянием и быстрой сортировки, которые менее чувствительны к начальному порядку.

Спектакль «Милосердный Сталин Сорт»

Эмпирические результаты показывают, что хотя сортировка Merciful Сталина немного выигрывает от начального упорядочения элементов, она не может сравниться по эффективности с такими алгоритмами, как Merge Sort и Quick Sort на больших или случайно упорядоченных наборах данных. Накладные расходы на множественные проходы и рекурсивные вызовы становятся значительными по мере увеличения размера массива. Более того, для каждого рекурсивного вызова алгоритм не может элементаризировать достаточное количество элементов, чтобы добиться какого-либо значимого прироста производительности.

По сравнению с сортировкой пузырьком и сортировкой вставкой сортировка Merciful Сталина работает лучше на больших массивах, особенно когда массив частично отсортирован. Это подчеркивает ее относительно лучшую производительность в среднем случае по сравнению с этими простыми алгоритмами сортировки.

Потенциальные улучшения

Направление паса на основе эвристики

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

Адаптивная отправная точка

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

Заключение

Сортировка Merciful Сталина представляет интересную концепцию, пытаясь оптимизировать сортировку посредством выборочного удержания элементов и рекурсии. Однако эмпирическое тестирование показывает, что она не превосходит традиционные алгоритмы сортировки для большинства общих случаев использования. Алгоритм превосходен, когда массив уже отсортирован, частично отсортирован или отсортирован в обратном порядке, но испытывает трудности со случайными данными.

Источник: github.com

Комментарии: