Часть 1. «Быстрая сортировка».
1. Изучение алгоритма:
Быстрая сортировка относится к алгоритмам «разделяй и властвуй».
Алгоритм состоит из трёх шагов:
1) Выбрать элемент из массива (последний элемент). Назовём его опорным.
2) Разбиение: перераспределение элементов в массиве таким образом, что элементы меньше опорного помещаются перед ним, а больше или равные после.
3) Рекурсивно применить первые два шага к двум подмассивам слева и справа от опорного элемента. Рекурсия не применяется к массиву, в котором только один элемент или отсутствуют элементы.
2. Схема алгоритма:
3. Пример сортировки:
| № | Массив A |
| {8,1,5} | |
| {1,8,5} | |
| {1,5,8} |
4. Текст программы:
1. mov edx, 2
2. lea ebx, [A]
3. push ebx
4. mov eax, 3
5. dec eax
6. mul edx
7. add eax, ebx
8. push eax
9. mov ebp, 3
10. mov EDI, ebx
11. mov ESI, eax
12. prigay:
13. mov ecx, [edi]
14. mov edx, [esi]
15. cmp dx, cx
16. jl trash
17. cmp edi, esi
18. je konec
19. dec esi
20. dec esi
21. jmp prigay
22. trash:
23. mov EDI, ebx
24. mov ESI, eax
25. nachalo:
26. xor edx, edx
27. xor ecx, ecx
28. mov EAX, [EDI]
29. add EAX, [ESI]
30. mov ebx, 2
31. div bx
32. and eax, 0x00ff
33. mov CX, AX
34. nazad:
35. cmp EDI, ESI
36. jnl nychtonarodpognali
37. c1:
38. cmp EDI, ESI
39. jg syuda
40. cmp [EDI], CX
41. jnl tuda
42. add EDI, 2
43. jmp c1
44. tuda:
45. mov ecx, esi
46. sub ecx, edi
47. mov ebx, 2
48. cmp ecx, ebx
49. jng syuda
50. cmp [ESI], CX
51. jng syuda
52. sub ESI, 2
53. jmp tuda
54. syuda:
55. cmp EDI, ESI
56. jg nazad
57. mov ax, [edi]
58. mov bx, [esi]
59. push ax
60. push bx
61. pop ax
62. mov [edi], ax
63. pop bx
64. mov [esi], bx
65. add EDI, 2
66. sub ESI, 2
67. jmp nazad
68. nychtonarodpognali:
69. dec ebp
70. mov ecx, ebp
71. jcxz konec
72. cmp esi, edi
73. je ravenstvo
74. jl menshe
75. ravenstvo:
76. pop esi
77. jmp nachalo
78. menshe:
79. xchg edi, esi
80. pop edi
81. jmp nachalo
82. konec:
83. mov edx, 1
84. ret
85. section.data
86. A dw 0x8, 0x1, 0x5
5. Трассировочная таблица:
| № | EDX | EAX | EBX | ECX | ESI | EDI | EBP | STACK | MAS |
| - | - | - | - | - | - | - | - | ||
| - | - | 0x402000 | - | - | - | - | - | - | |
| - | - | - | - | - | - | - | 0x402000 | - | |
| - | - | - | - | - | - | - | - | ||
| - | - | - | - | - | - | - | - | ||
| - | - | - | - | - | |||||
| - | 0x402004 | - | - | - | - | - | - | - | |
| - | - | - | - | - | - | - | 0x402004 | - | |
| - | - | - | - | - | - | - | - | ||
| - | - | - | - | - | 0x402000 | - | - | - | |
| - | - | - | - | 0x402004 | - | - | - | - | |
| - | - | - | 0x10008 | - | - | - | - | - | |
| - | - | - | - | - | - | - | - | ||
| - | - | - | - | - | 0x402000 | - | - | - | |
| - | - | - | - | 0x402004 | - | - | - | - | |
| - | - | - | - | - | - | - | - | ||
| - | - | - | - | - | - | - | - | ||
| - | 0x10008 | - | - | - | - | - | - | - | |
| - | 0x1000d | - | - | - | - | - | - | - | |
| - | - | - | - | - | - | - | |||
| 0x10006 | - | - | - | - | - | - | - | ||
| - | - | - | - | - | - | - | - | ||
| - | - | - | - | - | - | ||||
| 35-44 | - | - | - | - | - | - | - | - | - |
| - | - | - | 0x402004 | - | - | - | - | - | |
| - | - | - | - | - | - | - | - | ||
| - | - | - | - | - | - | - | |||
| 48-51 | - | - | - | - | - | - | - | - | - |
| - | - | - | - | 0x402002 | - | - | - | - | |
| - | - | - | 0x402002 | - | - | - | - | - | |
| - | - | - | - | - | - | - | - | ||
| - | - | - | - | - | - | - | - | ||
| 48-49 | - | - | - | - | - | - | - | - | - |
| 55-56 | - | - | - | - | - | - | - | - | - |
| - | - | - | - | - | - | - | - | ||
| - | - | - | - | - | - | - | - | ||
| - | - | - | - | - | - | - | - | ||
| - | - | - | - | - | - | - | - | ||
| - | - | - | - | - | - | - | |||
| - | - | - | - | - | - | - | - | {1,1,5} | |
| - | - | - | - | - | - | - | - | ||
| - | - | - | - | - | - | - | - | {1,8,5} | |
| - | - | - | - | - | 0x402002 | - | - | - | |
| - | - | - | - | 0x402000 | - | - | - | - | |
| - | - | - | - | - | - | - | - | - | |
| 35-36 | - | - | - | - | - | - | - | - | - |
| - | - | - | - | - | - | - | - | ||
| - | - | - | - | - | - | - | - | ||
| 71-74 | - | - | - | - | - | - | - | - | - |
| - | - | - | - | 0x402002 | 0x402000 | - | - | - | |
| - | - | - | - | - | 0x402004 | - | - | - | |
| - | - | - | - | - | - | - | - | - | |
| - | - | - | - | - | - | - | - | ||
| - | - | - | |||||||
| - | - | - | - | - | - | - | - | ||
| - | 0x5000d | - | - | - | - | - | - | - | |
| - | - | - | - | - | - | - | |||
| - | 0x50006 | - | - | - | - | - | - | - | |
| - | - | - | - | - | - | - | - | ||
| - | - | ||||||||
| 34-36 | - | - | - | - | - | - | - | - | - |
| 71-74 | - | - | - | - | - | - | - | - | - |
| - | - | - | - | 0x402004 | 0x402002 | - | - | - | |
| - | - | - | - | - | 0x402000 | - | - | - | |
| - | - | - | - | - | - | - | - | ||
| - | - | - | - | - | - | - | |||
| - | 0x80001 | - | - | - | - | - | - | - | |
| - | 0x80006 | - | - | - | - | - | - | - | |
| - | - | - | - | - | - | - | |||
| - | 0x80003 | - | - | - | - | - | - | - | |
| - | - | - | - | - | - | - | - | ||
| - | - | - | - | - | - | - | |||
| 34-41 | - | - | - | - | - | - | - | - | - |
| - | - | - | - | - | 0x402002 | - | - | - | |
| - | - | - | - | - | - | - | - | - | |
| 38-41 | - | - | - | - | - | - | - | - | - |
| - | - | - | 0x402004 | - | - | - | - | - | |
| - | - | - | - | - | - | - | - | ||
| - | - | - | - | - | - | - | - | ||
| 48-49 | - | - | - | - | - | - | - | - | - |
| 55-56 | - | - | - | - | - | - | - | - | - |
| - | - | - | - | - | - | - | - | ||
| - | - | - | - | - | - | - | - | ||
| - | - | - | - | - | - | - | - | ||
| - | - | - | - | - | - | - | - | ||
| - | - | - | - | - | - | - | |||
| - | - | - | - | - | - | - | - | {1,5,5} | |
| - | - | - | - | - | - | - | |||
| - | - | - | - | - | - | - | - | {1,5,8} | |
| - | - | - | - | - | 0x402004 | - | - | - | |
| - | - | - | - | 0x402002 | - | - | - | - | |
| - | - | - | - | - | - | - | - | - | |
| 35-36 | - | - | - | - | - | - | - | - | - |
| - | - | - | - | - | - | - | - | ||
| - | - | - | - | - | - | - | - | ||
| - | - | - | - | - | - | - | - | - | |
| - | - | - | - | - | - | - | - | ||
| - | - | - | - | - | - | - | - | - |
6. Анализ сложности алгоритма:
Ясно, что операция разделения массива на две части относительно опорного элемента занимает время: O(log2n). Поскольку все операции разделения, проделываемые на одной глубине рекурсии, обрабатывают разные части исходного массива, размер которого постоянен, суммарно на каждом уровне рекурсии потребуется также O(n) операций. Следовательно, общая сложность алгоритма определяется лишь количеством разделений, то есть глубиной рекурсии. Глубина рекурсии, в свою очередь, зависит от сочетания входных данных и способа определения опорного элемента.
Лучший случай: O(n*log2n)
Среднее: O(n*logn)
Худший случай: O(n2)
Часть 2. «Двоичные деревья поиска».
1. Структура данных:
Двоичное дерево поиска записывается в один массив. Для хранения информации об одном узле необходимо четыре байта. Место под данные резервируется с помощью директивы db. В первом байте – значение узла; во втором – относительный номер строки меньшего по значению потомка; в третьем – относительный номер строки большего по значению потомка; в четвертом – «0», так как необходимо расширение до степени 2.
Порядок работы программы:
1) Поиск вводимого элемента рекурсивным способом.
2) Добавление вводимого элемента в дерево (пропуск, если элемент был найден).
3) Обход дерева и вывод всех элементов в порядке возрастания.
2. Схемы алгоритмов:
1) Рекурсивный поиск:
2) Добавление элемента:
3) Обход дерева:
3. Код программы:
1. xor eax, eax
2. mov ebp, len
3. shr ebp, 2
4. call Poisk
5. obhod:
lea ebx, [A]
6. xor ah, ah
7. mov ebp, 1
8. push ebp
9. print_tree:
mov al, [ebx+1]
10. cmp al, 0
11. je skip_1
12. push ebx
13. shl ax, 2
14. add bx, ax
15. call print_tree
16. skip_1:
mov al, [ebx]
17. PRINT_DEC 1, al
18. PRINT_STRING [Pr]
19. mov al, [ebx+2]
20. cmp al, 0
21. je skip_2
22. push ebx
23. shl ax, 2
24. add bx, ax
25. call print_tree
26. skip_2:
pop ebx
27. pop ebx
28. cmp ebx, ebp
29. je konec
30. mov cl, [ebx+1]
31. cmp cl, 0
32. je obnulit
33. mov cl, 0
34. mov [ebx+1], cl
35. call print_tree
36. obnulit:
mov [ebx+2], cl
37. jmp skip_2
38. konec:
NEWLINE
39. PRINT_STRING [z]
40. ret
41. Poisk:
mov dl,23; iskomoe znachenie
42. lea ebx, [A]
43. xor ecx, ecx
44. sub esp, 4
45. p:
add esp, 4
46. mov al, [ebx]
47. cmp al, dl
48. je allgood
49. jl menshe
50. mov cl, [ebx+1]
51. cmp cl, 0
52. je allbad
53. shl cl, 2
54. add bx, cx
55. call p
56. menshe:
mov cl, [ebx+2]
57. cmp cl, 0
58. je allbad
59. shl cl, 2
60. add bx, cx
61. call p
62. allbad:
PRINT_STRING [e]
63. PRINT_DEC 1, dl
64. PRINT_STRING [ne]
65. PRINT_STRING [n]
66. NEWLINE
67. call Dobavlenie_elementa
68. ret
69. allgood:
PRINT_STRING [e]
70. PRINT_DEC 1, dl
71. PRINT_STRING [n]
NEWLINE
72. ret
73. Dobavlenie_elementa:
lea ebx, [A]
74. lea esi, [A]
75. push ebp
76. shl ebp, 2
77. add esi, ebp
78. pop ebp
79. xor ecx, ecx
80. sub esp, 4
81. sravnenie:
add esp, 4
82. mov al, [ebx]
83. cmp al, dl
84. jl bolshe
85. mov cl, [ebx+1]
86. cmp cl, 0
87. je pomeshchenie
88. shl cl, 2
89. add bx, cx
90. call sravnenie
91. bolshe:
mov cl, [ebx+2]
92. cmp cl, 0
93. je pomeshchenie
94. shl cl, 2
95. add bx, cx
96. call sravnenie
97. pomeshchenie:
mov eax, esi
98. mov ecx, ebx
99. cmp dl, [ebx]
100. jg bolshe_uzla
101. sub eax, ecx
102. shr eax, 2
103. mov [ebx+1],al
104. jmp uvelichenie_massiva
105. bolshe_uzla:
106. sub eax, ecx
107. shr eax, 2
108. mov [ebx+2],al
109. uvelichenie_massiva:
mov [esi], dl
110. mov ecx, 3
111. xor eax, eax
112. c1:
113. inc esi
114. mov [esi], al
115. loop c1
116. inc ebp
117. PRINT_STRING [e]
118. PRINT_DEC 1, dl
119. PRINT_STRING [d]
NEWLINE
120. Ret
121. section.data
A db 18, 1, 2, 0
db 9, 3, 0, 0
db 21, 0, 0, 0
122. len equ $-A
123. Pr db " ", 0
124. e db " Элемент ", 0
125. n db " найден", 0
126. ne db " не", 0
127. d db " добавлен", 0
128. z db " Задача выполнена", 0
4. Трассировочная таблица:
| № | eax | ebx | ecx | edx | ebp | esi | edi | stack | вывод | |
| 0x0 | ||||||||||
| 0xc | ||||||||||
| 0x3 | ||||||||||
| <> | ||||||||||
| 0x19 | ||||||||||
| 0x4030d0 | ||||||||||
| 0x0 | ||||||||||
| 45-46 | ||||||||||
| 0x40130f | ||||||||||
| 48-50 | ||||||||||
| 0x2 | ||||||||||
| 58-59 | ||||||||||
| 0x8 | ||||||||||
| 0x4030d8 | ||||||||||
| <>,<> | ||||||||||
| <> | ||||||||||
| 0x401314 | ||||||||||
| 48-50 | ||||||||||
| 0x0 | ||||||||||
| 58-59 | ||||||||||
| 63-67 | Элемент 23 не найден | |||||||||
| <>,<> | ||||||||||
| 0x4030d0 | ||||||||||
| 0x4030d0 | ||||||||||
| <>,<>,0x3 | ||||||||||
| 0xc | ||||||||||
| 0x4030dc | ||||||||||
| 0x3 | <>,<> | |||||||||
| 0x0 | ||||||||||
| 82-83 | ||||||||||
| 0x40130f | ||||||||||
| 85-86 | ||||||||||
| 0x2 | ||||||||||
| 94-95 | ||||||||||
| 0x8 | ||||||||||
| 0x4030d8 | ||||||||||
| <>,<>,<> | ||||||||||
| <>,<> | ||||||||||
| 0x401314 | ||||||||||
| 85-86 | ||||||||||
| 0x0 | ||||||||||
| 94-95 | ||||||||||
| 0x4030dc | ||||||||||
| 0x4030d8 | ||||||||||
| 101-102 | ||||||||||
| 0x4 | ||||||||||
| 0x1 | ||||||||||
| Добавление относительного номера строки в массив для узла-родителя | ||||||||||
| Добавление элемента в массив | ||||||||||
| 0x3 | ||||||||||
| 0x4030dd | ||||||||||
| 0x2 | ||||||||||
| 0x4030de | ||||||||||
| 0x1 | ||||||||||
| 0x4030df | ||||||||||
| 0x0 | ||||||||||
| 0x4 | ||||||||||
| 117-120 | Элемент 23 не найден Элемент 23 добавлен | |||||||||
| <> | ||||||||||
| - | ||||||||||
| 0x4030d0 | ||||||||||
| 0x0 | ||||||||||
| 0x1 | ||||||||||
| 0x1 | ||||||||||
| 0x1 | ||||||||||
| 10-11 | ||||||||||
| 0x1, 0x4030d0 | ||||||||||
| 0x4 | ||||||||||
| 0x4030d4 | ||||||||||
| 0x1, 0x4030d0,<> | ||||||||||
| 0x0 | ||||||||||
| 10-11 | ||||||||||
| 0xa | ||||||||||
| 17-18 | Элемент 23 не найден Элемент 23 добавлен 9 | |||||||||
| 0x0 | ||||||||||
| 20-21 | ||||||||||
| <> | 0x1, 0x4030d0 | |||||||||
| 0x4030d0 | 0x1 | |||||||||
| 28-29 | ||||||||||
| 0x1 | ||||||||||
| 31-32 | ||||||||||
| 0x0 | ||||||||||
| Обнуление относительного номера строки | ||||||||||
| 0x1,<> | ||||||||||
| 0x0 | ||||||||||
| 10-11 | ||||||||||
| 0xf | ||||||||||
| 17-18 | Элемент 23 не найден Элемент 23 добавлен 9 18 | |||||||||
| 0x2 | ||||||||||
| 20-21 | ||||||||||
| 0x1,<>, 0x4030d0 | ||||||||||
| 0x8 | ||||||||||
| 0x4030d8 | ||||||||||
| 0x1,<>, 0x4030d0,<> | ||||||||||
| 0x0 | ||||||||||
| 10-11 | ||||||||||
| 0x14 | ||||||||||
| 17-18 | Элемент 23 не найден Элемент 23 добавлен 9 18 21 | |||||||||
| 0x1 | ||||||||||
| 20-21 | ||||||||||
| 0x1,<>, 0x4030d0,<>, 0x4030d8 | ||||||||||
| 0x4 | ||||||||||
| 0x4030dc | ||||||||||
| 0x1,<>, 0x4030d0,<>, 0x4030d8,<> | ||||||||||
| 0x0 | ||||||||||
| 10-11 | ||||||||||
| 0x19 | ||||||||||
| 17-18 | Элемент 23 не найден Элемент 23 добавлен 9 18 21 23 | |||||||||
| 0x0 | ||||||||||
| 20-21 | ||||||||||
| <> | 0x1,<>, 0x4030d0,<>, 0x4030d8 | |||||||||
| 0x4030d8 | 0x1,<>, 0x4030d0,<> | |||||||||
| 28-29 | ||||||||||
| 0x0 | ||||||||||
| 31-32 | ||||||||||
| Обнуление относительного номера строки | ||||||||||
| <> | 0x1,<>, 0x4030d0 | |||||||||
| 0x4030d0 | 0x1,<> | |||||||||
| 28-29 | ||||||||||
| 0x0 | ||||||||||
| 31-32 | ||||||||||
| Обнуление относительного номера строки | ||||||||||
| <> | 0x1 | |||||||||
| 0x1 | - | |||||||||
| 28-29 | ||||||||||
| 38-39 | Элемент 23 не найден Элемент 23 добавлен 9 18 21 23 Задача выполнена | |||||||||
5. Отчет:
Хранение информации в виде упорядоченного двоичного дерева позволило нам выполнить следующие операции с данными:
1) Поиск элементов.
2) Добавление элементов, в случаях неудачного поиска.
3) Вывод всех элементов, в том числе и добавленных, в порядке возрастания.
Двоичное дерево – один из многочисленных способов хранения данных. Как и все способы, он имеет преимущества и недостатки. Перечислим основные преимущества и недостатки хранения информации в виде упорядоченного двоичного дерева:
Преимущества:
1) Лёгкость работы с элементами.
2) Быстрый поиск.
Недостатки:
1) Сложность алгоритмов работы с элементами и поиска, сложность самой структуры.
2) Сложность поддержания сбалансированности дерева.
3) Не самый удачный способ хранения малого количества данных.