Сортировки с анимацией

Тема в разделе "WASM.X64", создана пользователем Mikl___, 24 дек 2022.

  1. Mikl___

    Mikl___ Супермодератор Команда форума

    Публикаций:
    14
    Регистрация:
    25 июн 2008
    Сообщения:
    3.466

    Сортировка вставками с линейным поиском

    [​IMG]

    Она же «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-файлы и курсор
     

    Вложения:

  2. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    413
    Я пока завис на оптимизацией свой сортировки. В общем, сделал, прикрутил к тесту, и туда же библиотечную qsort из MSVCR100.dll, и... квик оказался в 1.5-2 быстрей, вот так. Думаю проблема с кешем, не оптимально, как я уже говорил, дергано обращается, сравнений (countComp) происходит меньше, и код в целом быстрей, но на практике код более медленный, хотя по идеи должен быть быстрей. И ещё медленно работает с уже полностью отсортированным массивом.
    Надо менять сам алгоритм сортировки, и избавится от хвостовой рекурсии, как мы помним в 19-ти ферзях тоже хвостовая рекурсия была, я потом от неё избавился и скорость хорошо поднялось, в несколько раз. На практике код сортировки строк мне может понадобится для XRayExtensions для правильной смены типа гранат.
     
  3. alex_dz

    alex_dz Member

    Публикаций:
    0
    Регистрация:
    26 июл 2006
    Сообщения:
    101
    какой именно имете ввиду
    L1/2/3/иное?
     
  4. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    413
    alex_dz, на сам деле проще, это сам алгоритм очень не оптимально работает с маленькими корзинами, т.е. если там осталось 2-8 элементов, и таких корзин очень много, оверхид уже приличный, вот и проседает быстродействия. Теперь если размер корзины 8 и меньше, то запускаем банальный пузырёк, и... код стал работать быстрей, и сейчас обгоняет квик(раньше 700-900 мс(вот так с по-разному), а теперь 325-361 мс, а квик 423-462 мс. Таким макаром можно и больше комбинаций сортировок запускать, но тут только длительные тесты/эксперименты что-то скажут.
     
  5. alex_dz

    alex_dz Member

    Публикаций:
    0
    Регистрация:
    26 июл 2006
    Сообщения:
    101
    Ежели держать дата массив в кеше - скорость будет на порядки больше ежели чтение с РАМ-а
     
  6. Mikl___

    Mikl___ Супермодератор Команда форума

    Публикаций:
    14
    Регистрация:
    25 июн 2008
    Сообщения:
    3.466

    Сортировка вставками с бинарным поиском

    Она же «Insertion sort (binary search)». Относится к классу «сортировок со вставками». Сложность сортировки в лучшем (полностью отсортированный массив), в среднем и в худшем случае (массив отсортирован в обратную сторону) ― [math]O(\frac{n\cdot(n−1)}{1.97})[/math]. Место для вставки обнаруживается с помощью бинарного поиска. Наблюдается небольшое приращение скорости для среднего случая по сравнению с сортировкой простыми вставками с линейным поиском.

    В аттаче asm-/rc-/exe-файлы и курсор
     

    Вложения:

  7. Mikl___

    Mikl___ Супермодератор Команда форума

    Публикаций:
    14
    Регистрация:
    25 июн 2008
    Сообщения:
    3.466

    Сортировка парными вставками

    Она же «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-файлы и курсор
     

    Вложения:

  8. Mikl___

    Mikl___ Супермодератор Команда форума

    Публикаций:
    14
    Регистрация:
    25 июн 2008
    Сообщения:
    3.466

    Голубиная сортировка

    06.jpg
    Она же «Pigeonhole Sort», она же «Сортировка Дирихле», она же «сортировка по полочкам», она же «групповая сортировка». Относится к классу «сортировок с распределением».
    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-файлы и курсор
     

    Вложения:

  9. Mikl___

    Mikl___ Супермодератор Команда форума

    Публикаций:
    14
    Регистрация:
    25 июн 2008
    Сообщения:
    3.466

    Двухсторонняя сортировка выбором

    Она же «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-файлы и курсор
     

    Вложения:

  10. Mikl___

    Mikl___ Супермодератор Команда форума

    Публикаций:
    14
    Регистрация:
    25 июн 2008
    Сообщения:
    3.466

    Бинго-сортировка

    Она же «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-файлы и курсор.
     

    Вложения:

    • BingoSort.zip
      Размер файла:
      9,5 КБ
      Просмотров:
      6
  11. R81...

    R81... Member

    Публикаций:
    0
    Регистрация:
    1 фев 2020
    Сообщения:
    87
    https://ru.wikipedia.org/wiki/«O»_большое_и_«o»_малое
    "фраза «сложность алгоритма есть [​IMG]» означает, что с увеличением параметра [​IMG], характеризующего количество входной информации алгоритма, время работы алгоритма будет возрастать не быстрее, чем [​IMG] умноженная на некоторую константу;"
    Константа не обязана быть > 1.
     
  12. R81...

    R81... Member

    Публикаций:
    0
    Регистрация:
    1 фев 2020
    Сообщения:
    87
    Mikl___, возможно и у меня и в Вики несколько
    устаревшее представление об О-большом.
    Спасибо за поддержку форума от Супермодератора.
     
  13. R81...

    R81... Member

    Публикаций:
    0
    Регистрация:
    1 фев 2020
    Сообщения:
    87
    Так в возрасте к современным изменениям
    представлений о мире на...
    https://rosettacode.org/wiki/Rosetta_Code
    http://algolab.valemak.com/sorting
    https://habr.com/
    ("и разных прочих шведов")
    маразмастойкости не наблюдается.

    Ну да - это скорее сарказм интернета над
    старыми, более стабильными системами понятий.

    "только с целыми" - ну "Семен Семенович".
    Вот все тут х64... х64.
    Предположительно: если чуть "поколдовать" с
    преобразованием формата, то 16GB вполне достаточно для
    сортирвки 4-х байтных чисел FPU с плавающей точкой!
    С не более чем 2^32-1 повторений.

    Можно и с 4GB начинать, а если более 127 повторов или 254
    какие-то форматы выдумывать для и более 2^32-1 повторений,
    но будут ограничения на кол-во чисел с повторениями
    и т.д. и т.п. "Но принцу вредно много" писать. Хаджа Насредин.

    До начала "Вы переписываете на ассемблер алгоритмы сортировки"
    пожалуй "классификации <линейный>, <квадратный> и <кубический>
    будет достаточно".
    Прошу прощения: "Идея..., идея..., иде я нахожусь?"
    А если углубиться "(а их более 80)", при таком погружении
    наверняка возникнет.
     
  14. alex_dz

    alex_dz Member

    Публикаций:
    0
    Регистрация:
    26 июл 2006
    Сообщения:
    101
    я б добавил еще логарифмический (как основа)