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

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

  1. Mikl___

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

    Публикаций:
    14
    Регистрация:
    25 июн 2008
    Сообщения:
    3.708
    ― Есть три вещи, на которые можно смотреть бесконечно ―
    горящий огонь, текущая вода и сортировка вставками... :)

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

    BubbleSort.gif
    «Пузырьковая сортировка», она же «Bubble» относится к классу «сортировок обменом». Сложность сортировки [math]O(n^{2})[/math]. Упорядочивание происходит в результате обхода массива с конца в начало, по пути происходит обмен местами у неотсортированных соседних элементов. В результате первого прохода в начало массива «всплывет» минимальный элемент. Снова обходим неотсортированную часть массива (от последнего элемента ко второму) и меняем по пути неотсортированных соседей. Второй минимальный по величине элемент окажется на втором месте. Продолжаем в том же духе — обходим уменьшающуюся неотсортированную часть массива, перемещаем найденные минимумы в начало массива.
    При упорядочении массива из [math]n[/math] элементов в лучшем случае, если массив отсортирован — произойдет ([math]n[/math]-1) сравнение. В худшем случае, если массив отсортирован в обратном порядке — при сортировке произойдут [math]\frac{n\cdot(n-1)}{2}[/math] обменов.

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

    Вложения:

    • BubbleSort.zip
      Размер файла:
      6 КБ
      Просмотров:
      115
    Application, Thetrik, DrochNaNoch и 3 другим нравится это.
  2. Mikl___

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

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

    Сортировка Хоара (быстрая сортировка)

    QuickSort.gif
    «Сортировка Хоара», она же «быстрая сортировка», она же «обменная сортировка с разделением» улучшенный вариант сортировки с помощью прямого обмена относится к классу «сортировок обменом». Сперва производятся перестановки на наибольшем возможном расстоянии, после каждого прохода элементы делятся на две независимые группы.
    Общая идея:
    • Выбрать из массива «опорный элемент» (обычно [math]\frac{max+min}{2}[/math] элементов массива). От выбора опорного элемента не зависит корректность алгоритма, но в отдельных случаях сильно зависит его эффективность.
    • Сравнить все остальные элементы с опорным и переставить их в массиве так, чтобы разбить массив на два непрерывных отрезка, следующих друг за другом: «элементы меньше опорного», «равные или больше».
    • Для отрезков «меньших» и «больших» значений выполнить рекурсивно ту же последовательность операций, если длина отрезка больше единицы.
    За время сортировки происходит в среднем [math]O(n\cdot log_{2}(n))[/math] обменов.

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

    Вложения:

    • QuikSort.zip
      Размер файла:
      6,7 КБ
      Просмотров:
      115
    Thetrik, DrochNaNoch, Intro и ещё 1-му нравится это.
  3. Mikl___

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

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

    Шейкерная сортировка

    ShakerSort.gif
    Она же «сортировка перемешиванием», она же «коктейльная сортировка» относится к классу «сортировок обменом». Сложность сортировки [math]O(n^{2})[/math]. Начинается процесс как в «пузырьке» «всплыванием» элемента с минимальным значением в начало массива. После этого разворачиваемся на 180o и движемся в конец массива, при этом перемещаем в конец массива элемент с максимальным значением. Отсортировав в массиве первый и последний элементы, снова разворачиваемся. Пройдя туда-сюда-обратно несколько раз, заканчиваем процесс, оказавшись в середине массива. Шейкерная сортировка работает немного быстрее чем пузырьковая, поскольку по массиву в нужных направлениях попеременно перемещаются и максимальные и минимальные элементы. Лучше пузырьковой сортировки примерно на 20%

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

    Вложения:

    • ShakerSort.zip
      Размер файла:
      6 КБ
      Просмотров:
      108
    Thetrik, DrochNaNoch и mantissa нравится это.
  4. Mikl___

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

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

    Пирамидальная сортировка

    HeapSort.gif
    Она же «сортировка кучей» относится к классу «сортировок выбором». Алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае за [math]O(n\cdot\log_{2}(n))[/math] операций при сортировке [math]n[/math] элементов. Количество применяемой служебной памяти не зависит от размера массива (то есть [math]O(1)[/math]). Представляет собой усовершенствованную сортировку пузырьком, в которой элемент «всплывает» либо «тонет» по многим путям.
    Сортировка пирамидой использует бинарное сортирующее дерево. Сортирующее дерево — дерево, у которого выполнены условия:
    1. Каждый лист имеет глубину либо [math]d[/math], либо ([math]d[/math]-1) — максимальная глубина дерева.
    2. Значение в любой вершине не меньше значения ее потомков.
    Удобная структура данных для сортирующего дерева — массив Array, у которого Array[0] — элемент в корне, а потомки элемента Array являются Array[[math]2i[/math]+1] и Array[[math]2i[/math]+2].
    Алгоритм сортировки состоит из двух шагов:
    1. Элементы массива выстраиваются в виде сортирующего дерева:
    Array[[math]i[/math]] [math]\geqslant[/math] Array[[math]2i[/math]+1]
    Array[[math]i[/math]] [math]\geqslant[/math] Array[[math]2i[/math]+2] при [math]0\leqslant i<\frac{n}{2}[/math]
    Этот шаг требует [math]O(n)[/math] операций.
    2. Удаляются элементы из корня (по одному за раз) и перестраивается дерево. На первом шаге обмениваются элементы Array[0] и Array[[math]n[/math]-1], преобразовываются Array[0], Array[1], … , Array[[math]n[/math]-2] в сортирующее дерево. Далее переставляются Array[0] и Array[[math]n[/math]-2], преобразовываются Array[0], Array[1], … , Array[[math]n[/math]-3] в сортирующее дерево. Процесс продолжается до тех пор, пока в сортирующем дереве не останется один элемент. Тогда Array[0], Array[1], … , Array[[math]n[/math]-1] — это упорядоченная последовательность.
    Этот шаг требует [math]O(n\cdot log_{2}(n))[/math] операций.

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

    Вложения:

    • HeapSort.zip
      Размер файла:
      6,3 КБ
      Просмотров:
      96
    Thetrik, DrochNaNoch и mantissa нравится это.
  5. Mikl___

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

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

    Сортировка Шелла

    Sorting_shellsort_anim.gif
    «Сортировка Шелла», она же «сортировка с убывающим смещением» относится к классу «сортировок вставками». Усовершенствованный вариант сортировки вставками, показывает хорошую скорость работы и не требует выделения дополнительной памяти.
    Сортировки Шелла состоит из сравнения элементов последовательности, разделенных на группы и находящихся друг от друга на некотором расстоянии. Изначально это расстояние примерно равно [math]d=\frac{n}{2}[/math], где [math]n[/math] — общее число элементов сортируемого массива. На первом шаге каждая группа включает в себя два элемента, расположенных друг от друга на расстоянии [math]\frac{n}{2}[/math]. Они сравниваются между собой, и, в зависимости от направления сортировки, меняются местами. Это позволяет на начальном этапе маленькие значения поместить ближе к началу массива, большие — ближе к концу. Затем уменьшая разрыв, мы наводим в массиве «локальные порядки». На последующих шагах происходим проверку и обмен, расстояние [math]d[/math] сокращается на [math]\frac{d}{2}[/math], количество групп уменьшается. Постепенно расстояние между сравниваемыми элементами уменьшается, при [math]d=1[/math] проход по массиву происходит в последний раз.
    Среднее время работы алгоритма зависит от длин промежутков, на которых будут находится сортируемые элементы исходного списка на каждом шаге алгоритма.
    • последовательности вида [math]2^{j}[/math]: 32768=215, 16384=214, 8192=213, 4096=212, 2048=211, 1024=210, 512=29, 256=28, 128=27, 64=26, 32=25, 16=24, 8=23, 4=22, 2=21, 1=20 неплохой выбор, особенно, когда количество элементов степень двойки
    • Последовательность Шелла [math]\frac{n}{2^{j}}[/math], приводит к алгоритму класса [math]O(n^{2})[/math]. При [math]n=1000[/math]: 500, 250, 125, 62, 31, 15, 7, 3, 1
    • последовательности Кнутта [math]\frac{3^{j}−1}{2}[/math], приводит к алгоритму класса [math]O(\sqrt{n^{3}})[/math]: 797161, 265720, 88573, 29524, 9841, 3280, 1093, 364, 121, 40, 13, 4, 1
    • последовательность Хиббарда [math]2^{ j}-1[/math], приводит к алгоритму класса [math]O(\sqrt{n^{3}})[/math]: 32767, 16383, 8191, 4095, 2047, 1023, 511, 255, 127, 63, 31, 15, 7, 3, 1
    • последовательность Инсерпи и Седжвика
      • [math](9\cdot(2^{j}-\sqrt{2^{j}})+1)[/math] если [math]j[/math] четное
      • [math](2^{j+3}-3\cdot \sqrt{2^{j+3}}+1)[/math] если [math]j[/math] нечетное
      198768, 86961, 33936, 13776, 4592, 1968, 861, 336, 112, 48, 21, 7, 3, 1 При использовании таких приращений средняя сложность алгоритма составляет: [math]O(\sqrt[6]{n^{7}})[/math], в худшем случае порядка [math]O(\sqrt[3]{n^{4}})[/math]
    • последовательность Пратта [math]2^{i}\cdot 3^{j}[/math], приводит к алгоритму класса [math]O(n\cdot log^{2}_{2}(n))[/math]: 486, 432, 384, 324, 288, 256, 243, 216, 192, 162, 144, 128, 108, 96, 81, 72, 64, 54, 48, 36, 32, 27, 24, 18, 16, 12, 9, 8, 6, 4, 3, 2, 1
    • последовательность [math]3^{j}−1[/math], приводит к алгоритму класса [math]O(\sqrt{n^{3}})[/math]: 531440, 177146, 59048, 19682, 6560, 2186, 728, 242, 80, 26, 8, 2, 1
    • эмпирическая последовательность Марцина Циура: 1750, 701, 301, 132, 57, 23, 10, 4, 1
    В аттаче asm-/rc-/exe-файлы и курсор
     

    Вложения:

    • ShellSort.zip
      Размер файла:
      6,4 КБ
      Просмотров:
      108
    Thetrik, DrochNaNoch и mantissa нравится это.
  6. Mikl___

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

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

    Сортировка выбором

    SelectionSort.gif
    Относится к классу «сортировок выбором». Сортировка выбором может быть как устойчивой, так и неустойчивой. На массиве из [math]n[/math] элементов сложность выполнения в среднем случае [math]O(\frac{n\cdot(n-1)}{1.94})[/math], предполагается, что сравнения делаются за постоянное время. После каждого прохода по внутреннему циклу делается только один обмен, поэтому общее число обменов =[math]n[/math]-1, что в [math]\frac{n}{2}[/math] раз меньше, чем в сортировке пузырьком. Число проходов по внутреннему циклу равно ([math]n[/math]-1) в случае сортировки частично или полностью отсортированного массива.
    Наихудший случай:
    • Число сравнений в теле цикла равно [math]\frac{(n-1)\cdot n}{2}[/math].
    • Число сравнений в заголовках циклов [math]\frac{(n-1)\cdot n}{2}[/math].
    • Число сравнений перед операцией обмена [math]n[/math]-1.
    • Суммарное число сравнений [math]n^{2}[/math]−1.
    • Число обменов [math]n[/math]-1.
    Пирамидальная сортировка сильно улучшает базовый алгоритм, используя структуру данных «куча» для ускорения нахождения и удаления минимального элемента.
    Существует двунаправленный вариант сортировки методом выбора, в котором на каждом проходе отыскиваются и устанавливаются на свои места и минимальное, и максимальное значения.

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

    Вложения:

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

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

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

    Гномья сортировка

    Sorting_gnomesort_anim.gif
    «Гномья сортировка» относится к классу «сортировок обменом». Сложность сортировки [math]O(n^{2})[/math]. Просматриваем массив от первого элемента к последнему по пути сравниваем соседние элементы. Если встретили пару неотсортированных элементов меняем их местами и возвращаемся в начало массива. Снова проходим и проверяем массив, если встретили «неправильную» пару соседних элементов, тогда меняем их местами и опять начинаем всё сначала. Продолжаем до тех пор пока массив не отсортируется.
    Сортировку можно улучшить. Обменяв два элемента, изменяем порядок в массиве, и нужно как-то выяснить не вступает ли новое расположение в диссонанс с теми элементами, которые были проверены ранее. Не перемещаемся в начало массива, не двигаемся к концу массива, а делаем шаг назад. Если там также не отсортированная пара, то устанавливаем очередность по старшинству и сделаем ещё один шаг к началу массива. будем двигаться к началу массива до тех пор, пока не достигнем отсортированной части массива. После этого двигаемся к концу массива.
    Если зафиксировать место, в котором встретилась неотсортированная пара элементов, и сделать несколько корректирующих итераций назад, тогда после наведения порядка после перемещения к началу массива, можно переместится туда, где перемещение к концу массива прервалось и следовать по массиву дальше.

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

    Вложения:

    • GnomeSort.zip
      Размер файла:
      6 КБ
      Просмотров:
      102
    Thetrik, DrochNaNoch и mantissa нравится это.
  8. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    561
    В HeapSort есть ошибка, один элемент почему-то не от сортировался. Правда было один раз, наверное ошибка в коде, а может и в алгоритме, надо посмотреть края, т.е. пограничные значения.
    Я тут некоторое время помучился с эмулятором МК-61, взял и написал.
    Код (ASM):
    1.  
    2. lea ecx, [ebx+40];I_40
    3. .if (ecx>42)
    4.     sub ecx, 42
    5. .endif
    6.  
    А надо было.
    Код (ASM):
    1.  
    2. lea ecx, [ebx+40];I_40
    3. .if (ecx>=42)
    4.     sub ecx, 42
    5. .endif
    6.  
    Не сразу заметил.
     
    Mikl___ нравится это.
  9. Mikl___

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

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

    Сортировка расческой

    1_-XhyyRlu6FLAz7nq0tlYcw.gif
    Сортировка расческой, она же сортировка гребнем относится к классу «сортировок обменом». Главный недостаток пузырьковой сортировки — полный перебор всех элементов массива. Скорость работы алгоритма зависит не от количества сравнений, а от количества перестановок.
    Если в начале массива много больших элементов, которые нужно отправить в конец массива, тогда каждый раз их придется менять их местами с соседями, по одной перестановке за раз. Можно представить, что мы несем куда-то не слишком тяжелый груз, но после каждого шага ставим этот груз на пол, потом поднимаем, делаем шаг, снова ставим, снова поднимаем. Процедуры простые, но из-за устройства алгоритма мы делаем эти процедуры слишком много раз.
    Если большие элементы тормозят весь процесс, тогда их нужно перекидывать не на соседнее место, а подальше. Так уменьшается количество перестановок, а с ними экономится и процессорное время, для их обработки.
    Отправлять каждый большой элемент сразу в конец массива недальновидно — мы же не знаем, насколько этот элемент большой по сравнению с остальными элементами. Поэтому в сортировке расческой сравниваются элементы, которые отстоят друг от друга на каком-то расстоянии. Оно не слишком большое, чтобы сильно не откидывать элементы и возвращать потом большинство назад, но и не слишком маленькое, чтобы можно было отправлять не на соседнее место, а чуть дальше. Опытным путем было установлено оптимальное расстояние между элементами равное количеству элементов массива, деленному на 1,247 (получившееся в результате число округляется до целого). С этим числом алгоритм работает быстрее всего. Оптимальное значение фактора уменьшения [math]1,247...=\frac{1}{1-e^{-\phi }}[/math], где [math]e=2,7182818285…[/math] — основание натурального логарифма, а [math]\phi=1,618033988…[/math] — золотое сечение.
    На первом шаге количество элементов массива (у меня 137) делят на 1,247. После округления получаем число 110. Проходим первый цикл пузырьковой сортировки, сравнивая 1 и 111, 2 и 112, 3 и 113 и так далее. Это отправит элементы с самым большим значением, если они есть в начале массива, в самый его конец. Всего на первом шаге будет (137-110=27) сравнений и примерно (27/2) перемещений.
    На втором шаге число 110 из предыдущего этапа делим на 1,247, получаем число 88. Снова проходим весь массив и сравниваем: 1 и 88, 2 и 89, 3 и 90, и т.д. Получилось (137-88=49) перестановок и снова элементы с наибольшим значением переместились к концу массива. С каждым проходом уменьшается размер шага до тех пор, пока он не станет меньше единицы — к этому моменту массив будет полностью отсортирован.
    Сортировка расческой называется так из-за того, что массив как бы расчесывается сначала редким гребнем, потом более частым гребнем. В конце шаг равен единице, как в пузырьковой сортировке.

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

    Вложения:

    • CombSort.zip
      Размер файла:
      6 КБ
      Просмотров:
      108
    Thetrik, Intro, DrochNaNoch и ещё 1-му нравится это.
  10. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    561
    Что-то мерцает форма, и ещё утечка происходит, приложение начинает постепенно всё больше памяти брать, и если потом сбросить и начать сортировку, форма становиться чёрной.
    В общем, надо другими методами рисовать столбики. Ах да, я переписал код на UASM и Win32 386.
     
  11. Mikl___

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

    Публикаций:
    14
    Регистрация:
    25 июн 2008
    Сообщения:
    3.708
    Intro,
    ну вы же понимаете, что пишется это всё на ходу и криво, главное успеть к Новому году. О мерцании знаю, но пока не понял как это мерцание устранить. Про утечки памяти, спасибо, посмотрю внимательнее. Буду рад любым предложениям по улучшению :friends:
     
  12. algent

    algent Member

    Публикаций:
    0
    Регистрация:
    11 апр 2018
    Сообщения:
    101
    Визуализация просто прелесть, кажется первый раз такую вижу. Часто есть желание замедлить, лучше рассмотреть.
    Но сколько же эти Хоары и Шеллы мучались прежде чем, кто-то догадался до "Counting Sort" :laugh1:.
    Хотя, если она то, что я думаю, то там всё красиво только с целыми числами в диапазоне вордов, ну или хотя бы полуторных вордов... Может дело в этом...
     
  13. Mikl___

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

    Публикаций:
    14
    Регистрация:
    25 июн 2008
    Сообщения:
    3.708
    algent,
    для замедления увеличьте задержку у Sleep.
    Самое интересное, что Хоар разработал свою сортировку в Москве в 1959, куда он был направлен на стажировку в МГУ, где под руководством А.Н.Колмогорова занимался теорией вероятностей и машинным переводом.
     
    algent нравится это.
  14. GRAFik

    GRAFik Active Member

    Публикаций:
    0
    Регистрация:
    14 мар 2020
    Сообщения:
    352
    Ура!!! Свершилось!!! Друг спас друга в тяжелой жизненной ситуации и не дал погибнуть без ресурсов. А ресурсы в наше время - это все!!! :)

    Ну а если серъезно, то появилось меню выбора запуска сортировки, появилась секция ресурсов. Все работает. Спасибо, Mikl___. Всех с Наступающим... Слава ассемблерщикам ВАСМА!!! :)
     
  15. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    561
    Ну в общем вот моя версия. Написана на UASM, линковщик polink, Win32, процессор 386. Возможно заработает на Win95/98, на 98 скорей всего точно, с процем 586, 16 МБ и видеокарта 4 МБ, чтобы поддерживала труколор и 1280х1024 или лучше выше, а не!, надо 1600х1200 для квадратных мониторов, значит надо что уже более современное или в программе уменьшить размер формы, это количество колонок или ширину колонок.
    ЗЫ
    Аж 6 антивиря агрится. :skull:
    Cybereason Malicious.b62f8f
    Cylance Unsafe
    Cynet Malicious (score: 100)
    MaxSecure Trojan.Malware.300983.susgen
    SecureAge Malicious
    Trapmine Malicious.high.ml.score
    --- Сообщение объединено, 26 дек 2022 ---
    Ну вот версия получше, исправил некоторые баги, теперь можно менять скорость.
    Код (Text):
    1.  
    2. ;;     Управление
    3. ;; Пробел: старт/стоп
    4. ;; Ентер: сброс
    5. ;; + / -: быстрей/медленей
    6.  
     

    Вложения:

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

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

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

    Четно-нечетная сортировка

    Она же «кирпичная сортировка» (Brick sort), она же «четно-нечетная сортировка с транспозицией» (Odd–even transposition sort). Относится к классу «сортировок с обменами». Сначала элементы с нечетными индексами сравниваются/обмениваются с элементами с четными индексами (1-ый со 2-ым, 3-ий с 4-ым, 5-ый с 6-ым и т.д.). Затем элементы с четными индексами сравниваются/обмениваются с соседними элементами с нечетными индексами (2-ой с 3-им, 4-ый с 5-ым, 6-ой с 7-ым и т.д.). Затем снова нечетные сравниваются с четными, потом снова четные с нечетными и т.д. Процесс завершается если в результате двух прогонов обменов не произошло ― значит массив упорядочен. В обычной сортировке «пузырьком» во время каждого прохода текущий максимум планомерно выдавливается в конец массива. Если же передвигаться по массиву по четным и нечетным индексам, то сразу все более-менее крупные элементы массива одновременно за один проход проталкиваются вправо на одну позицию.

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

    Вложения:

    • BrickSort.zip
      Размер файла:
      6,1 КБ
      Просмотров:
      94
    Thetrik нравится это.
  17. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    561
    Давным давно, когда компа у меня не было, придумал быструю сортировку строк. Код написал на бумаге, реализовать понятно, не на чем было. Потом когда появился ПК, я забыл реализовать, где-то возможно бумажки лежат, а может и выбросили.
    Суть в том, сначала подсчитываем количество букв в строках с номером N, потом быстро сортируем по буквам. Переходим к следующему N. Ну что помню, писал код давно, уже забыл подробности, а бумажку с кодом вроде выкинули. Скорей всего такой алгоритм уже придумали, главное заточен под строки, ну байты или другие символы. Всё не как не собираюсь реализовать, а времени прошло лет 20. Может и пригодится где.
     
  18. Mikl___

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

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

    Сортировка слиянием (Merge sort)

    MergeSort.gif
    1. Сортируемый массив разбивается на две части примерно одинакового размера;
    2. Каждая из получившихся частей сортируется отдельно;
      1.1. - 2.1. Рекурсивное разбиение задачи на меньшие происходит до тех пор, пока размер массива не достигнет единицы (любой массив размером=1 считается упорядоченным).
    3. Два упорядоченных массива половинного размера соединяются в один.
      3.1. Соединение двух упорядоченных массивов в один.
      ____Допустим у нас есть два отсортированных по возрастанию подмассива. Тогда:
      3.2. Слияние двух подмассивов в третий результирующий массив.
      ____На каждом шаге берем меньший из двух первых элементов подмассивов и записываем его в результирующий массив. Счетчики номеров элементов результирующего массива и подмассива, из которого был взят элемент, увеличиваем на 1.
      3.3. «Сцепление» остатков.
      ____Когда один из подмассивов закончился — добавляем все оставшиеся элементы второго подмассива в результирующий массив.
    В аттаче asm-/rc-/exe-файлы и курсор
     

    Вложения:

    • MergeSort.zip
      Размер файла:
      9,6 КБ
      Просмотров:
      97
    DrochNaNoch и Thetrik нравится это.
  19. Mikl___

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

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

    Сортировка вставками


    Сортировка вставками — сортировка, при которой элементы массива просматриваются по одному, каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных.
    В сортировке вставками последовательно обрабатываются отрезки массива, начиная с первого элемента и затем последовательно расширяя подмассив, вставляя на своё место очередной неотсортированный элемент.
    Для вставки используется буферная область памяти, в которой хранится элемент, еще не вставленный на свое место (так называемый ключевой элемент). В подмассиве, начиная с конца отрезка, перебираются элементы, которые сравниваются с ключевым. Если эти элементы больше ключевого, то они сдвигаются на одну позицию вправо, освобождая место для последующих элементов. Если в результате этого перебора попадается элемент, меньший или равный ключевому, то значит в текущую свободную ячейку можно вставить ключевой элемент.
    Вычислительная сложность — [math]O(n^{2})[/math].

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

    Вложения:

    Последнее редактирование: 23 янв 2023
    DrochNaNoch и Thetrik нравится это.
  20. Mikl___

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

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

    Немного изменений

    1. Цвет для градиентного закрашивания сперва получал программным путем
    Код (ASM):
    1. color proc
    2. local red:byte
    3. local green:byte
    4. local blue:byte
    5. mov ecx,eax
    6. mov edx,eax
    7. cmp eax,128;96;64;32
    8. jae @f       ;0 - 31
    9. mov red,255;192+64
    10. add al,al
    11. sub red,al   ; r: 255 - 127
    12. jmp a1
    13. @@: cmp eax,224;192;160 ;128 - 159
    14. jae @f
    15. and red,0    ; r =0
    16. jmp a1
    17. @@: cmp eax,342;310;288;256
    18. jae @f
    19. sub eax,224
    20. and red,0
    21. add red,al
    22. jmp a1
    23. @@: cmp eax,374
    24. jae @f
    25. sub eax,342
    26. mov red,72h
    27. jmp a1
    28. @@: cmp eax,470;438;406
    29. jae @f
    30. sub eax,374
    31. mov red,72h;91h
    32. add red,al
    33. jmp a1
    34. @@: mov red,0CFh;0EEh
    35. sub eax,470
    36. add red,al
    37. ;----blue-------------------------------------
    38. a1: and blue,0   ; b = 0
    39. cmp ecx,64;32
    40. jb a0
    41. @@:     cmp ecx,128;96   ;64 - 95
    42. jae @f
    43. sub cl,64
    44. add cl,cl
    45. add blue,cl
    46. jmp a0
    47. @@: cmp ecx,160 ;128 - 159
    48. jae @f
    49. sub cl,128
    50. mov blue,128
    51. add blue,cl ;b =  190
    52. jmp a0
    53. @@: cmp ecx,192
    54. jae @f      ;255 - 383
    55. sub ecx,160
    56. mov blue,159;192
    57. add blue,cl
    58. jmp a0
    59. @@: cmp ecx,224
    60. jae @f     ;384 - 447
    61. mov blue,190;222
    62. sub ecx,192
    63. add blue,cl
    64. jmp a0
    65. @@: cmp ecx,256
    66. jae @f
    67. sub ecx,224
    68. mov blue,221
    69. jmp a0
    70. @@: cmp ecx,288
    71. jae @f
    72. sub ecx,256
    73. mov blue,0DDh
    74. sub blue,cl
    75. jmp a0
    76. @@: cmp ecx,310
    77. jae @f
    78. mov blue,0BEh
    79. sub ecx,288
    80. sub blue,cl
    81. jmp a0
    82. @@: cmp ecx,342
    83. jae @f
    84. mov blue,0A9h
    85. sub ecx,310
    86. sub blue,cl
    87. jmp a0
    88. @@: cmp ecx,374
    89. jae @f
    90. mov blue,8Ah
    91. sub ecx,342
    92. sub blue,cl
    93. jmp a0
    94. @@: cmp ecx,406
    95. jae @f
    96. mov blue,6Bh
    97. sub ecx,374
    98. sub blue,cl
    99. jmp a0
    100. @@: cmp ecx,438
    101. jae @f
    102. mov blue,4Ch
    103. sub ecx,406
    104. sub blue,cl
    105. jmp a0
    106. @@: cmp ecx,470
    107. jae @f
    108. mov blue,2Dh
    109. sub ecx,438
    110. sub blue,cl
    111. jmp a0
    112. @@: mov blue,0Eh
    113. sub eax,470
    114. sub blue,cl
    115. ;---green---------------------------------
    116. a0: cmp edx,64;32
    117. jae @f       ;0 - 31
    118. add dl,dl
    119. mov green,128
    120. add green,dl ; g: 127 - 255
    121. jmp a2
    122. @@:     cmp edx,96   ;64 - 95
    123. jae @f
    124. mov green,255; g = 255
    125. jmp a2
    126. @@: cmp edx,128 ;96 - 127
    127. jae @f
    128. mov green,255
    129. sub dl,96
    130. add dl,dl
    131. sub green,dl; g = 255 - 192
    132. jmp a2
    133. @@: cmp edx,310;160 ;128 - 159
    134. jae @f
    135. sub dl,128
    136. mov green,192
    137. sub green,dl; g = 192
    138. jmp a2
    139. @@: and green,0
    140. a2: xor eax,eax
    141. mov al,blue
    142. shl eax,8
    143. mov al,green
    144. shl eax,8
    145. mov al,red
    146. leave
    147. ret
    148. color endp
    потом переделал в табличное преобразование
    Код (ASM):
    1. . . .
    2. mov eax,array1[rdi*4]
    3. mov r8d,color[rax*4]
    4. . . .
    5. .data
    6. color dd 0,80FFh,82FDh,84FBh,86F9h,88F7h,8AF5h,8CF3h,8EF1h,90EFh, 92EDh,94EBh,96E9h
    7. dd 98E7h,9AE5h,9CE3h,9EE1h,0A0DFh,0A2DDh,0A4DBh,0A6D9h,0A8D7h, 0AAD5h,0ACD3h
    8. dd 0AED1h,0B0CFh,0B2CDh,0B4CBh,0B6C9h,0B8C7h,0BAC5h,0BCC3h, 0BEC1h,0C0BFh,0C2BDh
    9. dd 0C4BBh,0C6B9h,0C8B7h,0CAB5h,0CCB3h,0CEB1h,0D0AFh,0D2ADh, 0D4ABh,0D6A9h,0D8A7h
    10. dd 0DAA5h,0DCA3h,0DEA1h,0E09Fh,0E29Dh,0E49Bh,0E699h,0E897h, 0EA95h,0EC93h,0EE91h
    11. dd 0F08Fh,0F28Dh,0F48Bh,0F689h,0F887h,0FA85h,0FC83h,0FE81h, 0FF7Fh,2FF7Dh,4FF7Bh
    12. dd 6FF79h,8FF77h,0AFF75h,0CFF73h,0EFF71h,10FF6Fh,12FF6Dh,14FF6Bh, 16FF69h,18FF67h
    13. dd 1AFF65h,1CFF63h,1EFF61h,20FF5Fh,22FF5Dh,24FF5Bh,26FF59h,28FF57h,2AFF55h
    14. dd 2CFF53h,2EFF51h,30FF4Fh,32FF4Dh,34FF4Bh,36FF49h,38FF47h,3AFF45h,3CFF43h
    15. dd 3EFF41h,40FF3Fh,42FD3Dh,44FB3Bh,46F939h,48F737h,4AF535h,4CF333h,4EF131h
    16. dd 50EF2Fh,52ED2Dh,54EB2Bh,56E929h,58E727h,5AE525h,5CE323h,5EE121h,60DF1Fh
    17. dd 62DD1Dh,64DB1Bh,66D919h,68D717h,6AD515h,6CD313h,6ED111h,70CF0Fh,72CD0Dh
    18. dd 74CB0Bh,76C909h,78C707h,7AC505h,7CC303h,7EC101h,80C000h,81BF00h,82BE00h
    19. dd 83BD00h,84BC00h,85BB00h,86BA00h,87B900h,88B800h,89B700h,8AB600h,8BB500h
    20. dd 8CB400h,8DB300h,8EB200h,8FB100h,90B000h,91AF00h,92AE00h,93AD00h,94AC00h
    21. dd 95AB00h,96AA00h,97A900h,98A800h,99A700h,9AA600h,9BA500h,9CA400h,9DA300h
    22. dd 9EA200h,9FA100h,9FA000h,0A09F00h,0A19E00h,0A29D00h,0A39C00h,0A49B00h
    23. dd 0A59A00h,0A69900h,0A79800h,0A89700h,0A99600h,0AA9500h,0AB9400h,0AC9300h
    24. dd 0AD9200h,0AE9100h,0AF9000h,0B08F00h,0B18E00h,0B28D00h, 0B38C00h,0B48B00h
    25. dd 0B58A00h,0B68900h,0B78800h,0B88700h,0B98600h,0BA8500h,0BB8400h,0BC8300h
    26. dd 0BD8200h,0BE8100h,0BE8000h,0BF7F00h,0C07E00h,0C17D00h,0C27C00h,0C37B00h
    27. dd 0C47A00h,0C57900h,0C67800h,0C77700h,0C87600h,0C97500h,0CA7400h,0CB7300h
    28. dd 0CC7200h,0CD7100h,0CE7000h,0CF6F00h,0D06E00h,0D16D00h, 0D26C00h,0D36B00h
    29. dd 0D46A00h,0D56900h,0D66800h,0D76700h,0D86600h,0D96500h, 0DA6400h,0DB6300h
    30. dd 0DC6200h,0DD6100h,0DD6000h,0DD5F01h,0DD5E02h,0DD5D03h, 0DD5C04h,0DD5B05h
    31. dd 0DD5A06h,0DD5907h,0DD5808h,0DD5709h,0DD560Ah,0DD550Bh,0DD540Ch,0DD530Dh
    32. dd 0DD520Eh,0DD510Fh,0DD5010h,0DD4F11h,0DD4E12h,0DD4D13h,0DD4C14h,0DD4B15h
    33. dd 0DD4A16h,0DD4917h,0DD4818h,0DD4719h,0DD461Ah,0DD451Bh,0DD441Ch,0DD431Dh
    34. dd 0DD421Eh,0DD411Fh,0DD4020h,0DC3F21h,0DB3E22h,0DA3D23h,0D93C24h,0D83B25h
    35. dd 0D73A26h,0D63927h,0D53828h,0D43729h,0D3362Ah,0D2352Bh,0D1342Ch,0D0332Dh
    36. dd 0CF322Eh,0CE312Fh,0CD3030h,0CC2F31h,0CB2E32h,0CA2D33h,0C92C34h,0C82B35h
    37. dd 0C72A36h,0C62937h,0C52838h,0C42739h,0C3263Ah,0C2253Bh,0C1243Ch,0C0233Dh
    38. dd 0BF223Eh,0BE213Fh,0BE2040h,0BD1F41h,0BC1E42h,0BB1D43h,0BA1C44h,0B91B45h
    39. dd 0B81A46h,0B71947h,0B61848h,0B51749h,0B4164Ah,0B3154Bh,0B2144Ch,0B1134Dh
    40. dd 0B0124Eh,0AF114Fh,0AE1050h,0AD0F51h,0AC0E52h,0AB0D53h,0AA0C54h,0A90B55h
    41. dd 0A90056h,0A80057h,0A70058h,0A60059h,0A5005Ah,0A4005Bh,0A3005Ch,0A2005Dh
    42. dd 0A1005Eh,0A0005Fh,9F0060h,9E0061h,9D0062h,9C0063h,9B0064h,9A0065h,990066h
    43. dd 980067h,970068h,960069h,95006Ah,94006Bh,93006Ch,92006Dh,91006Eh,90006Fh
    44. dd 8F0070h,8E0071h,8D0072h,8C0073h,8B0074h,8A0075h,8A0072h,890072h,880072h
    45. dd 870072h,860072h,850072h,840072h,830072h,820072h,810072h,800072h,7F0072h
    46. dd 7E0072h,7D0072h,7C0072h,7B0072h,7A0072h,790072h,780072h,770072h,760072h
    47. dd 750072h,740072h,730072h,720072h,710072h,700072h,6F0072h,6E0072h,6D0072h
    48. dd 6C0072h,6B0072h,6B0072h,6A0073h,690074h,680075h,670076h,660077h,650078h
    49. dd 640079h,63007Ah,62007Bh,61007Ch,60007Dh,5F007Eh,5E007Fh,5D0080h,5C0081h
    50. dd 5B0082h,5A0083h,590084h,580085h,570086h,560087h,550088h,540089h,53008Ah
    51. dd 52008Bh,51008Ch,50008Dh,4F008Eh,4E008Fh,4D0090h,4C0091h,4C0092h,4B0093h
    52. dd 4A0094h,490095h,480096h,470097h,460098h,450099h,44009Ah,43009Bh,42009Ch
    53. dd 41009Dh,40009Eh,3F009Fh,3E00A0h,3D00A1h,3C00A2h,3B00A3h,3A00A4h,3900A5h
    54. dd 3800A6h,3700A7h,3600A8h,3500A9h,3400AAh,3300ABh,3200ACh,3100ADh,3000AEh
    55. dd 2F00AFh,2E00B0h,2D00B1h,2D00B2h,2C00B3h,2B00B4h,2A00B5h,2900B6h,2800B7h
    56. dd 2700B8h,2600B9h,2500BAh,2400BBh,2300BCh,2200BDh,2100BEh,2000BFh,1F00C0h
    57. dd 1E00C1h,1D00C2h,1C00C3h,1B00C4h,1A00C5h,1900C6h,1800C7h,1700C8h,1600C9h
    58. dd 1500CAh,1400CBh,1300CCh,1200CDh,1100CEh,1000CFh,0F00D0h,0E00D1h,3800CFh
    59. dd 3700D0h,3600D1h,3500D2h,3400D3h,3300D4h,3200D5h,3100D6h,3000D7h,2F00D8h
    60. dd 2E00D9h,2D00DAh,2C00DBh,2B00DCh,2A00DDh,2900DEh,2800DFh,2700E0h,2600E1h
    61. dd 2500E2h,2400E3h,2300E4h,2200E5h,2100E6h,2000E7h,1F00E8h,1E00E9h,1D00EAh
    62. dd 1C00EBh,1B00ECh,1A00EDh,1900EEh,1800EFh,1700F0h,1600F1h,1500F2h,1400F3h
    63. dd 1300F4h,1200F5h,1100F6h,1000F7h,0F00F8h
    64.  
    2. Избавился от мерцания. При инициализации программы создаю виртуальный контекст устройства, совместимый
    Код (ASM):
    1. wmCREATE:invoke GetSystemMetrics,SM_CXSCREEN
    2.        mov maxX,rax
    3.        invoke GetSystemMetrics,SM_CYSCREEN
    4.        mov maxY,rax
    5.        invoke GetDC,hWnd
    6.        mov hDC,rax
    7.        invoke CreateCompatibleDC,eax
    8.        mov memDC,rax
    9.        invoke CreateCompatibleBitmap,hDC,maxX,maxY
    10.        invoke SelectObject,memDC,eax
    11.        invoke GetStockObject,BLACK_BRUSH
    12.        invoke SelectObject,memDC,eax
    13.        invoke PatBlt,memDC,0,0,maxX,maxY,PATCOPY
    14.        invoke SetBkMode,memDC,TRANSPARENT
    15.        invoke ReleaseDC,hWnd,hDC
    16.        jmp wmBYE
    с контекстом реального устройства. Созданный виртуальный контекст будет существовать в течение всего времени выполнения программы. Сначала через GetSystemMetrics программа получает размеры экрана, — эти значения будут затем использоваться совместимым растром. Затем через GetDC создается контекст устройства окна, а после этого при помощи функции CreateCompatibleDC — совместимый контекст устройства памяти. Полученный контекст сохраняется в переменной memDC. Затем через CreateCompatibleBitmap создается совместимый растр. Эта операция устанавливает взаимно-однозначное соответствие между растром — виртуальным окном и реальным окном на экране. Растр должен иметь размеры равные размерам экрана. Это гарантия того, что он окажется достаточно большим для восстановления всего окна независимо от размеров окна. Затем через GetStockObject программа получает дескриптор встроенной черной кисти. Кисть выбирается как текущая для контекста устройства памяти, после чего функция PatBlt заполняет черным цветом виртуальное окно. Контекст устройства физического окна hDC через ReleaseDC освобождается; контекст устройства памяти memDC продолжает существовать до завершения программы. После создания виртуального окна весь вывод направляется в него.
    Код (ASM):
    1. wmUSER_1:invoke PatBlt,memDC,0,0,maxX,maxY,PATCOPY
    2.       lea edx,rect
    3.       invoke GetClientRect,hWnd
    4.       invoke SetTextColor,memDC,0FFFFFFh
    5.       invoke SetBkColor,memDC,0
    6.       cmp count,0
    7.       je @f
    8.       mov eax,(n*n-n)/4
    9.       cvtsi2sd xmm0,eax
    10.       cvtsi2sd xmm1,count
    11.       divsd xmm0,xmm1
    12.       movq m,xmm0
    13.       mov rax,m
    14.       mov r9d,count
    15.       mov edx,offset fmt
    16.       lea ecx,buffer
    17.       invoke sprintf,,,n,,rax
    18.       lea r9d,buffer
    19.       invoke TextOut,memDC,0,0,,rax
    20. @@:   xor edi,edi
    21.       mov esi,14
    22. @@:   mov eax,array1[rdi*4]
    23.       mov r8d,color[rax*4]
    24.       invoke CreatePen,PS_SOLID,9
    25.       invoke SelectObject,memDC,eax
    26.       mov hPen,rax
    27.       invoke MoveToEx,memDC,esi,rect.bottom,0
    28.       mov r8d,rect.bottom
    29.       sub r8d,array1[rdi*4]
    30.       invoke LineTo,memDC,esi
    31.       invoke DeleteObject,hPen
    32.       add esi,10
    33.       inc edi
    34.       cmp edi,n
    35.       jb @b
    36.       invoke InvalidateRect,hWnd,0,1
    37.       jmp wmBYE
    Вывод в физическое окно осуществляется только в одном месте программы при обработке сообщения WM_PAINT. Весь вывод направляется на устройство, соответствующее контексту memDC, после чего вызывается функция InvalidateRect для перерисовки реального окна. При получении сообщения WM_PAINT содержимое виртуального окна копируется в реальное окно. Для копирования изображения из memDC в hDC используется BitBlt. Параметр
    Код (ASM):
    1. wmPAINT:lea edx,ps
    2.        invoke BeginPaint,hWnd
    3.        invoke BitBlt,eax,0,0,maxX,maxY,memDC,0,0,SRCCOPY
    4.        lea edx,ps
    5.        invoke EndPaint,hWnd
    SRCCOPY определяет процесс копирования изображения. Весь вывод программы до этого направлялся контексту memDC, после этой операции выводимая информация отображается на экране. Если окно было перекрыто другим окном, а затем восстановлено, будет получено сообщение WM_PAINT и содержимое окна автоматически восстановится.
    В функции потока через PostMessage основному окну отправляется сообщение WM_USER+1 о том, что произошло изменение в массиве array1 или сообщение WM_USER+2 о том, что сортировка окончена. Получив сообщение WM_USER+2 или после выбора пользователем пункта меню "Сброс" поток уничтожается при помощи TerminateThread
     

    Вложения:

    • BubbleSort.zip
      Размер файла:
      8,9 КБ
      Просмотров:
      94
    DrochNaNoch нравится это.