И еще о сортировке Рискну поднять эту тему еще раз.
начну со ссылки на статью Михаил Опанасенко (oms7) , очень впечатляет как по объёму проделанной работы, так и по количеству предоставленных ссылок.
Я начал готовить свой материал, не зная об этом издании, что впоследствии, после ознакомления, привело к необходимости его существенной переработки.
Для тех, кто уже прочитал эту статью, сообщаю, что в моем материале рассматриваются более разнообразные типы данных, в частности, строки и вещественные числа, используются библиотеки boost и bsd, а также затрагиваются некоторые другие темы, отсутствующие в названной статье.
.
Существуют десятки различных способов упорядочить элементы данных.
Среди них есть те, которые работают быстро, например, они могут отсортировать любой массив данных, расположенный в оперативной памяти компьютера, максимум за минуты.
Точнее, быстрая сортировка может отсортировать миллиард целых чисел на хорошем современном персональном компьютере менее чем за сто секунд. Если для сортировки большего количества элементов использовать примитивные, медленные методы, например, сортировку пузырьком или сортировку выбором, то время, затрачиваемое на такую обработку данных, может превзойти любые ожидания – такая «обработка» реально может занять несколько дней, недель и даже годы.
Такая большая разница обусловлена тем, что время сортировки быстрыми методами занимает величину, примерно пропорциональную Н бревно Н , и примитивный – Н 2 .
С ростом Н разница между двумя значениями становится очень заметной.
Поэтому примитивные методы разумно использовать только для работы с небольшими объемами данных, например, на современных компьютерах до нескольких тысяч элементов.
Их также естественно использовать для обучения основам программирования и логического мышления, поскольку они намного проще, чем быстрые методы.
Я хотел бы понять методы сортировки, существующие в текущих стандартных библиотеках.
Узнайте, насколько велика между ними разница по основным характеристикам, скорости работы, а также их характерным особенностям.
Кроме того, мы также рассмотрим для сравнения и умственных упражнений некоторые простые в реализации методы.
Также стоит отметить, что оптимизатор компилятора GCC и, возможно, других хороших компиляторов очень хорошо работает с сортировками, ускоряя код в несколько раз (иногда даже более чем в 5 раз).
Давайте начнем с пузырьковый метод (пузырьковая сортировка) как самая простая и медленная.
Используя этот метод, вам нужно снова и снова проходить по массиву данных, сравнивая соседние элементы и меняя их местами, если порядок между ними нарушен.
После каждого прохода хотя бы один элемент (самый большой или самый маленький — в зависимости от выбранного порядка) оказывается на своем месте.
Помимо простоты, у этого метода есть еще одно преимущество: он не требует дополнительной памяти.
Можно отметить еще одну особенность пузырькового метода – он очень быстро обрабатывает уже упорядоченные данные и это в ряде случаев делает его одним из самых быстрых методов.
Если данные упорядочены лишь частично, этот метод работает быстрее, но в большинстве случаев лишь незначительно быстрее.
Для тестов я использовал следующее выполнение .
Еще один медленный метод — сортировка выбор (сортировка выбором).
Здесь на каждом проходе сначала находятся самые большие и самые маленькие элементы в данных, а затем эти элементы помещаются в крайние позиции, соответствующие выбранному порядку.
На следующем проходе мы сортируем данные без этих внешних элементов.
Этот метод так же прост, как пузырьковая сортировка, и также не требует дополнительной памяти, но заметно быстрее.
Более того, сортировка с использованием этого метода выполняет рекордно минимальное количество перестановок элементов данных.
Следовательно, в тех случаях, когда перестановки выполняются значительно медленнее, чем сравнения, упорядочивание путем выбора может быть целесообразным, если количество элементов данных невелико.
Вот мой выполнение .
Чаще такая сортировка реализуется путем расстановки на место только одного элемента за проход. Сортировка в куче (или пирамидальная), о которой пойдет речь ниже, является наиболее продвинутым вариантом рассматриваемой сортировки.
Код для последнего обсуждавшегося медленного метода: сортировка вставкой (сортировка вставками), вероятно, самый короткий среди всех кодов, реализующих сортировку, поэтому этот метод иногда используется в сложных быстрых сортировках для случаев, когда количество сортируемых элементов невелико (несколько десятков).
Это чем-то похоже на сортировку пузырьком, поскольку последовательно сравниваются оба соседних элемента.
Но сортировка вставкой находит правильную позицию для следующего элемента в уже отсортированной части данных, а не просто перемещает крайний элемент во внешнюю позицию.
Этот подход также не требует дополнительной памяти.
Как и пузырьковая сортировка, сортировка вставкой выполняется очень быстро для упорядоченных данных и быстрее для частично упорядоченных данных.
В последнем случае он заметно быстрее пузырькового.
Обычно сортировка вставкой выполняется немного быстрее, чем сортировка выбором.
И в отличие от последней, она, как и пузырьковая сортировка, стабильна.
Сортировка вставкой хуже всего работает с данными в обратном порядке, с которыми она иногда бывает самой медленной из медленных.
Для испытаний использовалось следующее выполнение .
Его можно немного ускорить, если вместо линейного поиска использовать двоичный поиск, например, с помощью функции std::bsearch. Значительного ускорения можно добиться, если использовать структуру типа списка, в которой вставка элемента происходит очень быстро.
Также можно отметить, что это самая естественная сортировка – она, например, обычно используется интуитивно при игре в карты.
Сортировка Шелла (сортировка оболочки) является самым простым среди быстрых методов и вполне подходит для реализации студентами, только начинающими изучать программирование.
Это всего лишь модификация пузырьковой сортировки.
Единственное отличие между ними состоит в том, что в сортировке Шелла расстояние между сравниваемыми элементами принимается меняющимся от прохода к проходу: от большего на первом проходе до 1 на последних, таким образом, на этих последних проходах метод Шелла вырождается в примитивная пузырьковая сортировка.
Дональд Шелл опубликовал базовый алгоритм сортировки, носящий его имя, в 1959 году.
Таким образом, это одна из первых универсальных сортировок, которая работает быстро.
Для сравнения, алгоритм быстрой сортировки был опубликован двумя годами позже, а популярная ныне сортировка Тима или интроспективная сортировка стала известна только в 90-х годах.
Есть несколько интересных нерешенных математических проблем, связанных с сортировкой Шелла, главная из которых — как оптимально выбрать смещения между сравниваемыми элементами.
Удалось найти несколько последовательностей записей, например, А102549 .
Такие последовательности находятся посредством огромных вычислений, поэтому они очень короткие по длине: A102549 состоит всего из 8 элементов, чего достаточно только для данных, содержащих до 3000 элементов.
Для больших данных продолжение нужно искать практически случайным образом.
Использованы значения, близкие к степеням 2, е , 2,25 и 3. Простые числа, близкие к степени двойки, показали худшие результаты, заметно уступая лучшим.
А вот остальные три варианта оказались примерно одинаковыми по влиянию на производительность и, вероятно, очень близки к оптимальным.
Причём в этих трёх случаях использование простых чисел не дало ощутимых преимуществ.
Любопытно, что предложенные в Википедии смещения (с базой 2,25) на основе ссылок на соответствующие работы показали не лучшие результаты в тестах, хотя их отличия от лучших были весьма незначительными (не более 5-10%).
Использование А102549 в качестве исходного также не дало заметных результатов.
Михаил Опанасенко также попробовал решить сортировку Шелла и получил интересный результат: смещения, выбранные по формуле с п+1 = 10 с н /3 , дают очень хороший эффект и возможно даже близкий к идеальному.
Мои результаты подтверждают это.
Во многих случаях именно такие смещения давали лучший результат, хотя это было не всегда так и отрыв от ближайшего результата был очень небольшим (около 5%).
Мой код Для реализации сортировок Shell использует небольшие таблицы со смещениями, хотя если не использовать простые числа, то эти смещения для таблиц можно вычислить практически мгновенно, как это было сделано в реализации одного из приведенных вариантов такой сортировки.
Интересно, что если смещения, близкие к степеням тройки, взять немного по-другому и использовать немного другой алгоритм (см.
выполнение ), то на 32-битных числах мы получим скорости, близкие к лучшим, а вот на более длинных числах и на строках получим существенное замедление, иногда более чем на 100%.
Результаты лучшего алгоритма, используемого oms7, также есть в таблице ниже, но хотя он и показывает хорошие результаты по порядку величины, в абсолютных значениях он заметно отстает от лидеров.
Будет ли когда-нибудь способ найти оптимальные смещения? Возможно, но, полагаю, это будет не скоро.
Сортировка Шелла используется в ядре Linux, и по крайней мере одна библиотека C использует ее код для стандартной функции qsort().
Теоретически доказано, что сортировка оптимального порядка Шелла лишь незначительно медленнее, чем «настоящие» быстрые логарифмические методы.
Действительно, зависимость среднего времени обработки данных от их размера для оптимальной сортировки Шелла описывается формулой ∽ Н (бревно Н /log журнал Н ) 2 , что даже для очень больших Н очень близко к формуле ∽, типичной для других быстрых методов Н бревно Н .
Как правило, сортировка Шелла зачастую даже быстрее теоретически более быстрых методов на порядок и начинает им немного уступать только при обработке достаточно больших массивов (порядка 10 миллионов элементов).
Такая сортировка вообще не требует никакой дополнительной памяти и ведет себя стабильно для самых разных вариантов заполнения данных, чем выгодно отличается от быстрых сортировок.
Метод Шелла не обладает свойством устойчивости.
Быстрый Быстрая сортировка лишь немного сложнее алгоритма Шелла и по-прежнему остается одним из самых быстрых способов организации случайно разбросанных данных.
Однако такая сортировка имеет ряд недостатков.
Он требует дополнительной памяти и в очень редких случаях работает крайне медленно, по квадратичной зависимости.
Основная идея этого метода — разделить данные на две части: данные в одной части должны быть больше или меньше (в зависимости от выбранного порядка), чем в другой.
Есть несколько способов сделать это разделение.
В идеале при каждом делении обе части должны получиться примерно одинаковыми по размеру, и самое худшее случается, когда при делении одна из частей оказывается состоящей всего из одного элемента.
Рассмотрим несколько реализаций алгоритмов быстрой сортировки, в частности: Метод Хоара , в котором опорный элемент, разделяющий данные на две части, выбирается из середины сортируемых данных.
Обратите внимание также на чрезвычайно компактный Алгоритм Ломуто , что иногда немного (около 1%) быстрее рассмотренного метода Хоара.
Однако в типичных особых случаях, например, на упорядоченных, обратных данных или данных с малой дисперсией, метод Ломуто показывает крайнюю медлительность.
Кроме того, среди рассмотренных вариантов быстрой сортировки этот оказался самым жадным по размеру стека в практических прогонах: при сортировке относительно небольших массивов только этой сортировке не хватило 8 мегабайт на стек, поэтому мне пришлось чтобы установить этот размер больше через ulimit. Такая жадность к стеку приводит при обработке больших данных (десятки миллионов строк) к значительному замедлению работы, природу которого сложно назвать.
Могу только констатировать, что с такими данными лучше не использовать эту и сортировку из следующего пункта.
Метод Ломуто выбирает последний элемент в качестве ссылочного элемента, но можно реализовать быструю сортировку без каких-либо действий.
опорный элемент Точнее, выбор такого элемента здесь происходит в результате уже выполненного деления данных пополам.
Такая сортировка по скоростным характеристикам оказалась близка к методу Ломуто, хотя обычно немного быстрее, а в крайних случаях — заметно быстрее, чем Ломуто, но медленнее, чем Хоара.
Опубликовано в 2009 г.
алгоритм Быстрая сортировка с двумя опорными точками, ставшая стандартной в языке Java. Этот алгоритм уменьшает количество перестановок на 20% по сравнению с лучшими стандартными, но количество сравнений не меняется.
Ее автор – Владимир Ярославский.
Это действительно работает, как правило, быстрее, чем другие быстрые сортировки.
Я его немного оптимизировал, воспользовавшись давно известным фактом, что в архитектуре x86 обмен обычно выполняется быстрее, чем присваивание, а для строк C++ — гораздо-намного быстрее.
Все рассмотренные до сих пор быстрые сортировки не обладают свойством устойчивости.
Дополнительная память для быстрой сортировки необходима для организации рекурсивных вызовов.
Однако второй такой вызов можно заменить циклом, оптимизировав хвостовая рекурсия , что может и не дать никакого прироста скорости, но существенно уменьшает размер используемых дополнительных данных.
С этой оптимизацией я реализовал вариант сортировки Хоара.
Кроме того, в системных программах можно проверить указатель стека и если он приблизится к критическому значению, то можно просто сбросить все рекурсивные вызовы и начать сортировку заново — для этого случая очевидно, что нужно использовать опцию быстрой сортировки, которая не тормозит на почти упорядоченных данных, например, предложенная выше версия Хоара.
Борьбу с дополнительным использованием памяти можно считать основной идеей быстрой сортировки из стандартной библиотеки C в GCC. Он полностью отказался от рекурсии.
Вместо этого используется его симуляция, позволяющая снизить нагрузку на стек на треть.
Код оказался довольно большим, около 150 строк.
Подробнее об этой сортировке будет сказано ниже.
Сортировка хэш (хеш-сортировка) может быть очень быстрой, близкой к ∽ Н .
Однако иногда это может работать и по квадратичной зависимости.
Скорость этого метода сортировки сильно зависит от входных данных.
Если данные равномерно распределяются хэш-функцией по вспомогательному массиву, то мы получаем максимально быструю линейную зависимость.
А если все данные сгруппированы возле нескольких далеко разнесенных «центров масс» или когда имеется много одинаковых элементов данных, т.е.
когда происходит много хеш-коллизий, то мы получаем худшую зависимость типа ∽ Н 2 .
Как и сортировка дерева, хеш-сортировка требует довольно много дополнительных данных.
листинг Например, коду требуется 12 дополнительных байтов для каждого сортируемого целого числа (int32, x86-64).
Интересным свойством хеш-сортировки является отсутствие операций сравнения между элементами данных, что отличает эту сортировку от всех рассмотренных выше.
Точнее, эти операции нужны только в случае коллизий.
При сортировке данных, где ключ соответствует всему элементу данных, можно использовать дополнительный счетчик количества одинаковых элементов, но это довольно сомнительная оптимизация.
Вы также можете использовать двоичное дерево вместо списка для хранения данных о коллизиях хэшей; это существенно ускоряет работу для некоторых частных случаев, когда коллизий много, но в целом работа при использовании бинарного дерева во многих случаях замедляется, и это несмотря на то, что в этом случае поэлементные данные приходится хранить почти 100 байт дополнительной информации.
Я реализовал три варианта хеш-сортировка с использованием двоичного дерева: один использует неупорядоченное дерево, а два других используют стандартные деревья из библиотек std и boost. Хэш-сортировка практически непригодна для сортировки текстовых строк, за исключением очень коротких, поскольку для таких данных невозможно сделать хорошую хеш-функцию.
Стандартный C++ хеш (unordered_multiset) адаптировать для сортировки мне не удалось: пробовал использовать монотонные хеш-функции и отношения упорядочивания вместо равенства — не получилось.
Сортировка массива очень похожа на предыдущую.
Также используется вспомогательный массив, куда значения вводятся с помощью хэш-функции.
В случае коллизии нужно сдвинуть смежный фрагмент занятых элементов на позицию влево или вправо, освободив позицию, указанную хеш-функцией, для нового элемента.
Для получения хорошей скорости необходимо, чтобы вспомогательный массив был в несколько раз (от 2-3) больше исходного.
По мере увеличения размера вспомогательного массива скорость работы увеличивается лишь до определенного предела, в зависимости от сортируемых данных и связанной с ними хеш-функции, а затем (обычно от 4-5) падает. Скорость работы примерно такая же, как и у хеша, но на хороших данных немного быстрее, а на плохих — заметно медленнее.
Этот сорт также требует довольно много дополнительной памяти.
Если ограничить количество элементов в отсортированном массиве чуть более четырех миллиардов, то утроенный вспомогательный массив потребует такого же объема дополнительных данных, как и хеш-сортировка, а 7-й вспомогательный массив потребует 28 байт, что заметно меньше.
чем для сортировки по деревьям или гораздо меньше, чем для хэш-сортировки с деревьями.
Этот сорт также практически непригоден для работы со строками.
В Википедии нет статьи о таком алгоритме, но вот моя выполнение .
Интересно, что в Википедии, в хорошем обзоре статья Совсем не упоминаются промежуточные методы, такие как сортировка массива и хэша, которые естественным образом подходят между методами, основанными на сравнении элементов, и методами, основанными на абсолютном значении элементов.
Здесь также можно отметить, что аппаратное и программное обеспечение обычно поддерживают бесконечные значения реального типа, и работа с такими значениями может сильно усложнить алгоритмы сортировки, не использующие сравнения.
Мои реализации таких алгоритмов не поддерживают работу с бесконечностями.
Один из самых быстрых сортов, вообще никогда не использующий сравнений, известен еще с 19 века.
поразрядная сортировка (поразрядная сортировка).
Его идея очень проста — нужно работать с группами бит представления данных (для тестов я брал группы по 8, 11 и 16 бит).
Для каждой группы строятся таблицы, а затем результаты сравнительно простым способом объединяются.
Существует два основных способа использования поразрядной сортировки.
Для сортировки чисел удобнее брать цифры справа налево (это вариант LSD — Lest Significant Digit), а для сортировки строк — слева направо (это вариант MSD — Most Significant Digit).
Сортировка по радиусу часто выполняется значительно быстрее, чем любой другой метод упорядочивания данных.
На удивление, поддержка поразрядной сортировки пока не очень существенна: ее нет ни в boost, ни в стандартной библиотеке C++, мне даже не известна ее версия ни для одной известной библиотеки для работы с числами или строками C++.
Конечно, такая сортировка имеет свои недостатки.
Он очень чувствителен к типу сортируемых данных, например, нужно иметь свой вариант такой сортировки для данных каждого размера, нужно сделать специальные опции для беззнаковых и знаковых целых чисел, а также поддержку работы с вещественными числами.
может потребовать довольно больших усилий.
Его вариант при использовании порядка от младшего байта к старшему обычно требует дополнительной памяти, немного большей, чем для исходных данных (это существенно меньше, чем для сортировки по хешу или массиву и тем более по дереву).
Кроме того, эта опция малопригодна для сортировки длинных строк.
Мой код для этой сортировки Здесь , он основан на коде из упомянутой статьи oms7. Вариант с прямым порядком байтов более универсален и очень хорошо подходит для сортировки строк.
Этот вариант можно реализовать без использования дополнительной памяти (цена этого — потеря стабильности), как это сделано в функции radixsort() библиотеки bsd. Мой код для этого варианта он также основан на коде oms7, он за счет использования дополнительной памяти, несколько большего размера исходных данных, обладает свойством стабильности, но не оптимизирован под строки и поэтому показывает существенно худшие характеристики производительности чем аналогичная функция sradixsort() из уже упомянутой библиотеки bsd. Эта сортировка может работать на удивление плохо при работе с небольшими числовыми массивами, работая на несколько порядков медленнее, чем даже пузырьковая сортировка, хотя мы говорим об очень малых количествах, не более нескольких миллисекунд, и разницу заметить непросто.
Это происходит потому, что он использует небольшие вспомогательные массивы, но при сортировке небольших данных эти небольшие размеры могут быть больше, чем сами отсортированные данные.
Чтобы избежать замедления, в таких случаях опция слева направо использует сортировку вставками вместо основной сортировки.
В заключение стоит отметить, что это единственная известная мне относительно популярная сортировка, которая всегда надежно работает на скорости ∽ Н , но коэффициент пропорциональности здесь зависит от размера элементов данных и для строк или длинных чисел он может быть весьма заметен.
Вариантом поразрядной сортировки MSD является сортировка.
луч , структура данных, позволяющая эффективно хранить ключи ассоциативного массива.
Мой выполнение , несмотря на оптимизацию использования памяти, всё равно оказался очень жадным.
С точки зрения скорости лучшие результаты были получены при сортировке длинных строк.
Далее мы рассмотрим некоторые виды, которые можно найти в стандартных библиотеках.
Начнем с быстрого из стандартной библиотеки C (qsort, вариант GCC), о нем я уже писал.
Могу лишь добавить, что эта сортировка, как и другие C-сортировки (например, следующая из библиотеки BSD), непригодна для работы с объектными данными, в частности, строками C++, что связано с тем, что такие данные нет ПОД .
Имея исходники, проблему можно легко решить, заменив операции типа memcpy обычными присваиваниями.
Вы также можете заметить, что в некоторых стандартных библиотеках C такая сортировка не обязательно будет быстрой; его можно заменить другими.
В текущей версии для GCC эта сортировка даже обладает свойством стабильности.
С упомянутыми си-сортами иногда возникали неожиданности при сборе данных; они могли, например, при работе с типом std::vector через функциональный объект создать сложности — могу рекомендовать использовать его с объектными данными с осторожностью.
Судя по прогонам, такая сортировка иногда бывает относительно медленной: она заметно уступает по скорости другим реализациям быстрой сортировки при работе с числами, но при работе с C-строками она оказывается лучшей, только сортировка с двумя опорными точками иногда удаётся обгонит ее, но на длинных линиях ее почти всегда обгоняет стандартный qsort. Самое интересное обнаружилось при попытке отсортировать с его помощью миллиард целых чисел — оказалось, что заполнение типа 7 приводит к зависимости от времени, близкой к квадратичному закону, т.е.
к возможной «обработке», продолжающейся до нескольких лет (я не дождался конца и остановил его на 21 часе пробега).
На небольших данных такая сортировка обычно позволяет выбрать контрольные точки, с которыми она работает быстро.
интроспективный сортировка используется в стандартной библиотеке C++, хотя точный метод, используемый в std::sort, зависит от реализации, информация предоставляется только для GCC. По прогонам это второе место после сортировки по спреду при работе с числами, причем преимущество сортировки по спреду невелико (почти от 0 до 30%), а вот с сортировкой строк все гораздо хуже - может быть 3-4 раз уступает лидерам.
На самом деле это быстрая сортировка, которая учитывает два особых случая: 1) если количество рекурсий становится слишком большим, то происходит переключение на сортировку кучей; 2) если количество сортируемых элементов невелико, то система переключается на сортировку вставками.
Надежная сортировка из стандартной библиотеки C++ ( std::stable_sort ), как следует из названия, обладает свойством персистентности — он сохраняет относительный порядок между элементами с одинаковым ключом.
Это свойство требуется сравнительно редко, хотя пишу об этом довольно голословно, лишь исходя из собственного опыта.
Можно использовать дополнительную память, что делает работу быстрее.
Удивительно, но такая сортировка зачастую выполняется быстрее, чем std::sort. Суперпопулярный язык Python стандартно использует сортировку.
Тим .
Для тестов я использовал его версию от репозиторий GitHub .
Он показывает рекордные результаты на частично упорядоченных данных, но в среднем все равно заметно медленнее лидеров.
Обычно его скорость средняя между быстрой сортировкой и сортировкой Шелла, хотя на рядах она иногда близка к лидерам.
Имеет свойство устойчивости.
Он реализует относительно сложный алгоритм, в стандартной реализации которого в 2015 году была обнаружена ошибка, которая, однако, требует для своего проявления достаточно нереальной ситуации.
Библиотека BSD C имеет поразрядную сортировку ( поразрядная сортировка ) и его стабильный вариант (sradixsort).
К сожалению, оба этих типа можно использовать только для C-строк.
Как будет видно из тестовых данных, на сегодняшний день это самый быстрый способ сортировки строк, и поэтому удивительно, что для строк C++ не существует стандартной версии.
В библиотеке BSD C также есть сортировка.
слияние ( Сортировка слиянием ).
Известно, что эта сортировка является одной из самых быстрых для данных с последовательным доступом (файлов, списков) и, возможно, используется в стандартной библиотеке C++ для сортировки списков (std::list и std::forward_list).
Кстати, она известна с 1948 года и одним из ее разработчиков был очень известный математик и специалист по первым вычислительным системам фон Нейман.
Среди быстрых методов этот сорт обладает не лучшими характеристиками, хотя, как правило, несколько быстрее методов Шелла.
Он требует дополнительной памяти и обычно реализуется надежно.
Кроме того, есть сортировка.
в куче (кучковая сортировка).
Куча обычно используется для организации очереди с оптимальным приоритетом, но ее также можно использовать для сортировки.
Кучиные сортировки не требуют дополнительной памяти, но не обладают свойством стабильности.
По скорости работы с числами он значительно (до 3-6 раз) медленнее методов Шелла, но для не очень коротких строк показывает очень хорошие результаты, обгоняя (с увеличением длины строки преимущество увеличивается) методы Шелла.
Сортировка пирамидой также имеется в стандартной библиотеке C++.
Эта сортировка выполняется в две операции: построение кучи (std::make_heap) и последующая сортировка ( std::sort_heap ).
Здесь, в отличие от библиотеки bsd, сортировка — это именно одна из операций над кучей.
Обычно этот вариант сортировки немного быстрее предыдущего (опция bsd показывает лучшие результаты только на коротких числах и длинных C-строках).
Используя стандартную библиотеку C++, вы можете сортировать с помощью двоичного сбалансированного дерева (std::multiset) — просто заполните дерево и затем пройдите его.
Вы можете думать об этом методе как о нерекурсивной быстрой сортировке.
Возникает проблема, что стандартный распределитель памяти работает заметно медленно, поэтому для лучших результатов необходимо использовать собственный распределитель, который ускоряется примерно на 10-30%.
Также можно отметить, что этот метод требует много дополнительной памяти, при этом g++ для каждого элемента данных помимо него самого нужно хранить еще и 32 байта (на архитектуре x86-64) - было бы интересно попробовать хранить такое дерево как кучу, т.е.
без дополнительного байта.
Если вы используете boost::container::multiset, вам потребуется меньше памяти: всего лишь дополнительные 24 байта на элемент данных.
Однако и Boost, и стандартная библиотека преподнесли один неприятный сюрприз — во время работы они иногда требовали больше памяти, чем необходимо.
Это может быть связано с балансировкой бинарных деревьев.
Коды – Здесь .
Библиотека повышения имеет Теги: #Алгоритмы #программирование #C++ #структуры данных #тестирование производительности #STL #алгоритмы сортировки #Обработка #boost #строки #timsort #сортировка выбором #пирамидальная сортировка #кучичная сортировка #BSD #пузырьковая сортировка #пузырьковая сортировка #сортировка вставками #introsort #radixsort #быстрая сортировка #сортировка вставкой #сортировка кучей #сортировка слиянием #сортировка по основанию #сортировка слиянием #сортировка по дереву #сортировка оболочкой #сортировка по массиву #хеш-сортировка #сортировка лучом #интроспективная сортировка #расширенная сортировка #pdqsort #спин-сорт #плоская_стабильная сортировка #std::sort # std::stable_sort #std::qsort #lomuto sort #dualpivot sort #сортировка выбором #пузырьковая сортировка
-
Кикстартер – Год Игр
19 Oct, 24 -
Моделирование Динамических Систем: Введение
19 Oct, 24
