1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.
128.
129.
130.
131.
132.
133.
134.
135.
136.
137.
138.
139.
140.
141.
142.
143.
144.
145.
146.
147.
148.
149.
150.
151.
152.
153.
154.
155.
156.
157.
158.
159.
160.
161.
162.
163.
164.
165.
166.
167.
168.
169.
170.
171.
172.
173.
174.
175.
176.
177.
178.
179.
180.
181.
182.
183.
184.
185.
186.
187.
188.
189.
190.
191.
192.
193.
194.
195.
196.
197.
198.
199.
200.
201.
202.
203.
204.
205.
206.
207.
model small
.data
;задаем массив
mas db 9,0,6,7,4,1,5,2,8,3
n=$-mas+1
x db 0 ;временная переменная
i dw 0
l dw 0
m dw 0
j dw 0
k dw 0
.stack 256
.486
.code
insert_item_in_tree proc
;----------------------------------------------------------
;ПРОЦЕДУРА insert_item_in_tree (i, mas, N)
;на входе:
;si - номер элемента i в последовательности (с конца)
;mas - массив элементов
;m=n/2 - значение, равное половине числа элементов массива mas
;----------------------------------------------------------
push si
push cx
;j:=i
mov j,si ;j:=i
;@@m1:
@@m4:
mov si,j ;i->si
mov ax,j
;k:=2*j; l:=k+1
shl ax,1 ;j*2
mov k,ax ;k:=j*2
inc ax
mov l,ax ;l:=k+1
;ЕСЛИ (l=<N И (mas[j]<mas[k] ИЛИ mas[j]<mas[l]) ТО ПЕРЕЙТИ_НА @@m6
;ИНАЧЕ ПЕРЕЙТИ_НА @@m2
;КОН_ЕСЛИ
cmp ax,m ;l<m
ja @@m2
mov al,mas[si-1] ;ax:=mas[j]
mov di,k
cmp al,mas[di-1]
jna @@m6
inc di
cmp al,mas[di-1]
jna @@m6
jmp @@m2
;@@m6:
;ЕСЛИ mas[k]>mas[l] ТО ПЕРЕЙТИ_НА @@m4
;ИНАЧЕ ПЕРЕЙТИ_НА @@m3
;КОН_ЕСЛИ
@@m6:
;условие выполнилось:
;2j+1+<M AND (mas[j]<mas[2j] OR mas[j]<mas[2j+1])
;обмен с mas[j]
mov di,k
mov al,mas[di-1] ;ax:=mas[k]
inc di
cmp al,mas[di-1] ;mas[k]>mas[l]
jna @@m3
;@@m4:
;x:=mas[j]
;mas[j]:=mas[k]
;j:=k
;mas[k]:=x
;ПЕРЕЙТИ_НА @@m1
mov al,mas[si-1]
mov x,al ;x:=mas[j]
dec di
mov al,mas[di-1]
mov mas[si-1],al ;mas[j]:=mas[k]
mov j,di ;j:=k
mov al,x
mov mas[di-1],al ;mas[k]:=x
jmp @@m4
;@@m3: x:=mas[j]
; mas[j]:=mas[l]
; mas[l]:=x
; j:=l
;ПЕРЕЙТИ_НА @@m1
@@m3: ;mas[k] =< mas[l]
mov al,mas[si-1]
mov x,al ;x:=mas[j]
mov al,mas[di-1]
mov mas[si-1],al ;mas[j]:=mas[l]
mov j,di ;j:=l
mov al,x
mov mas[di-1],al ;mas[l]:=x
jmp @@m4
;@@m2:
;ЕСЛИ (k==n И mas[j]<mas[k]) ТО ПЕРЕЙТИ_НА @@m7
;ИНАЧЕ ПЕРЕЙТИ_НА @@m8
;КОН_ЕСЛИ
@@m2: ; условие не выполнилось: 2j+1+<M AND (mas[j]<mas[2j] OR mas[j]<mas[2j+1])
mov ax,k
cmp ax,m
jne @@m1
mov di,k
mov al,mas[di-1] ;al:=mas[k]
cmp mas[si-1],al ;mas[j]<mas[k]
jae @@m1
;@@m7: x:=mas[j]
;mas[j]:=mas[n]
;mas[n]:=x
mov al,mas[si-1]
mov x,al ;x:=mas[j]
mov di,n
mov al,mas[di-1]
mov mas[si-1],al ;mas[j]:=mas[n]
mov al,x
mov mas[di-1],al ;mas[n]:=x
;@@m8:
;ВОЗВРАТ
@@m1:
pop cx
pop si
ret
insert_item_in_tree endp
main:
mov dx,@data
mov ds,dx
mov cx,0
mov ah,02h
lea si,mas
inmas:
mov dl,[si]
add dl,30h
int 21h
inc cx
inc si
cmp cx,10
jb inmas
mov dx,0Ah
int 21h
mov dx,0Dh
int 21h
;i:=n/2; l:=i; m:=n
mov ax,n ;n-1
mov m,ax ;m:=n
shr ax,1
mov i,ax ;i:=n\2
mov l,ax ;l:=i
;//строим пирамиду на основе входного массива
;ДЛЯ k:=1 ДО l
;строим пирамиду:
mov cx,l ;цикл по k:=1..l
mov si,i
@@cycl1:
;НАЧ_БЛОК_1
mov i,si
;insert_item_in_tree (i, mas, m)
call insert_item_in_tree
;i:=i-1
dec si ;i:=i-1
;КОН_БЛОК_1
loop @@cycl1
;а теперь собственно сортировка:
;//сортируем пирамиду
;ДЛЯ k:=2 ДО n
mov cx,n-1 ;n-2
@@cycl2:
;НАЧ_БЛОК_1
;x:=mas[1]
;mas[1]:=mas[m]
;mas[m]:=x
;m=m-1
xor si,si
mov al,mas[si]
mov x,al ;x:=mas[1]
mov di,m
mov al,mas[di-1]
mov mas[si],al ;mas[1]:=mas[m]
mov al,x
mov mas[di-1],al ;mas[m]:=x
dec m
inc si ;i:=1
;insert_item_in_tree (1, mas, m)
call insert_item_in_tree
;КОН_БЛОК_1
loop @@cycl2
;вывод
mov cx,0
mov ah,02h
lea si,mas
outmas:
mov dl,[si]
add dl,30h
int 21h
inc cx
inc si
cmp cx,10
jb outmas
;выход
mov ax,4c00h
int 21h
end main
