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

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

  1. Mikl___

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

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

    Спагетти-сортировка ver.2

    Она же «Spaghetti sort» ― относится к классу «Параллельных сортировок». Представим массив неотсортиронных чисел в виде пучка из сухих спагетти соответствующей длины. Установим спагетти вертикально на ровной поверхности. Сверху на спагетти опускается пресс, пока не встретится с самой длинной макарониной. Удаляем эту спагеттину и вставляем ее в конец (изначально пустого) массива отсортированных спагетти. Каждый раз, когда пресс касается очередной макаронины, фиксируем очередной отсортированный элемент и удаляем его из массива неотсортированных элементов. Повторяем, пока все спагетти не будут отсортированы. Худшая, средняя и лучшая сложность по времени [math]O(n)[/math]

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

    Вложения:

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

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

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

    Merge-sort with Transylvanian-saxon (German) folk dance

    Быстрая сортировка. Венгерский танец
     
    Marylin нравится это.
  3. Mikl___

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

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

    Сортировка пузырьком

    Сортировка выбором. Цыганский танец
     
    Marylin нравится это.
  4. mantissa

    mantissa Мембер Команда форума

    Публикаций:
    0
    Регистрация:
    9 сен 2022
    Сообщения:
    138
    Мой вариант:
    Объединил все алгоритмы сортировок в одну dll, как и другие вспомогательные функции для работы с массивами. Теперь новые алгоритмы сортировок можно добавлять туда, без необходимости перекомпилировать исходную программу (при условии, что туда заранее импорты будущих сортировок засунуть :) ).
    Ну и сделал программку для визуализации на свой вкус, пока выбрать конкретную сортировку нельзя (как и уменьшить задержку между перестановками, сейчас 40мс), всегда сортирует вставками, но скоро добавлю такой функционал.
    Элементы отображаю с помощью Rect, а не LineTo, но градиент подсмотрел у Mikl___
    upload_2023-4-5_20-53-35.png
    upload_2023-4-5_20-53-50.png
    https://github.com/babasuck/sortVisualisation
     

    Вложения:

    • samples.zip
      Размер файла:
      30,9 КБ
      Просмотров:
      92
    Marylin и Mikl___ нравится это.
  5. mantissa

    mantissa Мембер Команда форума

    Публикаций:
    0
    Регистрация:
    9 сен 2022
    Сообщения:
    138
    Внес некие изменения:
    1) Избавился от мерцания формы при сортировке - за счет добавления технологии двойной буферизации. Теперь за отрисовку графики отвечает отдельный поток, который в бесконечном цикле 60 раз в секунду перерисовывает форму с двойным буфером (через CreateCompatibleDC и CreateCompatibleBitmap, а потом копирование во внешний контекст устройства), подсмотрел у Mikl___ и доработал
    2) Избавился от утечек памяти (Не удалял кисточки в двух местах, в итоге программа через 3 минуты работы ложилась :) )
    3) Т.к. теперь форма обновляется отдельным потоком нет смысла запрашивать перерисовку через InvalidateRect, убрал из dll эту функцию в сортировках, теперь она полностью независима от головной программы.
    https://github.com/babasuck/sortVisualisation
     

    Вложения:

    • sortVisual.zip
      Размер файла:
      31,5 КБ
      Просмотров:
      114
    Mikl___ нравится это.
  6. mantissa

    mantissa Мембер Команда форума

    Публикаций:
    0
    Регистрация:
    9 сен 2022
    Сообщения:
    138
    Доделал до конца, убрал границу у элементов, теперь создается красивый градиент после сортировки, добавил еще алгоритмов, по прежнему реализуются в alglib.dll
    Функционал программы:
    1) Визуализация сортировки - ЛКМ
    2) Перемешивание массива - ПКМ
    3) Выбор алгоритма сортировки - стрелки вправо и влево
    Алгоритмы: bubble, shaker, insertion, selection, quick, merge
    upload_2023-5-11_16-58-26.png
    upload_2023-5-11_16-58-42.png
     

    Вложения:

    • samples.zip
      Размер файла:
      13,4 КБ
      Просмотров:
      136
    Mikl___ и alex_dz нравится это.
  7. mantissa

    mantissa Мембер Команда форума

    Публикаций:
    0
    Регистрация:
    9 сен 2022
    Сообщения:
    138
    Была ошибка со стеком, исправил. Теперь selection и insertion работает.
    (Не заметил ошибки, потому что на моем компьютере работало, а на другом нет :mda:)
     

    Вложения:

    • samples.zip
      Размер файла:
      13,4 КБ
      Просмотров:
      94
    Mikl___ и Marylin нравится это.
  8. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    559
    Кстати функцию градиента цвета лучше сделать в виде макроса.
    Код (ASM):
    1. ColorGradientMC MACRO len:req
    2. LOCAL bRed,bBlue,bGreen,res
    3. ;-----red------------------------------------
    4.     IF (len LT 128) ;<      ;0..127
    5.         bRed = 255-2*len
    6.     ELSEIF (len LT 224)     ;128..223
    7.         bRed = 0
    8.     ELSEIF (len LT 342)     ;224..341
    9.         bRed = len - 224
    10.     ELSEIF (len LT 374)     ;342..373
    11.         bRed = 114
    12.     ELSEIF (len LT 470)     ;374..469
    13.         bRed = 114+(len-374)
    14.     ELSE                    ;470..511
    15.         bRed = 207+(len-470)
    16.     ENDIF
    17. ;----blue-------------------------------------
    18.     IF (len LT 64)          ;0..63
    19.         bBlue = 0
    20.     ELSEIF (len LT 128)     ;64..127
    21.         bBlue = 2*(len-64)
    22.     ELSEIF (len LT 160)     ;128..159
    23.         bBlue = 128+(len-128)
    24.     ELSEIF (len LT 192)     ;160..191
    25.         bBlue = 159+(len-160)
    26.     ELSEIF (len LT 224)     ;192..223
    27.         bBlue = 190+(len-192)
    28.     ELSEIF (len LT 256)     ;224..255
    29.         ;;sub       len, 224
    30.         bBlue = 221
    31.     ELSEIF (len LT 288)     ;256..287
    32.         bBlue = 221-(len-256)
    33.     ELSEIF (len LT 310)     ;288..309
    34.         bBlue = 190-(len-288)
    35.     ELSEIF (len LT 342)     ;310..341
    36.         bBlue = 169-(len-310)
    37.     ELSEIF (len LT 374)     ;342..373
    38.         bBlue = 138-(len-342)
    39.     ELSEIF (len LT 406)     ;374..405
    40.         bBlue = 107-(len-374)
    41.     ELSEIF (len LT 438)     ;406..437
    42.         bBlue = 76-(len-406)
    43.     ELSEIF (len LT 470)     ;438..469
    44.         bBlue = 45-(len-438)
    45.     ELSE                    ;470..511
    46.         bBlue = (14-(len AND 0FFh)) AND 0FFh
    47.     ENDIF
    48. ;---green---------------------------------
    49.     IF (len LT 64)          ;0..63
    50.         bGreen = 128+2*len
    51.     ELSEIF (len LT 96)      ;64..95
    52.         bGreen = 255
    53.     ELSEIF (len LT 128)     ;96..127
    54.         bGreen = 255-2*(len-96)
    55.     ELSEIF (len LT 310)     ;128..309
    56.         bGreen = 192-(len-128)
    57.     ELSE                    ;310..511
    58.         bGreen = 0
    59.     ENDIF
    60.     res = bRed + (bGreen SHL 8) + (bBlue SHL 16)
    61.     EXITM <res>
    62. ENDM
    И ещё один макрос для инициализации таблицы.
    Код (ASM):
    1. InitTable MACRO name_tbl:req, count:req
    2. LOCAL i
    3.     i = 0
    4.     name_tbl    dword ColorGradientMC(i)
    5.     WHILE (i LT count)
    6.         dword ColorGradientMC(i)
    7.         i = i + 1
    8.     ENDM
    9. ENDM
    И ещё в секции данных: InitTable tblColorGradient, 512
    Так проще менять градиент, или если переводить код на С/С++.
     
  9. Mikl___

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

    Публикаций:
    14
    Регистрация:
    25 июн 2008
    Сообщения:
    3.706
    Intro,
    это всё бантики и рюшечки, Вы бы лучше еще какую-нибудь сортировку забабахали для коллекции :friends:
     
  10. alex_dz

    alex_dz Active Member

    Публикаций:
    0
    Регистрация:
    26 июл 2006
    Сообщения:
    315
    Каких еще нету? :)

    upload_2023-9-9_20-34-40.png
     
  11. Mikl___

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

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

    mantissa Мембер Команда форума

    Публикаций:
    0
    Регистрация:
    9 сен 2022
    Сообщения:
    138
     
    Mikl___ нравится это.
  13. rmn

    rmn Well-Known Member

    Публикаций:
    0
    Регистрация:
    23 ноя 2004
    Сообщения:
    2.327
    Что-то они слишком короткую анимацию для богосорта сделали. Надо было часов на 10 :)
     
    Mikl___ нравится это.