― Есть три вещи, на которые можно смотреть бесконечно ―
горящий огонь, текущая вода и сортировка вставками... ​

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

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

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

 

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

«Сортировка Хоара», она же «быстрая сортировка», она же «обменная сортировка с разделением» ― улучшенный вариант сортировки с помощью прямого обмена ― относится к классу «сортировок обменом». Сперва производятся перестановки на наибольшем возможном расстоянии, после каждого прохода элементы делятся на две независимые группы.
Общая идея:

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

За время сортировки происходит в среднем [math]O(n\cdot log_{2}(n))[/math] обменов.

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

 

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

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

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

 

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

Она же «сортировка кучей» ― относится к классу «сортировок выбором». Алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае за [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-файлы и курсор

 

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

«Сортировка Шелла», она же «сортировка с убывающим смещением» ― относится к классу «сортировок вставками». Усовершенствованный вариант сортировки вставками, показывает хорошую скорость работы и не требует выделения дополнительной памяти.
Сортировки Шелла состоит из сравнения элементов последовательности, разделенных на группы и находящихся друг от друга на некотором расстоянии. Изначально это расстояние примерно равно [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=2¹⁵, 16384=2¹⁴, 8192=2¹³, 4096=2¹², 2048=2¹¹, 1024=2¹⁰, 512=2⁹, 256=2⁸, 128=2⁷, 64=2⁶, 32=2⁵, 16=2⁴, 8=2³, 4=2², 2=2¹, 1=2⁰ неплохой выбор, особенно, когда количество элементов ― степень двойки
• Последовательность Шелла [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-файлы и курсор

 

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

Относится к классу «сортировок выбором». Сортировка выбором может быть как устойчивой, так и неустойчивой. На массиве из [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-файлы и курсор

 

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

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

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

 

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

Сортировка расческой, она же сортировка гребнем ― относится к классу «сортировок обменом». Главный недостаток пузырьковой сортировки — полный перебор всех элементов массива. Скорость работы алгоритма зависит не от количества сравнений, а от количества перестановок.
Если в начале массива много больших элементов, которые нужно отправить в конец массива, тогда каждый раз их придется менять их местами с соседями, по одной перестановке за раз. Можно представить, что мы несем куда-то не слишком тяжелый груз, но после каждого шага ставим этот груз на пол, потом поднимаем, делаем шаг, снова ставим, снова поднимаем. Процедуры простые, но из-за устройства алгоритма мы делаем эти процедуры слишком много раз.
Если большие элементы тормозят весь процесс, тогда их нужно перекидывать не на соседнее место, а подальше. Так уменьшается количество перестановок, а с ними экономится и процессорное время, для их обработки.
Отправлять каждый большой элемент сразу в конец массива недальновидно — мы же не знаем, насколько этот элемент большой по сравнению с остальными элементами. Поэтому в сортировке расческой сравниваются элементы, которые отстоят друг от друга на каком-то расстоянии. Оно не слишком большое, чтобы сильно не откидывать элементы и возвращать потом большинство назад, но и не слишком маленькое, чтобы можно было отправлять не на соседнее место, а чуть дальше. Опытным путем было установлено оптимальное расстояние между элементами равное количеству элементов массива, деленному на 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-файлы и курсор

 

Intro,
ну вы же понимаете, что пишется это всё на ходу и криво, главное успеть к Новому году. О мерцании знаю, но пока не понял как это мерцание устранить. Про утечки памяти, спасибо, посмотрю внимательнее. Буду рад любым предложениям по улучшению

 

algent,
для замедления увеличьте задержку у Sleep.
Самое интересное, что Хоар разработал свою сортировку в Москве в 1959, куда он был направлен на стажировку в МГУ, где под руководством А.Н.Колмогорова занимался теорией вероятностей и машинным переводом.

 

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

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

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

 

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

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

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

 

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

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

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

 

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

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