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

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

  1. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    561
    alex_dz, оптимизация. Чтобы не нагружала проц в момент паузы, там цикл гоняется, если в режиме паузы. Да там же по коментам понятно.
     
  2. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    561
    Я думал что пузырёк самый медленный из реальных сортировок(Bogo не в счёт), но оказалось ещё более медленная, это Stooge sort, зависимость почти кубическая, аж [math]O(n^{2.7095})[/math]. Это медленно, я добавил этот алгоритм, и мне пришлось задержку давать в части обмена, иначе очень медленно работает, устанете ждать.
     

    Вложения:

  3. Mikl___

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

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

    Дурацкая сортировка

    «Дурацкая сортировка», она же «stupid sort» относится к классу «сортировок обменом». Сложность сортировки в лучшем, среднем и худшем случае [math]O(n^{3})[/math] (постоянство признак мастерства [​IMG]). Просматривается массив, начиная с первого элемента, по пути сравниваются соседние элементы. Если находят неотсортированную пару элементы меняются местами, происходит возврат в начало массива и всё повторяется. Процесс заканчивается, если добрались до последнего элемента массива.

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

    Вложения:

    • StupidSort.zip
      Размер файла:
      8,9 КБ
      Просмотров:
      83
  4. Mikl___

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

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

    Придурковатая сортировка

    Sorting_stoogesort_anim.gif
    Она же «сортировка по частям», она же «блуждающая сортировка» ― относится к классу «сортировок обменом». Сложность сортировки в лучшем, среднем и худшем случае [math]O(n^{\frac{\displaystyle log_{2}(3)}{\displaystyle log_{2}(1,5)}})\approx O(n^{2,70951})[/math]. Сортировка названа в честь американской комик-группы «Three stooges» («Три придурка»). Коллектив трио периодически менялся. В алгоритм заложен элемент абсурда ― обычно массив давно отсортирован, но сортировка продолжает безумно метаться по третям массива.
    • Сравнивают элементы в начале и конце подмассива (первоначально это весь массив).
    • Если значение элемента в начале массива больше чем у элемента в конце массива, тогда элементы меняют местами.
    • Рекурсивно применяют сортировку для первых 2/3 элементов массива.
    • Рекурсивно применяют сортировку для последних 2/3 элементов массива.
    • Снова рекурсивно применяют сортировку для первых 2/3 элементов массива
    В аттаче asm-/rc-/exe-файлы и курсор
     

    Вложения:

    • StoogeSort.zip
      Размер файла:
      9,2 КБ
      Просмотров:
      71
  5. asmlamo

    asmlamo Well-Known Member

    Публикаций:
    0
    Регистрация:
    18 май 2004
    Сообщения:
    1.729
    горшочек не вари :)
    Это какое то сортировочное безумие !
     
    Последнее редактирование: 5 янв 2023
    Mikl___ нравится это.
  6. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    561
    Вот ещё добавил три штуки. Интересная сортировка CountingSort, очень быстрая(быстрей квика), зависимость равна O(n), но есть ограничения, надо знать диапазон чисел, работает только с целыми, и диапазон должен быть не очень большой, но в некоторых случаях это что нужно, например сортировка номеров, там диапазон ограничен.
    И ещё CycleSort, там количество записей равно O(n), что используется если у нас флэшпамять.
    ЗЫ
    Ах да, антивири ругаются, аж 9 штук, но потом один передумал.
    --- Сообщение объединено, 5 янв 2023 ---
    Mikl___, что-то мерцает форма! Может лучше моим методом отрисовывать?, у меня ничего не мерцает.
    --- Сообщение объединено, 5 янв 2023 ---
    На ноутбуке тоже мерцает, монитор 60 Гц. Может на более высокочастотных не мерцает?
     

    Вложения:

    Последнее редактирование: 5 янв 2023
    alex_dz и Mikl___ нравится это.
  7. alex_dz

    alex_dz Active Member

    Публикаций:
    0
    Регистрация:
    26 июл 2006
    Сообщения:
    335
    на какой скорости мерцает?
     
  8. Mikl___

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

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

    Сортировка подсчетом

    CountingSort.gif
    Она же «Counting sort» ― относится к классу «сортировок подсчетом». Вычисляется значения максимального [math]max[/math] элемента массива. Выделяется вспомогательный массив [math]count[0...k][/math], заполненный нулями, где [math]k=max.[/math] Подсчитывается сколько раз в сортируемом массиве [math]A[/math] встречается каждое значение и для каждого [math]A[i][/math] увеличивается [math]count[A[i]][/math] на единицу. Проходят по массиву [math]count[/math], [math]j\in\{0,...,k\}[/math] в массив [math]A[/math] последовательно записывают число [math]j[/math] столько раз, сколько указано в ячейке [math]count[j].[/math] Сложность сортировки в лучшем случае [math]O(n)[/math], в среднем и худшем случае [math]O(n+k)[/math]

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

    Вложения:

  9. Mikl___

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

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

    Цикличная сортировка
    или семь раз отмерь (cmp) ― один отрежь (swap)

    CycleSort.gif
    Она же «Cycle sort» ― относится к классу «сортировок выбором». Сложность сортировки в лучшем, среднем и худшем случае [math]O(n^{2})[/math]
    Выбирается очередной элемент. Для него отыскивается подходящее место в массиве. Элемент помещается в найденное место, а элемент, который занимал нужное место, извлекается и новое расположение ищется теперь для него... Продолжаем, пока на найдем элемент, который нужно положить на место того, с которого начали. Круг замкнулся.
    Циклы повторяются для каждого элемента массива слева направо.
    На i-й итерации все элементы левее i-го уже стоят на своих местах. Анализировать нужно только тех, кто правее i-й позиции.
    Чтобы определить правильное место, элемента, достаточно посчитать, сколько элементов меньше него (на сколько позиций правее он должен быть).
    Большое количество сравнений обычно делает этот алгоритм не слишком эффективным. Его область применения ― задачи в которых велика «стоимость» записи в массив. Цикличная сортировка ценна тем, что изменения среди элементов массива происходят только в случаях, когда элемент ставится на своё место. Это важно, если перезапись в массиве обходится слишком «дорого» и актуальны минимальные изменения в физической памяти. Количество перестановок в этом алгоритме минимально.

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

    Вложения:

    • CycleSort.zip
      Размер файла:
      9,3 КБ
      Просмотров:
      59
  10. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    561
    Пытался вот этот код использовать, отладил на UASM.
    Код (ASM):
    1.  
    2. node_t struct ;(sizeof=12, align=4)
    3.     item            sdword ?        ;int
    4.     prev            dword ?         ;*node_t
    5.     next            dword ?         ;*node_t
    6. node_t ends
    7. sizeof@node_t       = sizeof(node_t)
    8. align_proc
    9. list_initialize proc list:ptr node_t
    10.     ASSUME  edx:ptr node_t, ebx:ptr node_t, edi:ptr node_t
    11.     mov     edx, list
    12.     mov     [edx].prev, edx
    13.     mov     [edx].next, edx
    14.     ret
    15. list_initialize endp
    16. align_proc
    17. list_destroy proc uses esi edi ebx list:ptr node_t
    18.     mov     ebx, list
    19.     mov     edi, [ebx].next ;n
    20.     .while (edi != ebx)
    21.         mov     esi, [edi].next ;tmp
    22.         hfree(edi)
    23.         mov     edi, esi
    24.     .endw
    25.     ASSUME  edx:nothing
    26.     ret
    27. list_destroy endp
    28. align_proc
    29. list_append_node proc list:ptr node_t, node:ptr node_t
    30.     ASSUME  eax:ptr node_t, edx:ptr node_t, ecx:ptr node_t
    31.     mov     edx, list
    32.     mov     ecx, node
    33.     mov     eax, [edx].prev ;prev
    34.     mov     [eax].next, ecx
    35.     mov     [edx].prev, ecx
    36.     mov     [ecx].prev, eax
    37.     mov     [ecx].next, edx
    38.     ASSUME  eax:nothing
    39.     ret
    40. list_append_node endp
    41. align_proc
    42. list_append_item proc list:ptr node_t, item:sdword
    43.     mov     ecx, halloc(sizeof@node_t)  ;node
    44.     mrm     [ecx].item, item
    45.     list_append_node(list, ecx)
    46.     ret
    47. list_append_item endp
    48. align_proc
    49. list_print proc uses esi edi list:ptr node_t
    50.     mov     edi, list
    51.     printf("[")
    52.     mov     esi, [edi].next ;n
    53.     .if (esi != edi)
    54.         printf("%d", [esi].item)
    55.         mov     esi, [esi].next
    56.     .endif
    57.     .for (: esi != edi: esi = [esi].next)
    58.         printf(", %d", [esi].item)
    59.     .endfor
    60.     printf("]\n")
    61.     ret
    62. list_print endp
    63. align_proc
    64. tree_insert proc uses ebx p:ptr ptr node_t, n:ptr node_t
    65.     ASSUME  edx:ptr dword, ecx:ptr node_t
    66.     mov     edx, p
    67.     mov     ecx, n
    68.     .while ([edx] != NULL)
    69.         mov     ebx, [edx]
    70.         mov     eax, [ebx].item
    71.         .if ([ecx].item < eax)
    72.             lea     edx, [ebx].prev
    73.         .else
    74.             lea     edx, [ebx].next
    75.         .endif
    76.     .endw
    77.     mov     [edx], ecx
    78.     ret
    79. tree_insert endp
    80. align_proc
    81. tree_to_list proc uses esi edi ebx list:ptr node_t, node:ptr node_t
    82.     ASSUME  edi:ptr node_t, esi:ptr node_t
    83.     mov     ebx, list
    84.     mov     edi, node
    85.     .if (edi)
    86.         mov     esi, [edi].next ;next
    87.         tree_to_list(ebx, [edi].prev)
    88.         list_append_node(ebx, edi)
    89.         tree_to_list(ebx, esi)
    90.     .endif
    91.     ret
    92. tree_to_list endp
    93. align_proc
    94. tree_sort proc uses esi edi ebx list:ptr node_t
    95. local root:ptr node_t
    96.     mov     esi, list
    97.     mov     edi, [esi].next ;n
    98.     .if (edi != esi)
    99.         and     root, NULL
    100.         .while (edi != esi)
    101.             mov     ebx, [edi].next ;next
    102.             xor     eax, eax
    103.             mov     [edi].next, eax
    104.             mov     [edi].prev, eax
    105.             tree_insert(&root, edi)
    106.             mov     edi, ebx
    107.         .endw
    108.         list_initialize(esi)
    109.         tree_to_list(esi, root)
    110.     .endif
    111.     ASSUME  edi:nothing, esi:nothing, ecx:nothing, ebx:nothing
    112.     ret
    113. tree_sort endp
    114. align_proc
    115. TreeSort proc  dummy:dword
    116. local list:node_t
    117.     mov     g_bActiveProcces, true
    118.     ASSUME  esi:ptr node_t
    119.     list_initialize(&list)
    120.     tree_sort(&list)
    121.     list_destroy(&list)
    122.     ASSUME  esi:nothing
    123.     xor     eax, eax
    124.     mov     g_bActiveProcces, al ;=false
    125.     mov     g_bPause, al  ;=false
    126.     ret
    127. TreeSort endp
    128.  
    Код работает, но как его в демку засунуть, хрен его знает?!?!?!?!
    ЗЫ
    А антивири таки дорабатывают, ну дежурные программисты таки водку на рабочем месте не жрут, а работают. В общем сейчас только 5 антивиря детектят вредоноса, всего-то надо ида-про открыть фыйл и быстро убедится в безопасности файла.
     
    Последнее редактирование: 6 янв 2023
  11. Mikl___

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

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

    Гравитационная сортировка

    GravitySort.gif
    Она же «сортировка бусинами», она же «сортировка абаком», она же «Bead Sort» ― относится к классу «сортировок распределением». Операции сравнения используются при поиске максимального элемента, чтобы потом выделить дополнительную память [math]max\times n[/math], где [math]n[/math] — количество элементов в массиве. Сложность по времени:
    • [math]O(\sqrt {n})[/math], где [math]n[/math] — количество рядов — В реалистичной симуляции гравитации время, затрачиваемое на расчет падения бусин, прямо пропорционально квадратному корню из количества рядов.
    • [math]O(n)[/math] — Бусины просчитываются по одному ряду за раз.
    • [math]O(S)[/math], где [math]S[/math] — сумма всех чисел в изначальном массиве — Каждая бусина просчитывается индивидуально.
    В аттаче asm-/rc-/exe-файлы и курсор
     

    Вложения:

    • GravitySort.zip
      Размер файла:
      9,1 КБ
      Просмотров:
      73
  12. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    561
    Ещё добавил сортировок. TreeSort не получилось анимацию, но видно что это быстрая сортировка, хотя я думал как пузырёк, но зависимость [math]O(log_{2}(n))[/math] и сам код простой. Добавил просто для примера.
    ЗЫ
    Ещё переделал отрисовку, теперь рисуется непосредственно на основную форму, это быстрей (совсем нет мерцаний) и меньше памяти требует.
    --- Сообщение объединено, 9 янв 2023 ---
    Нашёл ультрамедленную сортировку! Выдала аж 19 млн сравнений, при 150 чисел, хотя перемещений столько, сколько в пузырьке.
    https://ru.wikipedia.org/wiki/Медленная_сортировка
    Дурацкая по ходу быстрей, потом код выложу.
     

    Вложения:

    Mikl___ нравится это.
  13. Mikl___

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

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

    Сортировка деревом

    Она же «сортировка с помощью бинарного дерева», она же «tree sort» — относится к классу «сортировок вставками». Алгоритм сортировки, заключающийся в построении двоичного дерева поиска. Первый элемент — корень дерева, остальные добавляются по следующему принципу — начиная с корня дерева, элемент сравнивается с узлами, если элемент меньше чем узел — тогда спускаемся по левой ветке, если не меньше — тогда по правой. Спустившись до конца, элемент сам становится узлом. Построенное таким образом дерево можно легко обойти так, чтобы двигаться от узлов с меньшими значениями к узлам с большими значениями. При этом получаем все элементы в возрастающем порядке. Сортировка является оптимальной при получении данных путем непосредственного чтения из потока (файла, сокета или консоли).
    Процедура добавления [math]n[/math] объектов в бинарное дерево имеет среднюю алгоритмическую сложность порядка [math]O(n\cdot log_{2}(n))[/math], что относит сортировку к группе «быстрых сортировок». Cложность добавления одного объекта в разбалансированное дерево может достигать [math]O(n)[/math], что для [math]n[/math] элементов приведет к общей сложности порядка [math]O(n^{2})[/math]. Сложность сортировки в лучшем и среднем случае [math]O(n\cdot log_{2}(n))[/math], в худшем случае [math]O(n^{2})[/math]. Сложность сортировки по памяти [math]O(4\cdot n)[/math] — при развертывании древовидной структуры в памяти требуется не менее чем [math]4n[/math] ячеек дополнительной памяти (каждый узел должен содержать ссылки на элемент исходного массива, на родительский элемент, на левый и правый лист), существуют способы уменьшить требуемую дополнительную память.

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

    Вложения:

    • TreeSort.zip
      Размер файла:
      10,1 КБ
      Просмотров:
      68
  14. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    561
    Добавил пару сортировок крайне медленную SlowSort и довольно быструю BitonicSort, но требуется размер массива степени двойки.
    Решил так же и потестировать код, на хабре много статей, но нет тестов на ассемблере, что быстрей, ассемблер или C/C++ т.е. сортировка контейнеров со сложными типами данных и как следствия, всяким шаблонным программированием на плюсах в новых редакциях. Для меня шаблоны на плюсах дикий лес, практически не понимаю, только что-то очень просто на старых плюсах.
    По предварительным данным, вроде не самая быстрая CombSort показывает хороший результат.
     

    Вложения:

    Mikl___ нравится это.
  15. Mikl___

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

    Публикаций:
    14
    Регистрация:
    25 июн 2008
    Сообщения:
    3.708
    Intro,
    а с чем связано то, что для нормальной работы BitonicSort значение ArraySize должно быть 2N? Заменой деления на сдвиги?
     
  16. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    561
    Код взял на хабре.
    https://habr.com/ru/post/335920/
    Идея данного алгоритма заключается в том, что исходный массив преобразуется в битонную последовательность – последовательность, которая сначала возрастает, а потом убывает. Ее можно эффективно отсортировать следующим образом: разобьем массив на две части, создадим два массива, в первый добавим все элементы, равные минимуму из соответственных элементов каждой из двух частей, а во второй – равные максимуму. Утверждается, что получатся две битонные последовательности, каждую из которых можно рекурсивно отсортировать тем же образом, после чего можно склеить два массива (так как любой элемент первого меньше или равен любого элемента второго). Для того, чтобы преобразовать исходный массив в битонную последовательность, сделаем следующее: если массив состоит из двух элементов, можно просто завершиться, иначе разделим массив пополам, рекурсивно вызовем от половинок алгоритм, после чего отсортируем первую часть по порядку, вторую в обратном порядке и склеим. Очевидно, получится битонная последовательность. Асимптотика: O(nlog2n), поскольку при построении битонной последовательности мы использовали сортировку, работающую за O(nlogn), а всего уровней было logn. Также заметим, что размер массива должен быть равен степени двойки, так что, возможно, придется его дополнять фиктивными элементами (что не влияет на асимптотику).
    Такая реализация, сам до конца не понимаю. Но лучше в демке сделать 128, 256 многовато, конечно работает и другими размерами, если дополнить фиктивными элементами, но в демке это не очень выглядит.
     
  17. Mikl___

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

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

    Битонная сортировка

    Bitonic Sort.gif
    «Битонная сортировка», она же «bitonic sort» относится к классу «параллельных сортировок». Сложность сортировки в лучшем, среднем и худшем случае [math]O(n\cdot log_{2}^{2}(n))[/math] Алгоритм основан на понятии битонных последовательностей и операций над ними. Битонной последовательностью называют последовательность, которая монотонно не убывает, а затем монотонно не возрастает.
    Чтобы превратить любую битонную последовательность в отсортированную, нужно:
    1. Разделить последовательность пополам, попарно сравнить элементы [math]x_{i}[/math] и [math]x_{\frac{n}{2}+i}[/math], меняя их местами, если элемент из первой половины больше (или меньше).
    2. Рекурсивно выполнить эту сортировку над каждой из получившихся половин.
    Чтобы превратить произвольную последовательность в битонную, нужно:
    1. Разделить последовательность пополам.
    2. Первую часть превратить в битонную последовательность и отсортировать по возрастанию.
    3. Вторую часть превратить в битонную и отсортировать по убыванию.

    Реализация

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

    Временная сложность

    Сортировка рекурсивно разбивается на [math]log_{2}(n)[/math] уровней. Каждый рекурсивный вызов уменьшает размер подмассива в 2 раза, при этом количество таких подмассивов в два раза увеличивается. Сначала сравниваются [math]\frac{n}{2}[/math] пар, затем[math]\frac{n}{4}[/math] в одной половине массива и [math]\frac{n}{4}[/math] в другой, и так далее...
    [math]\frac{n}{2}+2\frac{n}{4}+4\frac{n}{8}+...=\frac{n}{2}\times log_{2}(n)[/math]
    Общее количество сравнений равно [math]\frac{n}{2}log_{2}(n)[/math]

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

    Вложения:

    • BitonicSort.zip
      Размер файла:
      9,4 КБ
      Просмотров:
      74
  18. R81...

    R81... Active Member

    Публикаций:
    0
    Регистрация:
    1 фев 2020
    Сообщения:
    141
    Но видов деревьев, подходящих для сортировки много.
    Мне больше нравится, как пример "6.3 Цифровой поиск... Бинарный случай..." Д. Кнут т.3 1978г стр. 581. Но и не обязательно бинарный. 4,8,16...
     
  19. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    561
    Вот бы как-то строковые сортировки анимировать, можно не только буквами, но цветными блоками, но надо думать.
     
  20. Mikl___

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

    Публикаций:
    14
    Регистрация:
    25 июн 2008
    Сообщения:
    3.708
    R81...,
    но я же не Дональд Кнут :) А если серьезно, названия у каких сортировок нужно поправить, какие более правильные определения должны быть? Напишите, можно в личку, я поправлю