Сортировка вставками с линейным поиском Она же «Insertion sort». Относится к классу «сортировок со вставками». Сложность сортировки в лучшем случае (полностью отсортированный массив) [math]O(\frac{n\cdot(n-1)}{2})[/math], в среднем ― [math]O(\frac{n\cdot(n-1)}{1.3})[/math], в худшем (массив отсортирован в обратную сторону) ― [math]O(n\cdot(n-1))[/math]. Для вставки используется буферная область памяти, в которой хранится элемент, еще не вставленный на свое место (так называемый «ключ»). Сам ключ отправляется в буфер, в результате в массиве появляется свободная ячейка — это позволяет сдвигать элементы и освободить точку вставки. В подмассиве, начиная с конца отрезка, перебираются элементы, которые сравниваются с ключом. Если элементы больше ключа, тогда они сдвигаются на одну позицию вправо, освобождая место для последующих элементов. Если в результате этого перебора попадается элемент, меньший или равный ключу, тогда в текущую свободную ячейку вставляется ключевой элемент. В аттаче asm-/rc-/exe-файлы и курсор
Я пока завис на оптимизацией свой сортировки. В общем, сделал, прикрутил к тесту, и туда же библиотечную qsort из MSVCR100.dll, и... квик оказался в 1.5-2 быстрей, вот так. Думаю проблема с кешем, не оптимально, как я уже говорил, дергано обращается, сравнений (countComp) происходит меньше, и код в целом быстрей, но на практике код более медленный, хотя по идеи должен быть быстрей. И ещё медленно работает с уже полностью отсортированным массивом. Надо менять сам алгоритм сортировки, и избавится от хвостовой рекурсии, как мы помним в 19-ти ферзях тоже хвостовая рекурсия была, я потом от неё избавился и скорость хорошо поднялось, в несколько раз. На практике код сортировки строк мне может понадобится для XRayExtensions для правильной смены типа гранат.
alex_dz, на сам деле проще, это сам алгоритм очень не оптимально работает с маленькими корзинами, т.е. если там осталось 2-8 элементов, и таких корзин очень много, оверхид уже приличный, вот и проседает быстродействия. Теперь если размер корзины 8 и меньше, то запускаем банальный пузырёк, и... код стал работать быстрей, и сейчас обгоняет квик(раньше 700-900 мс(вот так с по-разному), а теперь 325-361 мс, а квик 423-462 мс. Таким макаром можно и больше комбинаций сортировок запускать, но тут только длительные тесты/эксперименты что-то скажут.
Сортировка вставками с бинарным поискомОна же «Insertion sort (binary search)». Относится к классу «сортировок со вставками». Сложность сортировки в лучшем (полностью отсортированный массив), в среднем и в худшем случае (массив отсортирован в обратную сторону) ― [math]O(\frac{n\cdot(n−1)}{1.97})[/math]. Место для вставки обнаруживается с помощью бинарного поиска. Наблюдается небольшое приращение скорости для среднего случая по сравнению с сортировкой простыми вставками с линейным поиском. В аттаче asm-/rc-/exe-файлы и курсор
Сортировка парными вставкамиОна же «Pairwise Insertion Sort». Относится к классу «сортировок со вставками». Сложность сортировки в лучшем случае (полностью отсортированный массив) [math]O(\frac{n\cdot(n−1)}{18.9})[/math], в среднем ― [math]O(\frac{n\cdot(n−1)}{3.3})[/math], в худшем (массив отсортирован в обратную сторону) ― [math]O(\frac{n\cdot(n−1)}{1.9})[/math]. Количество элементов в массиве [math]n[/math] должно быть нечетным. В буфер отправляются два рядом стоящих элемента. Элемент с бòльшим значением выставляется ближайшим к отсортированному подмассиву. Сперва метод простой вставки применяется к бòльшему элементу из пары. Место для вставки обнаруживается с помощью бинарного поиска. Затем метод простой вставки применяется к меньшему элементу из пары. Так как меньший элемент обрабатывается после вставки бòльшего, поэтому при поиске места вставки пропускается область, в которую произошла вставка бòльшего элемента. Это сокращает расходы на обработку меньшего элемента из пары. В аттаче asm-/rc-/exe-файлы и курсор
Голубиная сортировка Она же «Pigeonhole Sort», она же «Сортировка Дирихле», она же «сортировка по полочкам», она же «групповая сортировка». Относится к классу «сортировок с распределением». EnglishВарианты переводаPigeon(голубь)+hole (дыра)=Pigeonholeжопа голубяотделение для бумагзакутокголубиное гнездораскладывать по ящикамнебольшое углубление для гнезда домашнего голубяабонентская ячейка на почте или банковская ячейка в банкекатегория, обычно чрезмерно ограничительная, к которой относят кого-то или что-то.положить (документ) в ячейкуСложность сортировки в лучшем, среднем и в худшем случае [math]O(n+k)[/math], где [math]n[/math] ― размер массива, [math]k[/math] ― ранг массива. Первый раз проходим по массиву и находим минимальный и максимальный элементы массива. Вычисляем ранг массива [math]k=max-min+1[/math], заводим [math]k[/math] счетчиков. Второй раз проходим по массиву, от значения каждого элемента отнимаем значение [math]min[/math] и инкрементируем соответствующий счетчик. Подсчитываем сколько раз в массиве счетчиков встречается каждое значение, пропускаем счетчики заполненные нулем и заполняем исходный массив элементами равными (номер счетчика+значение [math]min[/math]) в соответствующих количествах. В аттаче asm-/rc-/exe-файлы и курсор
Двухсторонняя сортировка выборомОна же «Double Selection Sort». Относится к классу «сортировок выбором». Сложность сортировки в лучшем случае (полностью отсортированный массив) [math]O(\frac{n\cdot(n−1)}{1.93})[/math], в среднем ― [math]O(\frac{n\cdot(n−1)}{1.92})[/math], в худшем (массив отсортирован в обратную сторону) ― [math]O(\frac{n\cdot(n−1)}{0.97})[/math]. При проходе по массиву, отыскиваются максимум и минимум. Минимум устанавливается на первое место, максимум на последнее. Еще раз проходим по неотсортированной части массива (от второго элемента до предпоследнего) и опять находим в ней максимум и минимум, которые меняем со вторым и предпоследним элементом. Неотсортированная часть с каждым проходом уменьшается сразу на два элемента. Проходы продолжаются, пока массив не отсортируется полностью. По сравнению с обычной сортировкой выбором количество сравнений увеличилось в 2 раза, число перестановок осталось неизменным. Двухсторонний выбор незначительно увеличивает скорость сортировки. Возможна коллизия ― когда вместо найденного максимума оказался элемент, появившийся при обмене минимального и первого элемента массива. В таком случае проход с поиском минимального и максимального элемента повторяется. В аттаче asm-/rc-/exe-файлы и курсор
Бинго-сортировкаОна же «Bingo Sort». Относится к классу «сортировок выбором». Сложность сортировки в лучшем случае (полностью отсортированный массив) [math]O(\frac{n\cdot(n−1)}{1.9})[/math], в среднем ― [math]O(\frac{n\cdot(n−1)}{2.2})[/math], в худшем (массив отсортирован в обратную сторону) ― [math]O(\frac{n\cdot(n−1)}{1.9})[/math]. Модификация простой сортировки выбором, позволяющая быстрее сортировать массивы, состоящие из повторяющихся элементов. В неупорядоченной части запоминается не только максимальный элемент, но и определяется максимум для следующей итерации. Это позволяет не искать повторяющиеся максимумы заново, а ставить их на свое место сразу, как только максимум в очередной раз встретили в массиве. В аттаче asm-/rc-/exe-файлы и курсор.
https://ru.wikipedia.org/wiki/«O»_большое_и_«o»_малое "фраза «сложность алгоритма есть » означает, что с увеличением параметра , характеризующего количество входной информации алгоритма, время работы алгоритма будет возрастать не быстрее, чем умноженная на некоторую константу;" Константа не обязана быть > 1.
Mikl___, возможно и у меня и в Вики несколько устаревшее представление об О-большом. Спасибо за поддержку форума от Супермодератора.
Так в возрасте к современным изменениям представлений о мире на... https://rosettacode.org/wiki/Rosetta_Code http://algolab.valemak.com/sorting https://habr.com/ ("и разных прочих шведов") маразмастойкости не наблюдается. Ну да - это скорее сарказм интернета над старыми, более стабильными системами понятий. "только с целыми" - ну "Семен Семенович". Вот все тут х64... х64. Предположительно: если чуть "поколдовать" с преобразованием формата, то 16GB вполне достаточно для сортирвки 4-х байтных чисел FPU с плавающей точкой! С не более чем 232-1 повторений. Можно и с 4GB начинать, а если более 127 повторов или 254 какие-то форматы выдумывать для и более 232-1 повторений, но будут ограничения на кол-во чисел с повторениями и т.д. и т.п. "Но принцу вредно много" писать. Хаджа Насредин. До начала "Вы переписываете на ассемблер алгоритмы сортировки" пожалуй "классификации <линейный>, <квадратный> и <кубический> будет достаточно". Прошу прощения: "Идея..., идея..., иде я нахожусь?" А если углубиться "(а их более 80)", при таком погружении наверняка возникнет.
Пасьянсная сортировка ver.1 Пасьянс (фр. patience — «терпение») — карточная игра для одного игрока. Играющий раскладывает карты, придерживаясь определенных правил или преследуя некоторую цель. В зависимости от правил цель может быть достижима в той или иной степени благодаря интеллектуальным усилиям играющего и благодаря случайности. «Пасьянсная сортировка», она же «Терпеливая сортировка», она же «Patience Sort» ― относится к классу «сортировок вставками». Сложность сортировки в худшем случае [math]O(n\cdot log_{2}(n))[/math], в лучшем случае ― [math]O(n)[/math] В аттаче asm-/rc-/exe-файлы и курсор
Пасьянсная сортировка ver.2Сделал так, чтобы было видно КАК формируются «стопки карт». «Карты» (элементы неупорядоченного массива) раскладываются в несколько стопок, так, чтобы в каждой стопке элементы представляли из себя упорядоченную последовательность — из имеющегося неотсортированного массива создается несколько упорядоченных подмассивов. Желательно, чтобы количество этих подмассивов было поменьше, а подмассивы были длиннее. Делается это следующим образом: Первая «карта» — начало первой стопки. В эту стопку перекладываем карты по очереди, до тех пор, пока очередная перекладываемая карта меньше или равна значению верхней карты в стопке. Каждая стопка является стеком — работаем не со всей стопкой, а только с верхней картой, которую положили последней. Если текущая карта больше, чем минимальная в стопке — текущая карта открывает новую стопку. Очередную карту кладем в самую левую стопку, в которую можем положить. В итоге карты разложены в несколько стопок. В каждой стопке карты — убывающая последовательность, сверху — карта с наименьшим значением. Разбираем подмассивы слева-направо. Самая верхняя карта в левом подмассиве — текущий минимум, возвращаем минимум в исходный массив. Каждый раз, когда возвращаем очередную карту в исходный массив, на освободившееся место кладем карту из стопок, что находятся в подмассивах левее — среди доступных карт выбирается минимум, который перемещается на вакантное место, а оттуда — в основной массив. Комбинируя работу с упорядоченной по возрастанию очередью и упорядоченными по убыванию стеками получаем все элементы от минимального до максимального. Для пасьянсной сортировки массива из [math]N[/math] элементов требуется дополнительная память размером [math]N^{2}[/math]. Если сортируется массив из отсортированных от меньшего к большему элементов, тогда получаем [math]N[/math] стопок с единственной картой в стопке. Если сортируется массив из элементов отсортированных от большего к меньшему — получим одну стопку из [math]N[/math] карт. Для неотсортированного массива потребуется дополнительная память размером [math]\frac{\displaystyle N^2}{\displaystyle 4}[/math], а может быть и меньше.В аттаче asm-/rc-/exe-файлы и курсор
Спящая сортировка Она же «Sleep sort» ― относится к классу «Параллельных сортировок». Параллельный алгоритм, сортирующий набор положительных чисел за линейное время. Сортировка реализуется на языках программирования, поддерживающих многопоточность. Для каждого элемента массива создается отдельный процесс, который «спит» количество миллисекунд равное значению элемента, а затем выводит значение этого элемента на экран. Меньшие числа выведутся первыми, бòльшие последними. Худшая, средняя и лучшая сложность по времени [math]O(n + max)[/math]. Можно сортировать и отрицательные вместе с положительными числами, но тогда их придется перевести в «смещенный вид», как в представлении степени вещественного числа. В аттаче asm-/rc-/exe-файлы и курсор
Спагетти-сортировка Она же «Spaghetti sort» ― относится к классу «Параллельных сортировок». Аналоговый параллельный алгоритм, сортирующий набор положительных чисел за линейное время. Идея та же, что и у «спящей сортировки». Представим массив неотсортиронных чисел в виде пучка из сухих спагетти соответствующей длины. Установим спагетти вертикально на ровной поверхности. Сверху на спагетти опускается пресс. Каждый раз, когда пресс касается очередной макаронины, фиксируем очередной отсортированный элемент и удаляем его из массива неотсортированных элементов. В данной версии не пресс опускается, а снизу от «спагетти» отрезается по «миллиметру». Для каждого элемента массива создается отдельный процесс, в котором через 1 миллисекунду на 1 уменьшается длина «спагетти». «Макарошку», чья длина обратилась в ноль, считаем отсортированной и копию «макаронины» отправляем в «пачку с отсортированными макаронами». Меньшие числа выведутся первыми, бòльшие последними. Худшая, средняя и лучшая сложность по времени [math]O(n)[/math] В аттаче asm-/rc-/exe-файлы и курсор
Библиотечная сортировка ver.1 Она же «Library sort», она же «Сортировка вставками с разрывами», она же «Gapped Insertion sort» ― относится к классу «Сортировок вставками».АлгоритмБиблиотекарю необходимо, чтобы книги были расставлены по алфавиту на длинной полке: начиная от буквы «А», до буквы «Я». Если в библиотеку поступает новая книга, относящаяся к разделу «Б», тогда, чтобы поставить ее в нужное место, придется перемещать каждую книгу, начиная от середины раздела «Б» до раздела «Я». Если библиотекарь зарезервирует свободное пространство в каждой секции, тогда ему достаточно переместить несколько книг, чтобы освободить место для новых поступлений. Это основной принцип библиотечной сортировки. Теперь по пунктам: Создается пустой вспомогательный массив, в несколько раз больший чем основной. Первый элемент переносится в середину вспомогательного массива. Ищется место вставки для очередного элемента во вспомогательном массиве. 3.1. Если найдено место для вставки, элемент переносится и происходит возврат к пункту 3. 3.2. Если места для вставки не находится, производится перебaлансировка вспомогательного массива и возврат к пункту 3. После обработки всех элементов они возвращаются в основной массив. Сперва вычисляют, сколько максимально ячеек можно выделить на каждый элемент во вспомогательном массиве. При этом пустые ячейки должны быть и перед первой, и после последней заполненной ячейки. ε — во сколько раз вспомогательный массив больше основного ([math]2\leqslant[/math] ε) [math]Size[/math] — размер основного массива ε[math]\times (Size + 1) − 1=NewSize[/math] — размер вспомогательного массива [math]Count[/math] — текущее количество непустых элементов во вспомогательном массиве. [math]\frac{\displaystyle NewSize+1}{\displaystyle Count+1}=M[/math] — количество ячеек, которое можно выделить на каждый элемент. Дробь округляют в меньшую сторону и приводят к целому значению. Чем больше элементов перенесено во вспомогательный массив, тем меньше ячеек можно выделить под окрестность каждого элемента. Зная [math]M[/math], получают точную позицию для каждого непустого элемента во вспомогательном массиве, на котором он должен находиться после завершения перебaлансировки. [math]Number[/math] — какой это по счету непустой элемент во вспомогательном массиве ([math]1\leqslant Number\leqslant Count[/math]) [math]Number\times M =NewPos[/math] — новая позиция элемента после перебaлансировки. Новые позиции известны, нужно не просто во вспомогательном массиве перебрать непустые элементы и перенести их на другие места, при этом нужно сохранить очередность элементов массива. В результате бинарного поиска и вставки элементы оказываются намного левее или намного правее той позиции, в которой они должны быть после перебaлансировки. На месте, куда нужно перенести, может стоять другой элемент, который нужно куда-то пристроить. Нельзя переносить элемент, если между его старой и новой позицией во вспомогательном массиве есть другие элементы — иначе элементы перемешаются, важно не перепутать порядок. Для перебaлансировки недостаточно пройтись циклом и переложить каждый элемент из одного кармана в другой. Используется рекурсия. Если элемент нельзя перенести на новое место (между его старой и новой позициями оказались другие элементы), то сначала нужно разобраться (рекурсивно) с этими непрошенными гостями. И тогда всё расставится правильно.Вырожденный случайДля большинства сортировок вставками упорядоченный в обратную сторону массив — наихудшая ситуация. Библиотечная сортировка не исключение. Элементы стремятся к левому краю вспомогательного массива, в результате чего свободные места быстро заканчиваются. Приходится очень часто делать перебaлансировку массива. Если взять почти упорядоченный массив (наилучший случай для сортировки простыми вставками), то получим ту же проблему. Вновь поступающие элементы будут забивать не левую, а правую часть вспомогательного массива, что также приведет к слишком частым перебaлансировкам. Библиотечная сортировка эффективно обрабатывает наборы случайных данных. Частичная упорядоченность (как прямая, так и обратная) ухудшает скоростные показатели.Алгоритмическая сложностьНа больших наборах случайных данных алгоритм дает временную сложность [math]O(n\cdot log_{2}(n))[/math]. На наборах случайных уникальных (или в основном уникальных) данных при правильном подборе коэффициента ε и удачной реализации бинарного поиска количество перебaлансировок можно свести к минимуму. Алгоритм имеет временную сложность [math]O(n)[/math]. Большой процент повторяющихся по значению данных, а также наличие в массиве упорядоченных (в прямом или обратном порядке) подпоследовательностей приводит к частым перебaлансировкам вспомогательного массива и, как следствие, — к деградации временной сложности до [math]O(n^2)[/math] в наиболее неблагоприятных случаях. На вспомогательный массив требуется [math]O(n)[/math] дополнительной памяти. За основу взята статья с хабра.В аттаче asm-/rc-/exe-файлы и курсор
Библиотечная сортировка ver.2В версии #1 толщина элементов сведена к минимуму, чтобы было видно основной и вспомогательный массив, и было понятно, КАК происходит сортировка. Версия #1 использовалась как отладочная. В версии #2 — стандартная толщина элементов в основном массиве (как в остальных сортировках), вспомогательный массив вынесен за пределы экрана (а в перспективе перенесен в динамически выделенную память). В аттаче asm-/rc-/exe-файлы и курсор