Программа для сортировки любого массива

@novic-di · Регистрация: 10.02.2011

Студворк — интернет-сервис помощи студентам

Отсортировать любой массив. Создать программу для отсортировки любого массива.

@Vadimych · 23.11.2011, 20:18

novic-di, поищите по разделу, тут таких программ навалом уже.

@masterlomaster · 23.11.2011, 21:17

Метод пузырька.

Assembler
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
data segment para public
N dw 5
M dw 5, 2, 1, 11, 6
data ends
 
stck segment para stack
dw 32 dup(?)
stck ends
 
code segment para public
assume cs:code, ds:data, ss:stck
 
 
start:
    mov ax, data
    mov ds, ax
        mov bp,N
C:
    mov cx, N
    dec cx
    lea bx, M
        xor si, si                
B:
    mov ax, [bx + si]
    mov di, si
    A:
        add di, 2
        mov dx, [bx + di]
 
        cmp ax, dx
        jl davaytuda
            mov [bx+di], ax
            mov [bx+si], dx
    davaytuda:
 
     mov dx, N
     shl dx, 1
     cmp di, dx
     jnl  A
     add si, 2
     loop B
         xor si, si
         xor di, di
         dec bp
         cmp bp,0
         jne c
 
 
 
         mov ah,1   
         int 21h
         mov ax, 4c00h
         int 21h
 
    
 
code ends
end start

@Mikl___ · 25.11.2011, 05:03

Сортирую двойные слова
Пузырьковая

Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
.data
R dd n-1;количество неотсортированных элементов минус один
array  dd 10,450,320,120,180,600,50,230,340,460,550,500,130
      dd 80,390,410,20,800,670,60,730,610,310,0,360,200
n = ($-array)/4
.code
    mov esi,offset array    ;позиционируемся на массив
a2:    mov ecx,R    
    xor ebx,ebx        ;флаг – были/не были перестановки в проходе
a3:    mov eax,[esi+ecx*4-4]    ;получаем значение очередного элемента    
    cmp [esi+ecx*4],eax    ;сравниваем со значением соседнего элемента
    jnb a4    ;если больше или равен - идем к следующему элементу
    setna bl    ;была перестановка - взводим флаг
    xchg eax,[esi+ecx*4]    ;меняем значение элементов местами
    mov [esi+ecx*4-4],eax
a4:    loop a3    ;двигаемся вверх до границы массива
    add esi,4    ;сдвигаем границу отсортированного массива
    dec ebx    ;проверяем были ли перестановки
    jnz exit    ;если перестановок не было - заканчиваем сортировку
    dec R        ;уменьшаем количество неотсортированных элементов
    jnz a2;если есть еще неотсортированные элементы - начинаем новый проход
exit:

При упорядочении массива из n элементов произойдет в лучшем случае, если массив отсортирован — n-1 сравнений. В худшем случае, если массив отсортирован в обратном порядке — при сортировке произойдет n*(n-1)/2 сравнений. (для n=26 элементов лучший случай — 25, средний — 289, худший — 325)
Шейкер

Assembler
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
.data
H dd 0    ;верхняя граница неотсортированного массива
L dd n-1    ;нижняя граница неотсортированного массива
.code
    xor esi,esi        ;нижняя граница неотсортированного массива
    xor ebx,ebx        ;флаг - были/не были перестановки в проходе
    mov ecx,L;количество неотсортированных элементов снизу минус один
a4:    inc esi
      call Compare_and_Swapping    ;сравнение и обмен значений элементов
    loop a4                ;двигаемся вниз до границы массива
    dec ebx                ;проверяем были ли перестановки
    jnz exit        ;если перестановок не было - сортировка закончена 
    dec L        ;уменьшаем количество неотсортированных элементов снизу
    jz exit    ;достигли границы массива
    dec esi        ;esi=L
    mov ecx,esi
    sub ecx,H;количество неотсортированных элементов сверху минус один
    jecxz exit    ;если граница снизу равна границе сверху - выходим
a2:    call Compare_Swapping        ;сравнение и обмен значений элементов
    dec esi
    loop a2                ;двигаемся вверх до границы массива
    dec ebx                ;проверяем были ли перестановки
    jnz exit    ;если перестановок не было - заканчиваем сортировку
    inc H    ;уменьшаем количество неотсортированных элементов сверху
    inc esi        ;esi=H
    mov ecx,L    
    sub ecx,esi    ;если граница снизу больше, чем граница сверху – значит 
    ja a4;есть еще неотсортированные элементы - начинаем новый проход
exit:    . . .
Compare_Swapping proc;сравнение и обмен значений соседних элементов
    mov eax,array[esi*4]    ;получаем значение очередного элемента
    cmp array[esi*4-4],eax    ;сравниваем его с соседним элементом
    jna a3    ;если меньше или равен - идем к следующему элементу
    seta bl    ;если была перестановка - взводим флаг
    xchg eax,array[esi*4-4]        ;меняем значения элементов местами
    mov array[esi*4],eax
a3:    ret
Compare_Swapping endp

n=26 элементов лучший случай — 25, средний — 259 (лучше пузырьковой сортировки на 20%), худший — 325
Пирамидальная

Assembler
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
.data
L dd n/2-1    ;левая граница неотсортированного массива
R dd n-1        ;правая граница неотсортированного массива
.code
;массив преобразуется в отображение пирамиды – вызвать процедуру
;down_heap n/2 раз для преобразования массива  в пирамиду
b0:     call down_heap
        dec L        ;while ( L > 0 ) L--;
        jnz short b0
;собственно пирамидальная сортировка
       dec L        ;L=0
       dec R        ;R=n-2
b1:     mov edx,R   ;отправляем значение максимального
       mov eax,array    ;элемента в конец массива
        xchg eax,array[edx*4+4] ; array[0] <--> array[R];
        mov array,eax
        call down_heap   ;восстанавливаем пирамиду - на ее 
;вершине появляется новое максимальное значение      
        dec R        ;уменьшаем индекс последнего элемента
        jnz short b1    ;while ( R > 0 ) R--;
b2:        ...
;-----------------------------------------------------
down_heap proc; процедура вставки элемента на свое место в пирамиду
        mov eax,L
        mov ebx,eax            ;i = L;
        shl eax,1            ;j = 2*L;
        mov esi,array[eax*2]    ;item = array[L]; 
        cmp eax,R     ;if( j<R && array[j] < array[j+1]) j++; 
        jnb short a0
        mov edx,array[eax*4]
        cmp edx,array[eax*4+4]    ;array[j] < array[j+1] ?
        jnb short a0
; условие j<R && array[j]<array[j+1] выполнилось
        inc eax              ;j++
a0:     cmp eax,R           ;while( j<=R && item < array[j])
        ja short a1
        mov edi,array[eax*4]
        cmp esi,edi        ;item < array[j] ?
        jnb short a1
; условие j<=R && item < array[j] выполнилось
       mov array[ebx*4],edi    ;array[i] = array[j];
        mov ebx,eax        ;i = j;                                    
        shl eax,1            ;j = 2*j;
        cmp eax,R
        jnb short a0;if( j<R && array[j] < array[j+1]) j++;
        mov edx,array[eax*4]
        cmp edx,array[eax*4+4]
        jnb short a0
; условие j<R && array[j] < array[j+1] выполнилось
        inc eax            ;j++
       jmp short a0
a1:       mov array[ebx*4],esi    ;array[i] = item;
        retn
down_heap endp

n=26 элементов средний случай— 109 (лучше пузырьковой сортировки почти в 3 раза)

Добавлено через 3 минуты
сортировка прямым включением

Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
mov esi,4       ;i=1
a4:    push esi
a3:    mov eax,array[esi-4]
     cmp eax,array[esi]
    jb a2
    xchg eax,array[esi]
    sub esi,4    ;двигаемся к началу массива
    mov array[esi],eax
    jnz a3
a2:    pop esi
     add esi,4       ;двигаемся к концу массива
    cmp esi,n*4     ;просмотрели весь массив?
    jb a4

n=26 элементов лучший случай — 25, средний — 172 (лучше пузырьковой сортировки на 40%), худший — 325
Алгоритм можно улучшить пользуясь тем, что готовая последовательность уже упорядочена. Место вставки нового элемента можно найти значительно быстрее, если применить бинарный поиск, исследовав сперва средний элемент упорядоченной последовательности и продолжая деление пополам, пока не будет найдено место вставки. Для n=26 элементов лучший случай — 25, средний и худший — 106 (лучше пузырьковой сортировки почти в 3 раза)

Assembler
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
mov ebx,1  ;ebx - граница неотсортированного массива
b1:    mov edi,ebx
    mov edx,edi;edi индекс первого элемента отсортированного массива
    xor esi,esi;esi индекс последнего элемента отсортированного массива
    mov eax,array[ebx*4]
    cmp eax,array[ebx*4-4]
    jnb b2
b6:    cmp esi,edi        ;проверка esi>edi на завершение поиска
    jg b5    ;проверены все элементы, вставляем новый элемент 
    shr edx,1 ;индекс центрального элемента равен (edi+esi)/2
    cmp array[edx*4],eax;сравниваем с искомым значением
    ja b3               ;array[edx*4]<eax
    jz b5               ;array[edx*4]=eax
     inc edx        ;учтем только что проверенное значение
    mov esi,edx    ;изменяем нижнюю границу поиска
    add edx,edi    ;создаем индекс центрального элемента
    jmp short b6    ;переходим к следующему элементу
b3:    dec edx        ;учтем только что проверенное значение
    mov edi,edx    ;изменяем верхнюю границу поиска
    add edx,esi    ;создаем индекс центрального элемента
    jmp b6        ;переходим к следующему элементу
b5:    mov ecx,ebx    ;сдвигаем отсортированные элементы, чтобы
    sub ecx,esi    ;освободить место для нового элемента
    shl esi,2; esi=esi*4
    push eax
b7:    mov eax,array[esi+ecx*4-4];сдвиг отсортированных элементов
    mov array[esi+ecx*4],eax
    loop b7
    pop eax
    mov array[esi],eax;вставляем новый элемент
b2:  inc ebx
    cmp ebx,n
    jb b1

сортировка прямым выбором
На массиве из n элементов время выполнения в худшем, среднем и лучшем случае n*(n-1)/2

Assembler
1
2
3
4
5
6
7
8
9
10
11
12
mov edi,offset array    ;edi = указатель на массив
       mov ecx,N            ;ecx = количество элементов
a0:    lea ebx,[edi+ecx*4]    ;ebx = максимальный индекс в проходе+1
     mov eax,[edi]    ;eax=min=величина первого элемента в проходе
a1:     sub ebx,4        ;двигаемся по проходу вверх
     cmp eax,[ebx]
     jbe a2        ;min > array[ebx] ?
     xchg eax,[ebx]    ;swap(array[ebx],min)
a2:     cmp ebx,edi
     jnz a1        ;проход закончился?
     stosd ;mov [edi],eax edi=+4 на первой позиции минимальный элемент
     loop a0

сортировка Шелла
Среднее время работы алгоритма зависит от длин промежутков, на которых будут находится сортируемые элементы исходного списка на каждом шаге алгоритма
при выборе последовательности значений d1=n/2, d2=d1/2,...,1 в худшем случае алгоритм выполнит O(n2) — сравнений 140
Table dd 32768,16384,8192,4096,2048,1024,512,256, 128,64,32,16,8,4,2,1
все значения (3^j−1)/2 < n, такая последовательность шагов приводит к алгоритму класса O(n^(3/2)) — сравнений 108
Table dd 797161,265720,88573,29524,9841,3280,1093 ,364,121,40,13,4,1
последовательности вида N=2*N+1 — сравнений 118
Table dd 32767,16383,8191,4095,2047,1023,511,255, 127,63,31,15,7,3,1
последовательность Дж.Инсерпи и Р.Седгевика — сравнений 115:
Table dd 198768,86961,33936,13776,4592,1968,861,3 36,112,48,21,7,3,1

Assembler
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
.data
Table dd 797161,265720,88573,29524,9841,3280,1093,364,121,40,13,4,1
.code
mov ecx,-14;в таблице приращений 13 элементов
entry: inc ecx
jz exit; если последний элемент в таблице - выход из программы
cmp [Table+ecx*4+13*4],n; ищем максимальное приращение (gap), 
jge entry;соответствующее размеру нашего массива
a6:    mov edx,[Table+ecx*4+13*4];получаем очередное приращение из таблицы
shl edx,2;выбрали интервал,у нас двойные слова,поэтому edx=edx*4
a2:    mov ebx,edx;i=gap
a3:    mov esi,ebx
sub esi,edx;j=i-gap
a4:    mov eax,array[esi];for(i=gap;i<dim;i++)/*проход массива*/
    cmp eax,array[esi+edx];сравнение пар,отстоящих 
jbe a5;на gap друг от друга
xchg eax,array[esi+edx];swap(a[j],a[j+gap])
mov array[esi],eax
sub esi,edx  ;j-=gap
jge a4 
a5:    add ebx,4    ;i++
cmp ebx,n*4  ;i < dim
jb a3        ;for(j=i-gap; j>=0 && a[j] > a[j+gap]
inc ecx
jnz a6
exit:

сортировка Хоара (быстрая сортировка)
Сортировка даёт в среднем O(n log n) сравнений

Assembler
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
push    offset array+n*4-4;указатель на последний элемент
        push    offset array;указатель на первый элемент массива
        call    quick_sort      ; quicksort (data, data+n-1)
;-----------------------------------------------------
partition proc    Lb:dword,    Ub:dword
; функция partition возвращает адрес pivot 
        mov edx,Ub
       sub edx,eax             ;eax=Lb
       shr edx,3             ;(Ub-Lb)/2
; После завершения этого цикла все значения слева от элемента pivot 
; будут меньше значения элемента pivot, а все значения справа от 
; элемента pivot будут больше, чем значение элемента pivot
        mov edi,[eax+edx*4]   ;получаем указатель на pivot
;pivot = *(Lb+(Ub-Lb)/2)
        cmp eax,Ub         ;eax=Lb
        ja short b0             ;return Lb;
; Поиск значения, большего чем pivot, в нижней части массива
b1:     mov eax,Lb        
        cmp [eax],edi        ;edi=pivot
        jnl short b3        ;while (*Lb < pivot)
       add Lb,4            ;Lb++;   
       jmp short b1
; Поиск значения, меньшего чем pivot, в верхней части массива
b4:     sub Ub,4        
b3:     mov eax,Ub
        cmp [eax],edi        ;while (*Ub > pivot)
        jg short b4             ;Ub-- 
        mov ecx,Lb
       cmp ecx,eax             ;eax=Ub
        ja short b5           ;if(Lb <= Ub)
        sub Ub,4        ;swap( Lb++, Ub-- )
        add Lb,4        
        mov edx,[eax]        ;eax=Ub
        xchg edx,[ecx]        ;ecx=Lb
        mov [eax],edx        ;*Ub<-->*Lb;
b5:     mov eax,Lb
        cmp eax,Ub
        jbe short b1        ;while (*Lb < pivot)
b0:     pop ebp
        retn 8
partition endp
;------------------------------------------------------------
quick_sort proc Lb:dword, Ub:dword
         mov eax,Lb
         cmp eax,Ub ; if (Lb >= Ub)
         jnb short exit1    ;сортировать нечего
         push Ub
         push eax        ;eax=Lb
         call partition  
        mov edi,eax     ;eax=pivot_ptr
         sub eax,4        ;pivot_ptr-1
         push eax
         push Lb    
         call quick_sort ;отсортируем то, что слева от pivot
         push Ub
         push edi        ;edi=pivot_ptr
         call quick_sort ; и то, что справа от pivot
exit1:   pop ebp
         retn 8
quick_sort endp

ФедосеевПавел · 01.05.2017, 15:56

Сортировка Шелла (DOS 16 бит)
Отличие, от приведённого Mikl___ - используются 16 битные регистры и длина промежутка берётся не оптимальной (из таблицы), а вычисляется по упрощённому алгоритму - на каждом шаге длина промежутка уменьшается вдвое.
И дополнительно, код оформлен в виде процедуры.

О сортировке можно почитать на страницах Wikipedia
https://ru.wikipedia.org/wiki/Сортировка_Шелла
https://en.wikipedia.org/wiki/Shellsort
https://ru.wikibooks.org/wiki/... овка/Шелла

На русскоязычной странице Wikipedia приведён код на языке C с упрощённым выбором длины промежутка:

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// BaseType - любой перечисляемый тип 
// typedef int BaseType - пример
void ShellsSort(BaseType *A, unsigned N)
{
    unsigned i,j,k;
    BaseType t;
    for(k = N/2; k > 0; k /=2)
        for(i = k; i < N; i++)
        {
            t = A[i];
            for(j = i; j>=k; j-=k)
            {
                if(t < A[j-k])
                    A[j] = A[j-k];
                else
                    break;
            }
            A[j] = t;
        }
}

Переведём его на Assembler.
Соответствие регистров переменным
ax - t
bx - адрес A
cx - k
dx - N
si - i
di - j

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

В комментариях используется код на языке C.

Assembler
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
;Сортировка Шелла
;для массива слов (word)
;на входе
; ds:dx - адрес массива слов (word)
; cx    - длина массива
ShellsSort      proc
        mov     bx,     dx      ;bx - адрес массива
        mov     dx,     cx      ;dx - длина масива
 
        shl     dx,     1       ;для удобства приведём индекс к размерности элемента
        ;for(k = N/2; k > 0; k /=2)
@@ForK:
        shr     cx,     1       ;k/=2
        jcxz    @@BreakK        ;k>0
        ;       for(i = k; i < N; i++)
        shl     cx,     1       ;для удобства приведём индекс к размерности элемента
        mov     si,     cx      ;i=k
@@ForI:
        ;               t=A[i]
        mov     ax,      [bx+si]
        ;               for(j = i; j>=k; j-=k)
        mov     di,     si              ;j=i
        push    si
        sub     si,     cx
        @@ForJ:
        ;                       if(t < A[j-k])
                cmp     ax,     [bx+si]
                jge     @@BreakJ
                push    ax
                mov     ax,     [bx+si] ;ax=A[j-k]
                mov     [bx+di],ax      ;A[j]=A[j-k]
                pop     ax
 
                sub     di,     cx      ;j-=k
                sub     si,     cx
                cmp     di,     cx      ;j>=k
                jae     @@ForJ
        @@BreakJ:
        pop     si
        ;               A[j]=t
        mov     [bx+di],        ax
        add     si,     2       ;i++ (т.к. размер элемента массива равен 2)
        cmp     si,     dx      ;i<N
        jb      @@ForI
        shr     cx,     1       ;возвращение значения cx
 
        jmp     @@ForK
@@BreakK:
        ret
ShellsSort      endp

Пример использования

Assembler
1
2
3
4
5
6
7
8
9
10
11
.data
 
        Array           dw      100, 192, 500, -200, 845, -900, 754, 999, -999, 321
                        dw      2, -7, 888, -777, 2134, -4521
        Len             dw      ($-Array)/2
.code
.................
        lea     dx,     Array
        mov     cx,     Len
        call    ShellsSort
.................

ФедосеевПавел · 29.05.2017, 00:30

Сортировка пузырьком (DOS 16 бит)

Ранее Mikl___ уже приводил пример данной сортировки для упорядочивания двойных слов. Добавлю ещё два примера для сортировки байта и слова. Алгоритмическое отличие от приведённой Mikl___ в том, что подпрограмма продолжит просматривать отсортированный массив (конечно, это можно улучшить). Кроме того, не используются новые команды процессора. Это, конечно, не очень хорошо, но зато позволяет компилироваться без включения директив компилятора, разрешающих эти команды (для новичков это довольно критично).

Сортировка пузырьком интересна тем, что она устойчивая и простая в реализации. Этим обусловлено её применение за пределами собственно сортировки.

Примеры нестандартного применения сортировки "пузырьком" для упорядочивания массивов по критериям отличным от привычного "по неубыванию":
Вывод на экран упорядоченной строки - сначала цифры потом буквы
Сортировка массива: числа по убыванию с начала, буквы по убыванию в конце
Все отрицательные элементы массива А необходимо поставить в начало массива, а положительные в конец
Сортировка массива: в начале - все отрицательные, затем - нулевые, в конце - все положительные (с сохранением порядка)

Сортировка "пузырьком" по неубыванию на языке высокого уровня Pascal выглядит так (это, скорее, не "пузырёк", а "кирпичик", но сути не меняет)

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
  { Сортировка "пузырьком" }
  procedure BubbleSort(var A: mas; N: integer);
  var
    i, j: integer;
    x: byte;
  begin
    for i := 1 to N - 1 do
      for j := N downto i + 1 do
        if A[j] < A[j - 1] then
        begin
          x := A[j];
          A[j] := A[j - 1];
          A[j - 1] := x;
        end;
  end;

Внимательно присмотримся к алгоритму. Видно, что переменная i почти не участвует в алгоритме и используется лишь, как ограничитель для индекса j. А цикл по j выполняется хотя бы один раз. Таким образом, можно перезаписать этот алгоритм в виде

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
  procedure BubbleSort(var A: TArray; N: integer);
  var
    i, j: integer;
    x: integer;
  begin
    for i := 1 to N - 1 do
    begin
      j := N;
      repeat
        if (A[j] < A[j - 1] then
        begin
          x := A[j];
          A[j] := A[j - 1];
          A[j - 1] := x;
        end;
        Dec(j);
      until (j<=i);
    end;
  end;

Для массива байт (или символьной строки)

Assembler
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
;Сортировка "пузырьком" массива байт
;на входе
;  ds:si - адрес массива байт
;  cx    - длина массива
BubbleSort      proc
        push    ax
        push    bx
        push    cx
        push    dx
        push    si
        push    di
 
        mov     bx,     si
        mov     dx,     cx
        dec     dx
        dec     cx                      ;for i:=1 to N-1 do
        mov     si,     0
@@ForI:
        mov     di,     dx              ;  j:=N
@@ForJ:                                 ;  repeat
        mov     al,     [bx+di-1]       ;    if (a[j] < and a[j - 1]) then
        cmp     al,     [bx+di]         ;    begin
        jbe     @@NextJ                 ;
        xchg    al,     [bx+di]         ;      temp:=a[j]
        xchg    al,     [bx+di-1]       ;      a[j]:=a[j-1]
        xchg    al,     [bx+di]         ;      a[j-1]:=a[j]
@@NextJ:                                ;    end
        sub     di,     1               ;    dec(j)
        cmp     di,     si              ;  until j<=i;
        ja      @@ForJ
        add     si,     1               ;  end; for i равноценно inc(i)
        loop    @@ForI
 
        pop     di
        pop     si
        pop     dx
        pop     cx
        pop     bx
        pop     ax
        ret
BubbleSort      endp

Изменения для сортировки слов минимальны

Assembler
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
;Сортировка "пузырьком" массива слов
;на входе
;  ds:si - адрес массива слов
;  cx    - длина массива
BubbleSort      proc        push    ax
        push    bx
        push    cx
        push    dx
        push    si
        push    di
 
        mov     bx,     si
        mov     dx,     cx
        dec     dx
        shl     dx,     1               ;приведение dx=N к размерности элементов
        dec     cx                      ;for i:=1 to N-1 do
        mov     si,     0
@@ForI:
        mov     di,     dx              ;  j:=N
@@ForJ:                                 ;  repeat
        mov     ax,     [bx+di-2]       ;    (a[j] < and a[j - 1])
        cmp     ax,     [bx+di]
        jbe     @@NextJ                 ;    if r<0 then
        xchg    ax,     [bx+di]         ;      temp:=a[j]
        xchg    ax,     [bx+di-2]       ;      a[j]:=a[j-1]
        xchg    ax,     [bx+di]         ;      a[j-1]:=a[j]
@@NextJ:
        sub     di,     2               ;    dec(j)
        cmp     di,     si              ;  until j<=i;
        ja      @@ForJ
        add     si,     2               ;  end; for i равноценно inc(i)
        loop    @@ForI
 
        pop     di
        pop     si
        pop     dx
        pop     cx
        pop     bx
        pop     ax
        ret
BubbleSort      endp

Или ещё вариант

Assembler
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
;Сортировка "пузырьком" массива двухбайтных чисел со знаком
;на входе
;  ds:si - адрес массива
;  cx    - количество элементов в массиве
BubbleSort      proc
        push    ax
        push    bx
        push    cx
        push    dx
        push    si
        push    di
        push    es
 
        ;настройка для строковых операций
        mov     ax,     ds
        mov     es,     ax
        cld
 
        ;получение адреса N-го элемента массива
        dec     cx
        mov     ax,     2
        mul     cx
        add     si,     ax
        mov     dx,     si                              ;dx - адрес a[N]
        @@ForI:                                         ;for i:=1 to N-1 do
                mov     si,     dx                      ;begin
                push    cx                              ;  for j:=N downto i+1 do
                @@ForJ:                                 ;  begin
                        mov     ax,     [si]            ;    if(a[j] < a[j-1]) then
                        cmp     ax,     [si-2]
                        jge     @@NextJ                 ;    begin
                                push    word ptr [si-2] ;      temp:=a[j-1];
                                mov     [si-2], ax      ;      a[j-1]:=a[j];
                                pop     word ptr [si]   ;      a[i]:=temp;
                @@NextJ:                                ;    end;
                        sub     si,     2
                loop    @@ForJ                          ;  end;
                pop     cx
        loop    @@ForI                                  ;end;
 
        pop     es
        pop     di
        pop     si
        pop     dx
        pop     cx
        pop     bx
        pop     ax
        ret
BubbleSort      endp

Пример вызова

Assembler
1
2
3
    lea si, Array
    mov cx, Len
    call BubbleSort

ФедосеевПавел · 11.06.2017, 12:32

Двоичная поразрядная сортировка массива беззнаковых целых чисел (DOS 16 бит)

О поразрядной сортировке и её разновидностях можно почитать по ссылкам:
http://algolist.manual.ru/sort/radix_sort.php
https://en.wikipedia.org/wiki/Radix_sort
https://ru.wikipedia.org/wiki/... сортировка
Особенно рекомендую статью с algolist.manual.ru.

В Wikipedia приводится ссылка на примеры реализации в Wikibooks:
https://ru.wikibooks.org/wiki/... оразрядная
https://en.wikibooks.org/wiki/... Radix_sort

За основу для реализации на ассемблере возьму вариант из русской странички Wikibooks:

Вариант сортировки 32 битных unsigned int. Не самый быстрый.

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void radix_int(unsigned* begin, int size, unsigned bit = 0x80000000)
{
    if (!bit)
        return;
 
    if (size < 2)
        return;
 
    int last = 0;
    for (int i = 0; i < size; i++)
    {
        if ((begin[i] & bit) == 0)
            swap(begin[last++], begin[i]);
    }
 
    radix_int(begin,      last,      bit >> 1);
    radix_int(begin+last, size-last, bit >> 1);
}

Этот вариант ничем не лучше других, по скорости выполнения, даже медленнее (т.е. - хуже), но при реализации учебной программы на ассемблере имеется сомнительное достоинство - отсутствие дополнительных массивов для хранения промежуточных результатов. Это "достоинство" с лихвой компенсируется расходом стека на рекурсивные вызовы и хранение аргументов и регистров - т.е. придётся объявлять достаточно большой размер стека.

Т.к. имеем дело с рекурсивными вызовами, то параметры вызова удобнее передавать через стек. Можно "вручную" определять смещения аргументов в стеке, но, всё же, удобнее воспользоваться директивами объявления процедур, символьными метками аргументов. Для этого придётся объявить вместе с моделью памяти ещё и модель соглашения передачи аргументов процедуре вместе с указанием ответственного за очистку стека от этих аргументов (чаще всего это ассоциируется с названиями языков высокого уровня). Я выбрал Pascal: .model small, Pascal, что означает передачу параметров слева-направо и очистку в вызываемой процедуре.
Реализация для диалекта tasm (немного переименовал названия параметров, т.к. некоторые слова из исходника на С являются зарезервированными в tasm):

Assembler
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
RadixSort       proc
                arg pBegin:WORD, uiSize:WORD, uiMask:WORD
                uses ax,bx,cx,si,di
 
        cmp     [uiMask],       0       ;    if (!uiMask) return;
        je      @@Return
        cmp     [uiSize],       2       ;    if (uiSize < 2) return;
        jb      @@Return
 
        mov     bx,     0               ;    int last = 0;
        mov     di,     [pBegin]        ;
 
        mov     si,     [pBegin]        ;    for (int i = 0; i < uiSize; i++)
        mov     cx,     [uiSize]
@@For:                                  ;    {
        mov     ax,     [si]            ;      if ((pBegin[i] & uiMask) == 0)
        test    ax,     [uiMask]
        jnz     @@Next
        xchg    ax,     [si]            ;        swap(pBegin[last++], pBegin[i]);
        xchg    ax,     [di]
        xchg    ax,     [si]
        inc     bx
        add     di,     2
@@Next:
        add     si,     2
        loop    @@For                   ;    }
 
        mov     ax,     [pBegin]        ;    RadixSort(pBegin, last, uiMask >> 1);
        push    ax
        mov     ax,     bx
        push    ax
        mov     ax,     [uiMask]
        shr     ax,     1
        push    ax
        call    RadixSort
        mov     ax,     di              ;    RadixSort(pBegin+last, uiSize-last, uiMask >> 1);
        push    ax
        mov     ax,     [uiSize]
        sub     ax,     bx
        push    ax
        mov     ax,     [uiMask]
        shr     ax,     1
        push    ax
        call    RadixSort
 
@@Return:
        ret
RadixSort       endp

Несомненно, даже для этой реализации несовершенного алгоритма можно выполнить улучшения (сократив количество обращений к памяти, общее число операндов), но они могут ухудшить читабельность исходника.

Пример программы, использующей данную процедуру

Assembler
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
LOCALS
 
.model small, Pascal
 
.stack 1000h
 
.data
 
        A               dw      100, 20, 500, 800, 600, 42, 32, 7894, 6541
        N               dw      ($-A)/2
 
.code
 
main    proc
        mov     ax,     @data
        mov     ds,     ax
 
        ;сортировка массива
        lea     ax,     A
        push    ax
        mov     ax,     N
        push    N
        mov     ax,     8000h
        push    ax
        call    RadixSort
 
        mov     ax,     4C00h
        int     21h
main    endp
 
RadixSort       proc
        ;....................
        ret
RadixSort       endp
 
end     main

Более полный пример работы процедуры сортировки приведён в теме Двоичная поразрядная сортировка массива целых чисел

ФедосеевПавел · 31.10.2017, 18:34

Быстрая сортировка (Quick Sort) массива знаковых целых чисел (DOS 16 бит)

О быстрой сортировке и её разновидностях можно почитать по ссылкам:
http://algolist.manual.ru/sort/quick_sort.php
https://en.wikipedia.org/wiki/Quicksort
https://ru.wikipedia.org/wiki/Быстрая_сортировка

В Wikipedia приводится ссылка на примеры реализации в Wikibooks:
https://ru.wikibooks.org/wiki/... ка/Быстрая
https://en.wikibooks.org/wiki/... /Quicksort
На английской страничке приводится и итеративная версия алгоритма.

За основу для реализации на ассемблере возьму вариант из русской странички Wikibooks:

Работает для произвольного массива из n целых чисел.

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int n, a[n]; //n - количество элементов
void qs(int *s_arr, int first, int last)
{
    if (first < last)
    {
        int left = first, right = last, middle = s_arr[(left + right) / 2];
        do
        {
            while (s_arr[left] < middle) left++;
            while (s_arr[right] > middle) right--;
            if (left <= right)
            {
                int tmp = s_arr[left];
                s_arr[left] = s_arr[right];
                s_arr[right] = tmp;
                left++;
                right--;
            }
        } while (left <= right);
        qs(s_arr, first, right);
        qs(s_arr, left, last);
    }
}

Исходный вызов функции qs для массива из n элементов будет иметь следующий вид:

C
1
qs(a, 0, n-1);

Т.к. это учебная программа, то при её реализации не было задачи получить максимальную производительность. Поэтому не удивлюсь если узнаю, что "пузырёк" сортирует быстрее.

Сделаю пояснения по реализации.
1. По моим представлениям, названия переменных, функций и меток не могут быть столь коротки, что не вызывают правильных ассоциаций. Поэтому название функции qs при реализации заменил на QSort.
2. Т.к. для функции обработки всего массива привычнее передавать процедуре адрес и длину этого массива, то вместо вызова QSort из основной программы, вызывается процедура-обёртка QuickSort. А уже внутри QuickSort вызывается QSort c правильно cформированными параметрами.
3. При вычислении индекса середины диапазона (left + right) / 2 в поучительно-выпендрёжных целях (исключения переполнения при суммировании) использовал преобразованную формулу left + ((right - left) / 2)
4. Это реализация быстрой сортировки в общем виде (не разбиение Ломуто, не разбиение Хоара).
5. Опорный элемент выбирается как средний элемент подмассива. При решении задач с сайтов с "электронным судьёй" иногда встречаются специально подобранные последовательности, на которых быстрая сортировка с опорным элементом из середины фактически останавливает выполнение программы, и реальным выходом является выбор опорного элемента как элемента массива со случайным индексом из сортируемого диапазона.

Assembler
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
;Сортировка массива слов (word)
;Процедура-обёртка над процедурой QSort
;на входе:
;cx - количество элементов в массиве
;ds:dx - адрес массива слов
;на выходе:
;  неизменны все регистры
;  отсортированный массив
QuickSort       proc
        push    ax
        push    bx
        push    cx
        push    dx
        push    si
        push    di
        ;QSort(A, 0, N-1)
        mov     bx,     dx
        mov     si,     0
        mov     di,     cx
        dec     di
        shl     di,     1
        call    QSort
 
        pop     di
        pop     si
        pop     dx
        pop     cx
        pop     bx
        pop     ax
        ret
QuickSort       endp
 
;Быстрая сортировка
;на входе:
;  ds:bx - адрес массива
;  si    - адрес левой границы массива
;  di    - адрес правой границы массива
QSort   proc                    ;void QSort(int *a, int first, int last)
        push    ax              ;{
        push    bx
        push    cx
        push    dx
        push    si
        push    di
 
        cmp     si,     di      ;  if (first < last)
        jae     @@StopQSort     ;  {
        push    di
        push    si
        ;mov si, si             ;        int left = first,
        ;mov di, di             ;        int right = last,
        mov     dx,     di      ;        int middle = a[(left + right) / 2];
        mov     cx,     si
        shr     si,     1
        shr     di,     1
        sub     di,     si
        shr     di,     1
        add     si,     di
        shl     si,     1
        mov     ax,     [bx+si]
        mov     si,     cx
        mov     di,     dx
        @@DoWhile:              ;        do
                                ;        {
                                ;             while (a[left] < middle) left++;
                sub     si,     2
                @@WhileLeft:
                        add     si,     2
                        mov     cx,     [bx+si]
                        cmp     ax,     [bx+si]
                jg      @@WhileLeft
                                ;             while (a[right] > middle) right--;
                add     di,     2
                @@WhileRight:
                        sub     di,     2
                        mov     cx,     [bx+di]
                        cmp     ax,     [bx+di]
                jl      @@WhileRight
                                ;             if (left <= right)
                cmp     si,     di
                ja      @@BreakDoWhile
                                ;             {
                                ;                int tmp = a[left];
                                ;                a[left] = a[right];
                                ;                a[right] = tmp;
                mov     cx,     [bx+si]
                mov     dx,     [bx+di]
                mov     [bx+si],dx
                mov     [bx+di],cx
                                ;                left++;
                add     si,     2
                                ;                right--;
                sub     di,     2
                                ;            }
                                ;        } while (left <= right);
                cmp     si,     di
        jbe     @@DoWhile
        @@BreakDoWhile:
                                ;        QSort(a, first, right);
        mov     cx,     si
        pop     si
        call    QSort
                                ;        QSort(a, left, last);
        mov     si,     cx
        pop     di
        call    QSort
                                ;    }
                                ;  }
@@StopQSort:
        pop     di
        pop     si
        pop     dx
        pop     cx
        pop     bx
        pop     ax
        ret
QSort   endp                    ;}

Пример вызова из программы для сортировки массива Array из N элементов

Assembler
1
2
3
4
        ;сортировка массива
        mov     cx,     [N]
        lea     dx,     [Array]
        call    QuickSort

Пример полной программы по ссылке
Написать код реализации быстрой сортировки

@Jin X · 11.11.2017, 13:28

Умная быстрая сортировка

Заморочился и сделал не просто быструю сортировку, но ещё и умную

Алгоритм работы умной сортировки заключается в следующем.
По умолчанию используется быстрая сортировка, однако если кол-во элементов массива на первой или последующей итерации меньше некоего порогового значения (по умолчанию 16), либо если для следующего уровня рекурсии в общей сложности потребуется слишком много стека (по умолчанию 128 байт), используется сортировка вставками, в которой рекурсия отсутствует. Это немного ускоряет процесс (мои замеры показывают прирост до 10% для случайных данных) и защищает стек от переполнения.

Иногда при сортировке массивов необходимо упорядочить не только числовые элементы, но и соответствующие им данные. Например, имеется список людей с указанием года рождения и фамилии для каждого из них. Год рождения записан в виде числового значения, а фамилия – в виде указателя на строку. Таким образом, каждый элемент массива будет содержать 2 записи размером WORD каждая:
+0 WORD Год рождения
+2 WORD Адрес (смещение) строки с фамилией
При сортировке такого массива необходимо сравнивать только первые элементы (опорные значения), однако перемещать (менять местами) и первые, и вторые.
Если массив должен содержать более 2-х элементов, все элементы, кроме опорного (например, фамилию, имя, адрес и телефон) необходимо записать в отдельную область памяти, а во втором поле указать ссылку на эту структуру (которая не ограничена в размере и может также содержать ссылки на каждый из элементов).
К сожалению, данная реализация модулей не позволяет работать с 32-битными данными (включая дальние указатели), однако опытный программист без труда сможет внести требуемые изменения при необходимости

Мои процедуры позволяют выполнить как сортировку одиночных (числовых) элементов, так и двойных (числовых элементов с привязанными данными).
Некоторые файлы прикреплённого архива содержат универсальные процедуры (размер данных, знаковость числовых значений и направление сортировки, а также другие параметры задаются в исходнике программы перед подключением файла), другие – с заданными параметрами, некоторые из которых можно менять, изменяя сам исходник.

Процедура быстрой сортировки оптимизирована таким образом, что каждый последующий уровень рекурсии не требует записи в стек адреса возврата (поскольку рекурсивный вызов происходит из одной и той же точки в процедуре), в стек записываются лишь локальные данные, минимально необходимые для последующей работы (2 слово = 4 байта).
Это довольно весомый плюс в сравнении с предыдущим примером, в котором каждая рекурсия сохраняет в стек все модифицируемые регистры (на первой итерации это делается дважды) и требует аж 7-8 слов (14-16 байт) для каждого уровня рекурсии!

Модуль умной быстрой сортировки для массивов с одиночными элементами IQSortS1.inc:

Assembler
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
;##################################################
;##                                              ##
;##        [ Asm7x.List ][ IQSortS1.inc ]        ##
;##                                              ##
;##            -= Smart Quick Sort =-            ##
;##         (for single element arrays)          ##
;##                                              ##
;##           Умная быстрая сортировка           ##
;##    (для массивов с одиночными элементами)    ##
;##                                              ##
;##           [ v1.00 :: 11.11.2017 ]            ##
;##              MASM/TASM (16 bit)              ##
;##                                              ##
;##     (c) 2017 by Jin X (jin.x@sources.ru)     ##
;##             http://xk7.ru/p/a/i              ##
;##                                              ##
;##################################################
 
IFDEF           ??Version       ; TASM
  LOCALS
ENDIF
 
IQSortS1_ver    =       100h                    ; версия данного модуля (word: старший байт - целая часть, младший - дробная)
 
; !!! В данном модуле используется ЗНАКОВОЕ сравнение значений и сортировка по ВОЗРАСТАНИЮ (от меньшего к большему)
; !!! Для замены на БЕЗзнаковое сравнение или сортировку по УБЫВАНИЮ необходимо изменить соответствующие инструкции, помеченные в комментариях символами ***
 
; IQSortInsThrs = порог использования сортировки вставками (когда кол-во элементов меньше указанного здесь значения) [минимум 2; по умолчанию 16]
;   Если кол-во элементов (на первой или последующей итерации) больше или равно значению IQSortInsThrs, используется быстрая сортировка, иначе
;   используется сортировка вставками - это немного ускоряет процесс (при правильном выборе значения IQSortInsThrs, например, при значении по умолчанию)
;   и уменьшает глубину рекурсии, защищая стек от переполнения
IQSortInsThrs   =       16
 
; IQSortMaxStk = максимальный размер стека в байтах, который допустимо использовать процедуре IQSort (включая call из основного кода) [минимум 10; по умолчанию 128]
;   Каждый уровень вложенности использует 4 байта (2 слова) стека (первый уровень - до 4-х слов, последний может использовать на 1 слово больше, итого минимум 10 байт),
;   т.о. 128 байт позволяют организовать до 30 уровней рекурсии, что достаточно даже для очень больших массивов
IQSortMaxStk    =       128
 
;-----------------------------------------------------------------------------------------------------------------------
 
;-- IQSort: Умная БЫСТРАЯ СОРТИРОВКА массива (комбинированным методом) -------------------------------------------------
; > Входные данные: DS:DX = адрес массива, CX = кол-во элементов массива (знаковое значение)
; > Результат: отсортированный массив (по тому же адресу)
; Элементы массива содержат по 1 значению типа WORD, по которому происходит сравнение и сортировка
; Если кол-во элементов (на первой или последующей итерации) больше или равно значению IQSortInsThrs, используется быстрая сортировка,
;   иначе используется сортировка вставками
; Сортировка вставками также используется, если для следующего уровня рекурсии потребуется более IQSortMaxStk байт стека в общем сложности
; Процедура изменяет регистры AX, BX, CX, DX, SI, DI, сохраняет BP и сегментные регистры
IQSort          PROC
                dec     cx
                jle     @@exit                  ; выходим, если кол-во элементов <= 1
 
                push    bp
                xor     bp,bp                   ; BP = кол-во рекурсий
                shl     cx,1
                add     cx,dx                   ; CX = адрес последнего элемента
 
                ; Главная процедура быстрой сортировки
                ; DX = адрес первого элемента, CX = адрес последнего элемента, CX > DX, BP = уровень рекурсии
        @@IQSortMain:
                mov     ax,cx
                sub     ax,dx
                shr     ax,1                    ; AX = кол-во элементов минус 1
                cmp     ax,IQSortInsThrs-1
                jb      @@callins               ; если кол-во элементов меньше порогового значения, используем сортировку вставками
 
                mov     si,dx                   ;; I (SI) := L (DX)
        @@repeat1:                              ;; repeat
                mov     di,cx                   ;; J (DI) := R (CX)
                mov     bx,cx
                sub     bx,dx
                shr     bx,1
                and     bx,-2
                add     bx,dx                   ;; P (BX) := (L + R) / 2
                mov     ax,[bx]                 ;; T (AX) := [P]
        @@repeat2 = @@cmpI                      ;; repeat
                ; SI = I, AX = T, DI = J, DX = L, CX = R
                jmp     @@cmpI
        @@addI: add     si,2                    ;; Inc(I)
        @@cmpI: cmp     [si],ax                 ;; while [I] < T
                jl      @@addI                  ; {*** сортировка по возрастанию: jl - знаковое сравнение, jb - беззнаковое; по убыванию: jg - знаковое, ja - беззнаковое}
 
                jmp     @@cmpJ
        @@subJ: sub     di,2                    ;; Dec(J)
        @@cmpJ: cmp     [di],ax                 ;; while [J] > T
                jg      @@subJ                  ; {*** сортировка по возрастанию: jg - знаковое сравнение, ja - беззнаковое; по убыванию: jl - знаковое, jb - беззнаковое}
 
                cmp     si,di
                jnbe    @@noswap                ;; if I <= J then
 
                mov     bx,[si]                 ;;   Swap [I],[J]
                xchg    [di],bx
                mov     [si],bx
 
                add     si,2                    ;; Inc(I)
                sub     di,2                    ;; Dec(J)
        @@noswap:
                cmp     si,di
                jna     @@repeat2               ;; until I > J
 
                cmp     dx,di
                jnb     @@norecurs              ;; if L < J then
 
                push    cx
                push    si                      ; сохраняем R и I
                mov     cx,di
                ; DX = L, CX = J
                cmp     bp,(IQSortMaxStk-10)/4  ; 5 слов - это адрес возврата в вызываемую программу + bp + cx + si + адрес возврата из InsSort
                jae     @@callins2              ; если число рекурсий достигло максимума, идём на вызов сортировки вставками: InsSort(L, J)
                inc     bp                      ; иначе увеличиваем глубину рекурсии и идём на рекурсию
                jmp     @@IQSortMain            ;;   IQSort(L, J); вызов делаем через jmp для экономии стека :)
        @@recursret:
                pop     si
                pop     cx                      ; восстанавливаем I и R
        @@norecurs:
                mov     dx,si                   ;; L := I
                cmp     si,cx
                jnae    @@repeat1               ;; until I >= R
        @@finish:
                dec     bp                      ; уменьшаем глубину рекурсии
                jns     @@recursret             ; прыгаем, если это не первый (корневой) уровень рекурсии
                pop     bp
        @@exit: ret
 
        @@callins:
                push    offset @@finish         ; адрес возврата
                jmp     @IQInsSort              ; вместо call + jmp @@finish делаем push + jmp
        @@callins2:
                push    offset @@recursret      ; адрес возврата
                jmp     @IQInsSort              ; вместо call + jmp @@recursret делаем push + jmp
IQSort          ENDP
 
;-- InsSort: СОРТИРОВКА массива ВСТАВКАМИ ------------------------------------------------------------------------------
; > Входные данные: DS:DX = адрес массива, CX = кол-во элементов массива (знаковое значение)
; > Результат: отсортированный массив (по тому же адресу)
; Элементы массива содержат по 1 значению типа WORD, по которому происходит сравнение и сортировка
; Процедура изменяет регистры AX, BX, SI, DI, сохраняет CX, DX, BP и сегментные регистры
InsSort         PROC
                dec     cx
                jle     @@exit                  ; выходим, если кол-во элементов <= 1
 
                shl     cx,1
                add     cx,dx                   ; CX = адрес последнего элемента
 
                ; Главная процедура сортировки вставками
                ; DX = адрес первого элемента, CX = адрес последнего элемента, CX > DX
IFDEF           ??Version       ; TASM
  @IQInsSort:
ELSE                            ; MASM
  @IQInsSort::
ENDIF
                mov     di,dx                   ; J (DI) := L - адрес первого элемента
        @@next:                                 ;; for J (DI) := L+1 (CX) to R (DX) do
                add     di,2                    ; J++ (DI) - адрес следующего проверяемого элемента (в основном цикле)
                mov     bx,[di]                 ;; T (BX) := [J]
                mov     si,di                   ; I+1 (SI) := DI - адрес элемента, следующего за сравниваемым (во внутреннем цикле)
        @@loop:                                 ;; repeat
                mov     ax,[si-2]
                cmp     ax,bx                   ;; if [I] > T then
                jle     @@break                 ; прыгаем, если [I] <= T {*** сортировка по возрастанию: jle - знаковое сравнение, jbe - беззнаковое; по убыванию: jge - знаковое, jae - беззнаковое}
 
                mov     [si],ax                 ;;  [I+1] := [I] else Break
 
                sub     si,2                    ;; Dec(I)
                cmp     si,dx
                jnbe    @@loop                  ;; until I < L (I+1 <= L)
        @@break:
                mov     [si],bx                 ;; [I+1] := T
 
                cmp     di,cx
                jnae    @@next                  ; следующий элемент массива ;; end for
        @@exit: ret
InsSort         ENDP

Вызов:

Assembler
1
2
3
                lea     dx,Array                ; DS:DX = адрес массива
                mov     cx,Count                ; CX = кол-во элементов массива
                call    IQSort                  ; вызов процедуры умной быстрой сортировки

Всё остальное (сортировку массивов с двойными элементами, универсальные модули, отдельные процедуры обычной быстрой сортировки и сортировки вставками, а также примеры использования) – см. в архиве

@Jin X · 11.11.2017, 13:32

Решил всё же добавить в виде сообщений тексты исходников ещё некоторых (но не всех) модулей (к сожалению, в одной сообщение они не помещаются):

Модуль умной быстрой сортировки для массивов с двойными элементами IQSortS2.inc:

Assembler
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
;##################################################
;##                                              ##
;##        [ Asm7x.List ][ IQSortS2.inc ]        ##
;##                                              ##
;##            -= Smart Quick Sort =-            ##
;##         (for double element arrays)          ##
;##                                              ##
;##           Умная быстрая сортировка           ##
;##     (для массивов с двойными элементами)     ##
;##                                              ##
;##           [ v1.00 :: 11.11.2017 ]            ##
;##              MASM/TASM (16 bit)              ##
;##                                              ##
;##     (c) 2017 by Jin X (jin.x@sources.ru)     ##
;##             http://xk7.ru/p/a/i              ##
;##                                              ##
;##################################################
 
IFDEF           ??Version       ; TASM
  LOCALS
ENDIF
 
IQSortS2_ver    =       100h                    ; версия данного модуля (word: старший байт - целая часть, младший - дробная)
 
; !!! В данном модуле используется ЗНАКОВОЕ сравнение значений и сортировка по ВОЗРАСТАНИЮ (от меньшего к большему)
; !!! Для замены на БЕЗзнаковое сравнение или сортировку по УБЫВАНИЮ необходимо изменить соответствующие инструкции, помеченные в комментариях символами ***
 
; IQSortInsThrs = порог использования сортировки вставками (когда кол-во элементов меньше указанного здесь значения) [минимум 2; по умолчанию 16]
;   Если кол-во элементов (на первой или последующей итерации) больше или равно значению IQSortInsThrs, используется быстрая сортировка, иначе
;   используется сортировка вставками - это немного ускоряет процесс (при правильном выборе значения IQSortInsThrs, например, при значении по умолчанию)
;   и уменьшает глубину рекурсии, защищая стек от переполнения
IQSortInsThrs   =       16
 
; IQSortMaxStk = максимальный размер стека в байтах, который допустимо использовать процедуре IQSort (включая call из основного кода) [минимум 12; по умолчанию 128]
;   Каждый уровень вложенности использует 4 байта (2 слова) стека (первый уровень - до 4-х слов, последний может использовать на 2 слова больше, итого минимум 12 байт),
;   т.о. 128 байт позволяют организовать до 30 уровней рекурсии, что достаточно даже для очень больших массивов
IQSortMaxStk    =       128
 
;-----------------------------------------------------------------------------------------------------------------------
 
;-- IQSortDE: Умная БЫСТРАЯ СОРТИРОВКА массива (комбинированным методом) -----------------------------------------------
; > Входные данные: DS:DX = адрес массива, CX = кол-во элементов массива (знаковое значение)
; > Результат: отсортированный массив (по тому же адресу)
; Элементы массива содержат по 2 значения типа WORD:
;   * первое слово содержит опорное значение (по которому происходит сравнение),
;   * второе слово - связанные с элементом данные (обычно это указатель на данные);
;     при сортировке связанные данные переносятся вместе с опорными значениями
; Если кол-во элементов (на первой или последующей итерации) больше или равно значению IQSortInsThrs, используется быстрая сортировка,
;   иначе используется сортировка вставками
; Сортировка вставками также используется, если для следующего уровня рекурсии потребуется более IQSortMaxStk байт стека в общем сложности
; Процедура изменяет регистры AX, BX, CX, DX, SI, DI, сохраняет BP и сегментные регистры
IQSortDE        PROC
                dec     cx
                jle     @@exit                  ; выходим, если кол-во элементов <= 1
 
                push    bp
                xor     bp,bp                   ; BP = кол-во рекурсий
                shl     cx,2
                add     cx,dx                   ; CX = адрес последнего элемента
 
                ; Главная процедура быстрой сортировки
                ; DX = адрес первого элемента, CX = адрес последнего элемента, CX > DX, BP = уровень рекурсии
        @@IQSortMain:
                mov     ax,cx
                sub     ax,dx
                shr     ax,2                    ; AX = кол-во элементов минус 1
                cmp     ax,IQSortInsThrs-1
                jb      @@callins               ; если кол-во элементов меньше порогового значения, используем сортировку вставками
 
                mov     si,dx                   ;; I (SI) := L (DX)
        @@repeat1:                              ;; repeat
                mov     di,cx                   ;; J (DI) := R (CX)
                mov     bx,cx
                sub     bx,dx
                shr     bx,1
                and     bx,-4
                add     bx,dx                   ;; P (BX) := (L + R) / 2
                mov     ax,[bx]                 ;; T (AX) := [P]
        @@repeat2 = @@cmpI                      ;; repeat
                ; SI = I, AX = T, DI = J, DX = L, CX = R
                jmp     @@cmpI
        @@addI: add     si,4                    ;; Inc(I)
        @@cmpI: cmp     [si],ax                 ;; while [I] < T
                jl      @@addI                  ; {*** сортировка по возрастанию: jl - знаковое сравнение, jb - беззнаковое; по убыванию: jg - знаковое, ja - беззнаковое}
 
                jmp     @@cmpJ
        @@subJ: sub     di,4                    ;; Dec(J)
        @@cmpJ: cmp     [di],ax                 ;; while [J] > T
                jg      @@subJ                  ; {*** сортировка по возрастанию: jg - знаковое сравнение, ja - беззнаковое; по убыванию: jl - знаковое, jb - беззнаковое}
 
                cmp     si,di
                jnbe    @@noswap                ;; if I <= J then
 
                mov     bx,[si]                 ;;   Swap [I],[J]
                xchg    [di],bx
                mov     [si],bx
                mov     bx,[si+2]
                xchg    [di+2],bx
                mov     [si+2],bx
 
                add     si,4                    ;; Inc(I)
                sub     di,4                    ;; Dec(J)
        @@noswap:
                cmp     si,di
                jna     @@repeat2               ;; until I > J
 
                cmp     dx,di
                jnb     @@norecurs              ;; if L < J then
 
                push    cx
                push    si                      ; сохраняем R и I
                mov     cx,di
                ; DX = L, CX = J
                cmp     bp,(IQSortMaxStk-12)/4  ; 6 слов - это адрес возврата в вызываемую программу + bp + cx + si + адрес возврата из InsSort + bp
                jae     @@callins2              ; если число рекурсий достигло максимума, идём на вызов сортировки вставками: InsSort(L, J)
                inc     bp                      ; иначе увеличиваем глубину рекурсии и идём на рекурсию
                jmp     @@IQSortMain            ;;   IQSort(L, J); вызов делаем через jmp для экономии стека :)
        @@recursret:
                pop     si
                pop     cx                      ; восстанавливаем I и R
        @@norecurs:
                mov     dx,si                   ;; L := I
                cmp     si,cx
                jnae    @@repeat1               ;; until I >= R
        @@finish:
                dec     bp                      ; уменьшаем глубину рекурсии
                jns     @@recursret             ; прыгаем, если это не первый (корневой) уровень рекурсии
                pop     bp
        @@exit: ret
 
        @@callins:
                push    offset @@finish         ; адрес возврата
                jmp     @IQInsSort              ; вместо call + jmp @@finish делаем push + jmp
        @@callins2:
                push    offset @@recursret      ; адрес возврата
                jmp     @IQInsSort              ; вместо call + jmp @@recursret делаем push + jmp
IQSortDE        ENDP
 
;-- InsSortDE: СОРТИРОВКА массива ВСТАВКАМИ ----------------------------------------------------------------------------
; > Входные данные: DS:DX = адрес массива, CX = кол-во элементов массива (знаковое значение)
; > Результат: отсортированный массив (по тому же адресу)
; Элементы массива содержат по 2 значения типа WORD:
;   * первое слово содержит опорное значение (по которому происходит сравнение),
;   * второе слово - связанные с элементом данные (обычно это указатель на данные);
;     при сортировке связанные данные переносятся вместе с опорными значениями
; Процедура изменяет регистры AX, BX, SI, DI, сохраняет CX, DX, BP и сегментные регистры
InsSortDE       PROC
                dec     cx
                jle     @@exit                  ; выходим, если кол-во элементов <= 1
 
                shl     cx,2
                add     cx,dx                   ; CX = адрес последнего элемента
 
                ; Главная процедура сортировки вставками
                ; DX = адрес первого элемента, CX = адрес последнего элемента, CX > DX
IFDEF           ??Version       ; TASM
  @IQInsSort:
ELSE                            ; MASM
  @IQInsSort::
ENDIF
                push    bp
                mov     di,dx                   ; J (DI) := L - адрес первого элемента
        @@next:                                 ;; for J (DI) := L+1 (CX) to R (DX) do
                add     di,4                    ; J++ (DI) - адрес следующего проверяемого элемента (в основном цикле)
                mov     bx,[di]                 ;; T (BP:BX) := [J]
                mov     bp,[di+2]
                mov     si,di                   ; I+1 (SI) = DI - адрес элемента, следующего за сравниваемым (во внутреннем цикле)
        @@loop:                                 ;; repeat
                mov     ax,[si-4]
                cmp     ax,bx                   ;; if [I] > T then
                jle     @@break                 ; прыгаем, если [I] <= T {*** сортировка по возрастанию: jle - знаковое сравнение, jbe - беззнаковое; по убыванию: jge - знаковое, jae - беззнаковое}
 
                mov     [si],ax                 ;;  [I+1] := [I] else Break
                mov     ax,[si-4+2]
                mov     [si+2],ax
 
                sub     si,4                    ;; Dec(I)
                cmp     si,dx
                jnbe    @@loop                  ;; until I < L (I+1 <= L)
        @@break:
                mov     [si],bx                 ;; [I+1] := T
                mov     [si+2],bp
 
                cmp     di,cx
                jnae    @@next                  ; следующий элемент массива ;; end for
 
                pop     bp
        @@exit: ret
InsSortDE       ENDP

@Jin X · 11.11.2017, 15:21

Модуль обычной быстрой сортировки для массивов с одиночными элементами QSortS1.inc:

Assembler
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
;##################################################
;##                                              ##
;##        [ Asm7x.List ][ QSortS1.inc ]         ##
;##                                              ##
;##               -= Quick Sort =-               ##
;##         (for single element arrays)          ##
;##                                              ##
;##              Быстрая сортировка              ##
;##    (для массивов с одиночными элементами)    ##
;##                                              ##
;##           [ v1.00 :: 11.11.2017 ]            ##
;##              MASM/TASM (16 bit)              ##
;##                                              ##
;##     (c) 2017 by Jin X (jin.x@sources.ru)     ##
;##             http://xk7.ru/p/a/i              ##
;##                                              ##
;##################################################
 
IFDEF           ??Version       ; TASM
  LOCALS
ENDIF
 
QSortS1_ver     =       100h                    ; версия данного модуля (word: старший байт - целая часть, младший - дробная)
 
; !!! В данном модуле используется ЗНАКОВОЕ сравнение значений и сортировка по ВОЗРАСТАНИЮ (от меньшего к большему)
; !!! Для замены на БЕЗзнаковое сравнение или сортировку по УБЫВАНИЮ необходимо изменить соответствующие инструкции, помеченные в комментариях символами ***
 
;-----------------------------------------------------------------------------------------------------------------------
 
;-- QSort: БЫСТРАЯ СОРТИРОВКА массива ----------------------------------------------------------------------------------
; > Входные данные: DS:DX = адрес массива, CX = кол-во элементов массива (знаковое значение)
; > Результат: отсортированный массив (по тому же адресу)
; Элементы массива содержат по 1 значению типа WORD, по которому происходит сравнение и сортировка
; Процедура изменяет регистры AX, BX, CX, DX, SI, DI, сохраняет BP и сегментные регистры
QSort           PROC
                dec     cx
                jle     @@exit                  ; выходим, если кол-во элементов <= 1
 
                push    bp
                xor     bp,bp                   ; BP = кол-во рекурсий
                shl     cx,1
                add     cx,dx                   ; CX = адрес последнего элемента
 
                ; Главная процедура быстрой сортировки
                ; DX = адрес первого элемента, CX = адрес последнего элемента, CX > DX, BP = уровень рекурсии
        @@QSortMain:
                mov     si,dx                   ;; I (SI) := L (DX)
        @@repeat1:                              ;; repeat
                mov     di,cx                   ;; J (DI) := R (CX)
                mov     bx,cx
                sub     bx,dx
                shr     bx,1
                and     bx,-2
                add     bx,dx                   ;; P (BX) := (L + R) / 2
                mov     ax,[bx]                 ;; T (AX) := [P]
        @@repeat2 = @@cmpI                      ;; repeat
                ; SI = I, AX = T, DI = J, DX = L, CX = R
                jmp     @@cmpI
        @@addI: add     si,2                    ;; Inc(I)
        @@cmpI: cmp     [si],ax                 ;; while [I] < T
                jl      @@addI                  ; {*** сортировка по возрастанию: jl - знаковое сравнение, jb - беззнаковое; по убыванию: jg - знаковое, ja - беззнаковое}
 
                jmp     @@cmpJ
        @@subJ: sub     di,2                    ;; Dec(J)
        @@cmpJ: cmp     [di],ax                 ;; while [J] > T
                jg      @@subJ                  ; {*** сортировка по возрастанию: jg - знаковое сравнение, ja - беззнаковое; по убыванию: jl - знаковое, jb - беззнаковое}
 
                cmp     si,di
                jnbe    @@noswap                ;; if I <= J then
 
                mov     bx,[si]                 ;;   Swap [I],[J]
                xchg    [di],bx
                mov     [si],bx
 
                add     si,2                    ;; Inc(I)
                sub     di,2                    ;; Dec(J)
        @@noswap:
                cmp     si,di
                jna     @@repeat2               ;; until I > J
 
                cmp     dx,di
                jnb     @@norecurs              ;; if L < J then
 
                push    cx
                push    si                      ; сохраняем R и I
                mov     cx,di
                ; DX = L, CX = J
                inc     bp                      ; увеличиваем глубину рекурсии и идём на рекурсию
                jmp     @@QSortMain             ;;   QSort(L, J); вызов делаем через jmp для экономии стека :)
        @@recursret:
                pop     si
                pop     cx                      ; восстанавливаем I и R
        @@norecurs:
                mov     dx,si                   ;; L := I
                cmp     si,cx
                jnae    @@repeat1               ;; until I >= R
        @@finish:
                dec     bp                      ; уменьшаем глубину рекурсии
                jns     @@recursret             ; прыгаем, если это не первый (корневой) уровень рекурсии
                pop     bp
        @@exit: ret
QSort           ENDP

Модуль сортировки вставками для массивов с одиночными элементами ISortS1.inc:

Assembler
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
;##################################################
;##                                              ##
;##        [ Asm7x.List ][ ISortS1.inc ]         ##
;##                                              ##
;##             -= Insertion Sort =-             ##
;##         (for single element arrays)          ##
;##                                              ##
;##             Сортировка вставками             ##
;##    (для массивов с одиночными элементами)    ##
;##                                              ##
;##           [ v1.00 :: 11.11.2017 ]            ##
;##              MASM/TASM (16 bit)              ##
;##                                              ##
;##     (c) 2017 by Jin X (jin.x@sources.ru)     ##
;##             http://xk7.ru/p/a/i              ##
;##                                              ##
;##################################################
 
IFDEF           ??Version       ; TASM
  LOCALS
ENDIF
 
ISortS1_ver     =       100h                    ; версия данного модуля (word: старший байт - целая часть, младший - дробная)
 
; !!! В данном модуле используется ЗНАКОВОЕ сравнение значений и сортировка по ВОЗРАСТАНИЮ (от меньшего к большему)
; !!! Для замены на БЕЗзнаковое сравнение или сортировку по УБЫВАНИЮ необходимо изменить соответствующие инструкции, помеченные в комментариях символами ***
 
;-----------------------------------------------------------------------------------------------------------------------
 
;-- InsSort: СОРТИРОВКА массива ВСТАВКАМИ ------------------------------------------------------------------------------
; > Входные данные: DS:DX = адрес массива, CX = кол-во элементов массива (знаковое значение)
; > Результат: отсортированный массив (по тому же адресу)
; Элементы массива содержат по 1 значению типа WORD, по которому происходит сравнение и сортировка
; Процедура изменяет регистры AX, BX, SI, DI, сохраняет CX, DX, BP и сегментные регистры
InsSort         PROC
                dec     cx
                jle     @@exit                  ; выходим, если кол-во элементов <= 1
 
                shl     cx,1
                add     cx,dx                   ; CX = адрес последнего элемента
 
                ; Главная процедура сортировки вставками
                ; DX = адрес первого элемента, CX = адрес последнего элемента, CX > DX
                mov     di,dx                   ; J (DI) := L - адрес первого элемента
        @@next:                                 ;; for J (DI) := L+1 (CX) to R (DX) do
                add     di,2                    ; J++ (DI) - адрес следующего проверяемого элемента (в основном цикле)
                mov     bx,[di]                 ;; T (BX) := [J]
                mov     si,di                   ; I+1 (SI) := DI - адрес элемента, следующего за сравниваемым (во внутреннем цикле)
        @@loop:                                 ;; repeat
                mov     ax,[si-2]
                cmp     ax,bx                   ;; if [I] > T then
                jle     @@break                 ; прыгаем, если [I] <= T {*** сортировка по возрастанию: jle - знаковое сравнение, jbe - беззнаковое; по убыванию: jge - знаковое, jae - беззнаковое}
 
                mov     [si],ax                 ;;  [I+1] := [I] else Break
 
                sub     si,2                    ;; Dec(I)
                cmp     si,dx
                jnbe    @@loop                  ;; until I < L (I+1 <= L)
        @@break:
                mov     [si],bx                 ;; [I+1] := T
 
                cmp     di,cx
                jnae    @@next                  ; следующий элемент массива ;; end for
        @@exit: ret
InsSort         ENDP

asm7x

Добавлено через 1 час 43 минуты
Добавлю, что несмотря на большую популярность пузырьковой сортировки, сортировка вставками работает значительно быстрее на случайных данных, при этом её алгоритм ничуть не сложнее, а в чём-то даже и проще (мои тесты показали двойную разницу в скорости... правда, тестировал я в DOSBox, но и на реальной машине перевес будет в пользу сортировки вставками).

@Jin X · 11.11.2017, 22:16

Умная быстрая сортировка 32-битных элементов

Сделана ещё одна коллекция модулей сортировки. Полная копия описанных выше, но работающая с 32-битными элементами!

Теперь вы можете использовать дальние указатели во втором двойном слове, либо 2 ближних указателя, а также 32-битные элементы в первом (опорном) двойном слове (в котором можно расположить, например, дату рождения).
Например:

Code
1
2
3
4
5
+0  BYTE  День рождения
+1  BYTE  Месяц рождения
+2  WORD  Год рождения
+4  WORD  Ближний указатель на имя
+6  WORD  Ближний указатель на фамилию

Сортировка будет идти по дате рождения, а указатели на строку с фамилией и именем будут переноситься вместе с датой. Правда, здорово?

Если 4-х байтов для опорных значений (т.е. значений, которые будут сравниваться и на основе которых будет происходить сортировка) слишком много, можно использовать 2 старших (WORD), а младшие 2 заполнить нулями (если сделать наоборот, то знаковое сравнение работать не будет).

Прикрепляю архив с модулями для работы как с 16-битными данными (поскольку в них я внёс некоторые несущественные изменения, касающиеся по большей части комментариев и названий внутренних меток), так и с 32-битными.

Пользуйтесь!

asm7x

@Jin X · 11.11.2017, 22:18

К сожалению, ограничение размера сообщения в 15 Кб снова не позволило мне прикрепить исходник модуля (не хватило нескольких сотен байт), поэтому делаю это в отдельном сообщении.

На этот раз я приведу лишь один исходный код – универсального модуля IQSort4.inc, модуля умной быстрой сортировки расширенных (32-битных) элементов:

Assembler
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
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
;##################################################
;##                                              ##
;##        [ Asm7x.List ][ IQSort4.inc ]         ##
;##                                              ##
;##          UNIVERSAL UNIT FOR 16 BIT           ##
;##       УНИВЕРСАЛЬНЫЙ МОДУЛЬ ДЛЯ 16 БИТ        ##
;##                                              ##
;##            -= Smart Quick Sort =-            ##
;##        (for extended elenemt arrays)         ##
;##                                              ##
;##           Умная быстрая сортировка           ##
;##   (для массивов с расширенными элементами)   ##
;##                                              ##
;##           [ v1.00 :: 11.11.2017 ]            ##
;##           MASM/TASM (16 bit 386+)            ##
;##                                              ##
;##     (c) 2017 by Jin X (jin.x@sources.ru)     ##
;##             http://xk7.ru/p/a/i              ##
;##                                              ##
;##################################################
 
IFDEF           ??Version       ; TASM
  LOCALS
ENDIF
 
IQSort4_ver     =       100h                    ; версия данного модуля (word: старший байт - целая часть, младший - дробная)
 
; ПЕРЕД ВКЛЮЧЕНИЕМ ДАННОГО ФАЙЛА В ПРОЕКТ *МОЖНО* ОПРЕДЕЛИТЬ СЛЕДУЮЩИЕ СИМВОЛЫ:
 
; inclIQSort4 = 1 - включить процедуру IQSort4 (умная быстрая сортировка) в код, 0 - не включать [по умолчанию 1]
 
; inclInsSort4 = 1 - включить процедуру InsSort4 (сортировка вставками) в код, 0 - не включать [по умолчанию 0]
;   Если процедура InsSort4 используется процедурой IQSort4, в код включается лишь часть этой процедуры, необходимая для работы IQSort4
 
; Sort4SignCmp = 1 - знаковое сравнение, 0 - беззнаковое [по умолчанию 1]
 
; Sort4Ascending = 1 - сортировка по возрастанию (от меньшего к большему), 0 - по убыванию (от больего к меньшему)
 
; Sort4ElemDWords = кол-во двойных слов с данными (допускаются значения: 1 - только опорное слово, 2 - опорное слово и связанные данные; другие значения породят ошибки)
;   [*ЭТОТ СИМВОЛ НЕОБХОДИМО ОПРЕДЕЛИТЬ ОБЯЗАТЕЛЬНО*, значения по умолчанию для него нет!!!]
 
; IQSort4InsThrs = порог использования сортировки вставками (когда кол-во элементов меньше указанного здесь значения) [0 = отключено; минимум 2; по умолчанию 16]
;   Если кол-во элементов (на первой или последюущей итерации) больше или равно значению IQSort4InsThrs, используется быстрая сортировка, иначе
;   используется сортировка вставками - это немного ускоряет процесс (при правильном выборе значения IQSort4InsThrs, например, при значении по умолчанию)
;   и уменьшает глубину рекурсии, защищая стек от переполнения
 
; IQSort4MaxStk = максимальный размер стека в байтах, который допустимо использовать процедуре IQSort4 (включая call из основного кода) [0 = отключено; минимум 12; по умолчанию 128]
;   Каждый уровень вложенности использует 4 байта (2 слова) стека (первый уровень - до 4-х слов, последний может использовать на 1-2 слова больше, итого минимум 10-12 байт),
;   т.о. 128 байт позволяют организовать до 30 уровней рекурсии, что достаточно даже для очень больших массивов, особенно когда IQSort4InsThrs > 0
 
; При установке значений IQSort4InsThrs = IQSort4MaxStk = 0 процедура IQSort4 превращается в процедуру стандартной быстрой сортировки (т.е. некомбинированную)
 
;-----------------------------------------------------------------------------------------------------------------------
 
_defdef         MACRO   Const:REQ, DefVal:REQ
  IFDEF         Const
        _&Const =       Const
  ELSE
        _&Const =       DefVal
  ENDIF
ENDM
 
@386            =       ((@Cpu and 8) ne 0) or ((@Cpu and 2Fh) eq 0)
 
IF      not @386
  IFDEF         ??Version       ; TASM
    .ERR        "This module requires 386+ instructions enabled !!!"
  ELSE                          ; MASM
    .ERR        <This module requires 386+ instructions enabled !!!>
  ENDIF
ENDIF
 
_defdef inclIQSort4, 1
_defdef inclInsSort4, 0
 
_defdef Sort4SignCmp, 1
_defdef Sort4Ascending, 1
 
IF      _Sort4SignCmp
  IF    _Sort4Ascending
    srt?jl      EQU     <jl>
    srt?jg      EQU     <jg>
  ELSE
    srt?jl      EQU     <jg>
    srt?jg      EQU     <jl>
  ENDIF
ELSE
  IF    _Sort4Ascending
    srt?jl      EQU     <jb>
    srt?jg      EQU     <ja>
  ELSE
    srt?jl      EQU     <ja>
    srt?jg      EQU     <jb>
  ENDIF
ENDIF
 
_Sort4ElemDWords =      Sort4ElemDWords
IF      (_Sort4ElemDWords+1)/2 ne 1
  IFDEF         ??Version       ; TASM
    .ERR        "Wrong value of Sort4ElemDWords, it must be = 1 or 2 !!!"
  ELSE                          ; MASM
    .ERR        <Wrong value of Sort4ElemDWords, it must be = 1 or 2 !!!>
  ENDIF
ENDIF
_Sort4ElemSize  =       _Sort4ElemDWords*4      ; размер одного элемента массива (4 или 8 байт)
 
_defdef IQSort4InsThrs, 16
_defdef IQSort4MaxStk, 128
 
IF      _IQSort4InsThrs and _IQSort4InsThrs lt 2
  _IQSort4InsThrs =     0                       ; если IQSort4InsThrs < 2, принимаем значение 0
ENDIF
 
IF      _IQSort4MaxStk and _IQSort4MaxStk lt 10+(_Sort4ElemDWords-1)*2
  _IQSort4MaxStk =      0                       ; если IQSort4MaxStk < 10 + 2 (если Sort4ElemDWords = 2), принимаем значение 0
ENDIF
 
;-- IQSort4: Умная БЫСТРАЯ СОРТИРОВКА массива (комбинированным методом) ------------------------------------------------
; > Входные данные: DS:DX = адрес массива, CX = кол-во элементов массива (знаковое значение)
; > Результат: отсортированный массив (по тому же адресу)
; Если элементы массива содержат по 2 значения, т.е. Sort4ElemDWords = 2 (размер элемента массива = _Sort4ElemSize = 8 байтам), то:
;   * первое двойное слово содержит опорное значение (по которому происходит сравнение),
;   * второе двойное слово - связанные с элементом данные (обычно это указатель на данные);
;     при сортировке связанные данные переносятся вместе с опорными значениями
; Если кол-во элементов (на первой или последующей итерации) больше или равно значению IQSort4InsThrs, используется быстрая сортировка,
;   иначе используется сортировка вставками [только если IQSort4InsThrs <> 0]
; Сортировка вставками также используется, если для следующего уровня рекурсии потребуется более IQSort4MaxStk байт стека в общем сложности
;   [только если IQSort4MaxStk <> 0]
; Процедура изменяет регистры EAX, EBX, CX, DX, SI, DI, старшее слово EBP; сохраняет BP и сегментные регистры
IF      _inclIQSort4
IQSort4         PROC
                dec     cx
                jle     @@exit                  ; выходим, если кол-во элементов <= 1
 
                push    bp
                xor     bp,bp                   ; BP = кол-во рекурсий
                shl     cx,_Sort4ElemDWords+1
                add     cx,dx                   ; CX = адрес последнего элемента
 
                ; Главная процедура быстрой сортировки
                ; DX = адрес первого элемента, CX = адрес последнего элемента, CX > DX, BP = уровень рекурсии
        @@IQSort4Main:
IF      _IQSort4InsThrs
                mov     ax,cx
                sub     ax,dx
                shr     ax,_Sort4ElemDWords+1   ; AX = кол-во элементов минус 1
                cmp     ax,_IQSort4InsThrs-1
                jb      @@callins               ; если кол-во элементов меньше порогового значения, используем сортировку вставками
ENDIF
                mov     si,dx                   ;; I (SI) := L (DX)
        @@repeat1:                              ;; repeat
                mov     di,cx                   ;; J (DI) := R (CX)
                mov     bx,cx
                sub     bx,dx
                shr     bx,1
                and     bx,-_Sort4ElemSize
                add     bx,dx                   ;; P (BX) := (L + R) / 2
                mov     eax,[bx]                ;; T (EAX) := [P]
        @@repeat2 = @@cmpI                      ;; repeat
                ; SI = I, EAX = T, DI = J, DX = L, CX = R
                jmp     @@cmpI
        @@addI: add     si,_Sort4ElemSize       ;; Inc(I)
        @@cmpI: cmp     [si],eax                ;; while [I] < T
                srt?jl  @@addI
 
                jmp     @@cmpJ
        @@subJ: sub     di,_Sort4ElemSize       ;; Dec(J)
        @@cmpJ: cmp     [di],eax                ;; while [J] > T
                srt?jg  @@subJ
 
                cmp     si,di
                jnbe    @@noswap                ;; if I <= J then
 
                mov     ebx,[si]                ;;   Swap [I],[J]
                xchg    [di],ebx
                mov     [si],ebx
IF      _Sort4ElemDWords gt 1
                mov     ebx,[si+4]
                xchg    [di+4],ebx
                mov     [si+4],ebx
ENDIF
                add     si,_Sort4ElemSize       ;; Inc(I)
                sub     di,_Sort4ElemSize       ;; Dec(J)
        @@noswap:
                cmp     si,di
                jna     @@repeat2               ;; until I > J
 
                cmp     dx,di
                jnb     @@norecurs              ;; if L < J then
 
                push    cx
                push    si                      ; сохраняем R и I
                mov     cx,di
                ; DX = L, CX = J
IF      _IQSort4MaxStk
                cmp     bp,(_IQSort4MaxStk-(10+(_Sort4ElemDWords-1)*2))/4       ; 6 слов - это адрес возврата в вызываемую программу +
                                                ; bp + cx + si + адрес возврата из InsSort4 + bp (если Sort4ElemDWords = 2)
                jae     @@callins2              ; если число рекурсий достигло максимума, идём на вызов сортировки вставками: InsSort4(L, J)
ENDIF
                inc     bp                      ; иначе увеличиваем глубину рекурсии и идём на рекурсию
                jmp     @@IQSort4Main           ;;   IQSort4(L, J); вызов делаем через jmp для экономии стека :)
        @@recursret:
                pop     si
                pop     cx                      ; восстанавливаем I и R
        @@norecurs:
                mov     dx,si                   ;; L := I
                cmp     si,cx
                jnae    @@repeat1               ;; until I >= R
        @@finish:
                dec     bp                      ; уменьшаем глубину рекурсии
                jns     @@recursret             ; прыгаем, если это не первый (корневой) уровень рекурсии
                pop     bp
        @@exit: ret
IF      _IQSort4InsThrs
        @@callins:
                push    offset @@finish         ; адрес возврата
                jmp     @IQInsSort4             ; вместо call + jmp @@finish делаем push + jmp
ENDIF
IF      _IQSort4MaxStk
        @@callins2:
                push    offset @@recursret      ; адрес возврата
                jmp     @IQInsSort4             ; вместо call + jmp @@recursret делаем push + jmp
ENDIF
IQSort4         ENDP
ENDIF ; _inclIQSort4
 
;-- InsSort4: СОРТИРОВКА массива ВСТАВКАМИ -----------------------------------------------------------------------------
; > Входные данные: DS:DX = адрес массива, CX = кол-во элементов массива (знаковое значение)
; > Результат: отсортированный массив (по тому же адресу)
; Если элементы массива содержат по 2 значения, т.е. Sort4ElemDWords = 2 (размер элемента массива = _Sort4ElemSize = 8 байтам), то:
;   * первое двойное слово содержит опорное значение (по которому происходит сравнение),
;   * второе двойное слово - связанные с элементом данные (обычно это указатель на данные);
;     при сортировке связанные данные переносятся вместе с опорными значениями
; Процедура изменяет регистры EAX, EBX, SI, DI, старшее слово EBP; сохраняет CX, DX, BP и сегментные регистры
IF      _inclInsSort4
InsSort4        PROC
                dec     cx
                jle     @@exit                  ; выходим, если кол-во элементов <= 1
 
                shl     cx,_Sort4ElemDWords+1
                add     cx,dx                   ; CX = адрес последнего элемента
 
                ; Главная процедура сортировки вставками
                ; DX = адрес первого элемента, CX = адрес последнего элемента, CX > DX
IFDEF           ??Version       ; TASM
  @IQInsSort4:
ELSE                            ; MASM
  @IQInsSort4::
ENDIF
ELSEIF  _IQSort4InsThrs or _IQSort4MaxStk
@IQInsSort4     PROC
ENDIF
IF      _inclInsSort4 or _IQSort4InsThrs or _IQSort4MaxStk
IF      _Sort4ElemDWords gt 1
                push    bp
ENDIF
                mov     di,dx                   ; J (DI) := L - адрес первого элемента
        @@next:                                 ;; for J (DI) := L+1 (CX) to R (DX) do
                add     di,_Sort4ElemSize       ; J++ (DI) - адрес следующего проверяемого элемента (в основном цикле)
                mov     ebx,[di]                ;; T (EBP:EBX|EBX) := [J]
IF      _Sort4ElemDWords gt 1
                mov     ebp,[di+4]
ENDIF
                mov     si,di                   ; I+1 (SI) := DI - адрес элемента, следующего за сравниваемым (во внутреннем цикле)
        @@loop:                                 ;; repeat
                mov     eax,[si-_Sort4ElemSize]
                cmp     eax,ebx                 ;; if [I] > T then
%               srt?jl&e @@break                ; прыгаем, если [I] <= T
 
                mov     [si],eax                ;;  [I+1] := [I] else Break
IF      _Sort4ElemDWords gt 1
                mov     eax,[si-_Sort4ElemSize+4]
                mov     [si+4],eax
ENDIF
                sub     si,_Sort4ElemSize       ;; Dec(I)
                cmp     si,dx
                jnbe    @@loop                  ;; until I < L (I+1 <= L)
        @@break:
                mov     [si],ebx                ;; [I+1] := T
IF      _Sort4ElemDWords gt 1
                mov     [si+4],ebp
ENDIF
                cmp     di,cx
                jnae    @@next                  ; следующий элемент массива ;; end for
IF      _Sort4ElemDWords gt 1
                pop     bp
ENDIF
        @@exit: ret
ENDIF ; _inclInsSort4 or _IQSort4InsThrs or _IQSort4MaxStk
IF      _inclInsSort4
InsSort4        ENDP
ELSEIF  _IQSort4InsThrs or _IQSort4MaxStk
@IQInsSort4     ENDP
ENDIF

@Jin X · 12.11.2017, 12:20

Как вы понимаете, в прикреплённых архивах множество вариантов модулей на любой вкус и цвет, поэтому не стоит пугаться такому обилию директив условной компиляции – это самый насыщенный такими декорациями модуль

Файлы модулей, работающих с 16-битными данными:

Code
1
2
3
4
5
6
7
8
9
10
11
IQSort.inc – универсальный модуль умной быстрой сортировки (включает в себя процедуру быстрой сортировки IQSort и процедуру сортировки вставками InsSort)
IQSortS1.inc – модуль умной быстрой сортировки для массивов с одиночными элементами (процедуры IQSort и InsSort)
IQSortS2.inc – модуль умной быстрой сортировки для массивов с двойными элементами (процедуры IQSortDE и InsSortDE)
 
QSort.inc – универсальный модуль обычной быстрой сортировки (процедура QSort)
QSortS1.inc – модуль обычной быстрой сортировки для массивов с одиночными элементами (процедура QSort)
QSortS2.inc – модуль обычной быстрой сортировки для массивов с двойными элементами (процедура QSortDE)
 
ISort.inc – универсальный модуль сортировки вставками (процедура InsSort)
ISortS1.inc – модуль сортировки вставками для массивов с одиночными элементами (процедура InsSort)
ISortS2.inc – модуль сортировки вставками для массивов с двойными элементами (процедура InsSortDE)

Файлы модулей, работающих с 32-битными данными:

Code
1
2
3
4
5
6
7
8
9
10
11
IQSort4.inc – универсальный модуль умной быстрой сортировки (включает в себя процедуру быстрой сортировки IQSort4 и процедуру сортировки вставками InsSort4)
IQSrt4S1.inc – модуль умной быстрой сортировки для массивов с одиночными элементами (процедуры IQSort4 и InsSort4)
IQSrt4S2.inc – модуль умной быстрой сортировки для массивов с двойными элементами (процедуры IQSort4DE и InsSort4DE)
 
QSort4.inc – универсальный модуль обычной быстрой сортировки (процедура QSort4)
QSort4S1.inc – модуль обычной быстрой сортировки для массивов с одиночными элементами (процедура QSort4)
QSort4S2.inc – модуль обычной быстрой сортировки для массивов с двойными элементами (процедура QSort4DE)
 
ISort4.inc – универсальный модуль сортировки вставками (процедура InsSort4)
ISort4S1.inc – модуль сортировки вставками для массивов с одиночными элементами (процедура InsSort4)
ISort4S2.inc – модуль сортировки вставками для массивов с двойными элементами (процедура InsSort4DE)

Важно! Коллекция модулей, работающая с 32-битными элементами, требует включения поддержки инструкций процессора 386+ !!!

Файлы с именами без суффиксов (S1, S2) содержат много директив условной компиляции и констант и могут быть сложны для понимания. Однако они более универсальны и включают в код только ту часть, которая необходима.

Файлы с суффиксами S1 и S2 (Simple Single/Double) содержат минимальное кол-во настроек, которые хранятся внутри самих модулей (либо эти настройки отсутствуют вовсе). Для изменения некоторых настроек (например, присутствия знака в числовых значениях или направления сортировки) придётся править исходники (правда, сделать это легко – в этих файлах есть описание этого незамысловатого процесса). Эти файлы практически не содержат директив условной компиляции и более понятны для изучения.

В каждом из архивов есть файл ReadMe.txt с информацией о коллекции модулей сортировки.
К тому же, сами исходники снабжены подробным описанием каждой настройки и процедур.
В архивах также имеются папки examples с тестовыми программами, использующими данные модули.

Большая просьба!
В случае внесения изменений в текст include-файла добавляйте в его заголовок комментарий о том, что он модифицирован (с указанием имени автора внесения изменений, желательно также изменить и имя файла), чтобы при переносе на другой компьютер или в другой проект не возникло неожиданностей (сделайте это, даже если вы не планируете переносить файл в другое место)

p.s. Немного об используемых методах сортировки...
Почему я использую именно сортировку вставками, а не пузырьковую или сортировку Шелла? Повторюсь, что сортировка вставками на случайных данных работает раза в 2 быстрее пузырьковой (несмотря на её популярность), при этом в реализации она ничуть не сложнее, а где-то даже и проще. Сортировка Шелла не даст прироста скорости для небольших массивов (здесь же сортировка вставками используется по умолчанию для массивов, содержащих менее 16 элементами – это число взято в результате эмпирических экспериментов с разными значениями – 8, 12, 16, 24, 32). Прочие сортировки (вроде пирамидальной – тогда бы получился метод Introsort) слишком громоздки, поэтому я не стал их применять. Что касается быстрой сортировки, то я использую вариант реализации, схожий с используемым в Delphi – в сравнении с "классическим" вариантом (где рекурсивный вызов происходит дважды) данный метод во многих случаях более быстрый и использует меньше уровней рекурсии (правда, замеры я проводил именно в Delphi, но думаю, что и для ассемблера этот вариант оптимален, тем более он позволяет не записывать в стек адрес возврата при рекурсии)

asm7x

ФедосеевПавел · 24.06.2019, 02:37

Пирамидальная сортировка, сортировка кучей (HeapSort)
массива знаковых целых чисел (Windows 32 бит)

К реализации Mikl___ из сообщения #4 добавлю собственную.
Различие лишь в подходах передачи параметров и несколько более развёрнутом пояснении источников алгоритма.

О пирамидальной сортировке и разновидностях её реализации можно почитать по ссылкам:
https://ru.wikipedia.org/wiki/... сортировка
http://algolist.manual.ru/sort/pyramid_sort.php
https://www.codelab.ru/t/pyramid_sort/
Читать нужно внимательно, т.к. в статьях пояснения всегда приводятся для массива с индексацией от нуля, а примеры кода - то с индексацией от "0", то с индексацией от "1".

В Wikipedia приводится ссылка на примеры реализации в Wikibooks:
https://ru.wikibooks.org/wiki/... амидальная
https://en.wikibooks.org/wiki/... g/Heapsort
Также интересным будет ознакомление с реализациями на "розеттском коде":
http://rosettacode.org/wiki/So... s/Heapsort

Теория и рекурсивная реализация по данной ссылке, помогают лучше разобраться с алгоритмом:
https://evileg.com/ru/post/463/

Т.к. имеем дело с алгоритмом, а не с трюками для процессора, удобнее выбрать язык высокого уровня, реализовать на нём алгоритм и затем перевести отработанный код на ассемблер.

Мне удобнее реализовывать на Pascal.

Тестовая программа на Free Pascal

Pascal
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
program test_HeapSort;
 
const
  N = 10;
type
  TArray = array [0..N - 1] of integer;
 
 { алгоритм процедуры восстановления баланса пирамиды
  при добавлении нового A[k]
 
  A[]   - исходный массив
  K     - индекс добавляемого/просеиваемого элемента
  N     - максимальное значение индекса массива
 }
  procedure siftDown(var A: TArray; K, N: integer);
  var
    temp: integer;
    childPos: integer;
  begin
    {Это чтобы при K=0 И N=0 не делалось лишней перестановки}
    if 0 = N then
      exit;
(*
    while K * 2 + 1 <= N do
    begin
      childPos := 2 * K + 1;  // Индекс левого ребенка
 
      // выбираем в childPos индекс большего ребенка
      if (childPos + 1 <= N) and (A[childPos] < A[childPos + 1]) then
        Inc(childPos);
 
      // Если A[K] больше максимального ребенка - завершение
      if (A[K] >= A[childPos]) then
        break;
 
      // иначе - меняем его с наибольшим ребенком
      temp := A[K];
      A[K] := A[childPos];
      A[childPos] := temp;
 
      K := childPos;
    end;
*)
    temp := A[K];        // Оставляем копию
    while K * 2 + 1 <= N do
    begin
      childPos := 2 * K + 1;    // Индекс левого ребенка
 
      // выбираем в childPos индекс большего ребенка
      if (childPos + 1 <= N) and (A[childPos] < A[childPos + 1]) then
        Inc(childPos);
 
      // Если A[K] больше максимального ребенка - завершение
      if (temp >= A[childPos]) then
        break;
 
      // иначе - меняем его с наибольшим ребенком
      A[K] := A[childPos];
 
      K := childPos;
    end;
    {В конце восстанавливаем просеянному элементу
    его первоначальное значение}
    A[K] := temp;
  end;
 
  procedure HeapSort(var A: TArray; N: integer);
  var
    i: integer;
    temp: integer;
  begin
    { Построение пирамиды }
    for i := (N div 2) - 1 downto 0 do
      siftDown(A, i, N - 1);
    {Формирование конечной отсортированной
     последовательности + "балансирование"
     пирамиды }
    i := N - 1;
    while i > 0 do
    begin
      {меняем первый с последним}
      temp := A[0];
      A[0] := A[i];
      A[i] := temp;
      {Восстановление баланса для пирамиды A[0..i-1]}
      Dec(i);
      siftDown(A, 0, i);
    end;
  end;
 
  procedure ShowArray(const A: TArray; N: integer);
  var
    i: integer;
  begin
    for i := 0 to N - 1 do
      Write(A[i]: 3);
    writeln;
  end;
 
var
  A: TArray;
  i: integer;
begin
  randomize;
  for i := 0 to N - 1 do
    A[i] := random(100);
  ShowArray(A, N);
  HeapSort(A, N);
  ShowArray(A, N);
end.

Сделаю несколько примечаний по этой реализации.
За основу реализации был взят псевдокод по ссылке
https://www.codelab.ru/t/pyramid_sort/
Этот псевдокод содержит ошибки, исправить которые помогли сравнения с псевдокодом и реализацией по ссылке
http://rosettacode.org/wiki/So... s/Heapsort
Но в образцовом псевдокоде присутствует любопытная оптимизация процедуры siftDown - вместо обмена значений между "текущим корнем" и его "детьми", предлагается в корень помещать число, а само значение корня только хранить в переменной, чтобы по завершению цикла записать его в последнего просмотренного "ребёнка". Так несколько сокращается обращение к памяти и увеличивается скорость выполнения программы.

В моей реализации менее оптимальный (но более понятный) вариант заключён в комментарии.

Аккуратно перенося алгоритм на Ассемблер, получаем

Assembler
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
;вспомогательная процедура для сортировки кучей
;алгоритм процедуры восстановления баланса пирамиды при добавлении нового A[K]
;  A[]   - исходный массив
;  K     - индекс добавляемого/просеиваемого элемента
;  N     - максимальное значение индекса массива
;процедура просеивания следующего элемента:
;До процедуры: A[K+1]...A[N]  - пирамида
;После:  A[K]...A[N]  - пирамида
siftDown        proc      lpArray:DWORD, K:DWORD, N:DWORD       ;procedure siftDown(var A: TArray; K, N: integer);
                                                                ;  var
                                                                ;    temp: integer;
                                                                ;    childPos: integer;
        pushad                                                  ;  begin
        mov     ebx,    [N]
        mov     esi,    [lpArray]
        mov     ecx,    [K]
                                                                ;    {Это чтобы при K=0 И N=0 не делалось лишней перестановки}
        test    ebx,    ebx                                     ;    if 0 = N then
        jz      _exit                                           ;      exit;
        mov     edi,    [esi+ecx*4]                             ;    temp := A[K];
        _while:                                                 ;    while K * 2 + 1 <= N do
                                                                ;    begin
                mov     edx,    ecx                             ;      childPos := 2 * K + 1;  // Индекс левого ребенка
                add     edx,    edx
                inc     edx
                cmp     edx,    ebx
                ja      _break
                                                                ;      // выбираем в childPos индекс большего ребенка
                mov     eax,    edx                             ;      if (childPos + 1 <= N) and (A[childPos] < A[childPos + 1]) then
                inc     eax
                cmp     eax,    ebx
                ja      @f
                mov     eax,    [esi+eax*4]
                cmp     eax,    [esi+edx*4]
                jle     @f
                inc     edx                                     ;        Inc(childPos);
        @@:                                                     ;
                                                                ;      // Если A[K] больше максимального ребенка - завершение
                cmp     edi,    [esi+edx*4]                     ;      if (temp >= A[childPos]) then
                jge     _break                                  ;        break;
                                                                ;
                                                                ;      // иначе - меняем его с наибольшим ребенком
                mov     eax,    [esi+edx*4]                     ;      A[K] := A[childPos];
                mov     [esi+ecx*4],    eax
                                                                ;
                mov     ecx,    edx                             ;      K := childPos;
        jmp     _while                                          ;    end;
_break:
        mov     [esi+ecx*4],    edi                             ;    A[K] := temp;
_exit:                                                          ;  end;
        popad
        ret
siftDown        endp
 
;сортировка кучей (пирамидальная сортировка)
;на входе:
;  lpArray  - адрес массива
;  uiAmount - длина массива
HeapSort        proc    lpArray:DWORD, uiAmount:DWORD                   ;  procedure HeapSort(var A: TArray; N: integer);
                                                                        ;  var
                                                                        ;    i: integer;
                                                                        ;    temp: integer;
        pushad                                                          ;  begin
        mov     esi,    [lpArray]
        mov     ebx,    [uiAmount]
        ;Построение пирамиды                                            ;    { Построение пирамиды }
        mov     ecx,    ebx                                             ;    for i := (N div 2) - 1 downto 0 do
        shr     ecx,    1
        dec     ebx     ;т.к. в дальнейшем нужно только значение (N-1)
        jmp     _next
        _for:
                invoke  siftDown,       esi, ecx, ebx                   ;      siftDown(A, i, N - 1);
        _next:
                dec     ecx
        jns     _for
                                                                        ;    {Формирование конечной отсортированной
                                                                        ;     последовательности + "балансирование"
                                                                        ;     пирамиды }
        mov     ecx,    ebx                                             ;    i := N - 1;
        jmp     _test_while                                             ;    while i > 0 do
        _while:                                                         ;    begin
                ;меняем первый с последним                              ;      {меняем первый с последним}
                push    dword ptr [esi]                                 ;      temp := A[0];
                push    dword ptr [esi+4*ecx]                           ;      A[0] := A[i];
                pop     dword ptr [esi]                                 ;      A[i] := temp;
                pop     dword ptr [esi+4*ecx]
                ;Восстановление баланса для пирамиды A[0..i-1]          ;      {Восстановление баланса для пирамиды A[0..i-1]}
                dec     ecx                                             ;      Dec(i);
                invoke  siftDown,       esi, 0, ecx                     ;      siftDown(A, 0, i);
        _test_while:                                                    ;    end;
                test    ecx,    ecx
        jnz     _while
        popad                                                           ;  end;
        ret
HeapSort        endp

Пример вызова

Assembler
1
2
3
4
        Array           dd      22,  8, 42,  7, 43, 81, 51, 14, 49,  7
        ASize           dd      LENGTHOF Array
....................................
        invoke  HeapSort,       ADDR Array, [ASize]

Тестовая программа

Assembler
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
.686
.model flat, stdcall
option casemap :none
 
        include \masm32\include\windows.inc
 
        include \masm32\include\user32.inc
        include \masm32\include\kernel32.inc
        include \masm32\include\masm32.inc
 
        includelib \masm32\lib\user32.lib
        includelib \masm32\lib\kernel32.lib
        includelib \masm32\lib\masm32.lib
.data
        aszMsgInstant   db      0Dh, 0Ah, 'The data before sorting:', 0Dh, 0Ah, 0
        aszMsgResult    db      0Dh, 0Ah, 'The data after sorting:', 0Dh, 0Ah, 0
        aszInteger      db      '%4d', 0
        aszPressEnter   db      0Dh, 0Ah, 0Dh, 0Ah, "Press ENTER to exit", 0
        aszCrLf         db      0Dh, 0Ah, 0
        Array           dd      22,  8, 42,  7, 43, 81, 51, 14, 49,  7
        ASize           dd      LENGTHOF Array
 
.data?
        hConsoleOutput  HANDLE  ?
        hConsoleInput   HANDLE  ?
        Buffer          db      1024 dup(?)
        BufLen          dd      ?
 
.code
 
;вспомогательная процедура для сортировки кучей
;алгоритм процедуры восстановления баланса пирамиды при добавлении нового A[K]
;  A[]   - исходный массив
;  K     - индекс добавляемого/просеиваемого элемента
;  N     - максимальное значение индекса массива
;процедура просеивания следующего элемента:
;До процедуры: A[K+1]...A[N]  - пирамида
;После:  A[K]...A[N]  - пирамида
siftDown        proc      lpArray:DWORD, K:DWORD, N:DWORD       ;procedure siftDown(var A: TArray; K, N: integer);
                                                                ;  var
                                                                ;    temp: integer;
                                                                ;    childPos: integer;
        pushad                                                  ;  begin
        mov     ebx,    [N]
        mov     esi,    [lpArray]
        mov     ecx,    [K]
                                                                ;    {Это чтобы при K=0 И N=0 не делалось лишней перестановки}
        test    ebx,    ebx                                     ;    if 0 = N then
        jz      _exit                                           ;      exit;
        mov     edi,    [esi+ecx*4]                             ;    temp := A[K];
        _while:                                                 ;    while K * 2 + 1 <= N do
                                                                ;    begin
                mov     edx,    ecx                             ;      childPos := 2 * K + 1;  // Индекс левого ребенка
                add     edx,    edx
                inc     edx
                cmp     edx,    ebx
                ja      _break
                                                                ;      // выбираем в childPos индекс большего ребенка
                mov     eax,    edx                             ;      if (childPos + 1 <= N) and (A[childPos] < A[childPos + 1]) then
                inc     eax
                cmp     eax,    ebx
                ja      @f
                mov     eax,    [esi+eax*4]
                cmp     eax,    [esi+edx*4]
                jle     @f
                inc     edx                                     ;        Inc(childPos);
        @@:                                                     ;
                                                                ;      // Если A[K] больше максимального ребенка - завершение
                cmp     edi,    [esi+edx*4]                     ;      if (temp >= A[childPos]) then
                jge     _break                                  ;        break;
                                                                ;
                                                                ;      // иначе - меняем его с наибольшим ребенком
                mov     eax,    [esi+edx*4]                     ;      A[K] := A[childPos];
                mov     [esi+ecx*4],    eax
                                                                ;
                mov     ecx,    edx                             ;      K := childPos;
        jmp     _while                                          ;    end;
_break:
        mov     [esi+ecx*4],    edi                             ;    A[K] := temp;
_exit:                                                          ;  end;
        popad
        ret
siftDown        endp
 
;сортировка кучей (пирамидальная сортировка)
;на входе:
;  lpArray  - адрес массива
;  uiAmount - длина массива
HeapSort        proc    lpArray:DWORD, uiAmount:DWORD                   ;  procedure HeapSort(var A: TArray; N: integer);
                                                                        ;  var
                                                                        ;    i: integer;
                                                                        ;    temp: integer;
        pushad                                                          ;  begin
        mov     esi,    [lpArray]
        mov     ebx,    [uiAmount]
        ;Построение пирамиды                                            ;    { Построение пирамиды }
        mov     ecx,    ebx                                             ;    for i := (N div 2) - 1 downto 0 do
        shr     ecx,    1
        dec     ebx     ;т.к. в дальнейшем нужно только значение (N-1)
        jmp     _next
        _for:
                invoke  siftDown,       esi, ecx, ebx                   ;      siftDown(A, i, N - 1);
        _next:
                dec     ecx
        jns     _for
                                                                        ;    {Формирование конечной отсортированной
                                                                        ;     последовательности + "балансирование"
                                                                        ;     пирамиды }
        mov     ecx,    ebx                                             ;    i := N - 1;
        jmp     _test_while                                             ;    while i > 0 do
        _while:                                                         ;    begin
                ;меняем первый с последним                              ;      {меняем первый с последним}
                push    dword ptr [esi]                                 ;      temp := A[0];
                push    dword ptr [esi+4*ecx]                           ;      A[0] := A[i];
                pop     dword ptr [esi]                                 ;      A[i] := temp;
                pop     dword ptr [esi+4*ecx]
                ;Восстановление баланса для пирамиды A[0..i-1]          ;      {Восстановление баланса для пирамиды A[0..i-1]}
                dec     ecx                                             ;      Dec(i);
                invoke  siftDown,       esi, 0, ecx                     ;      siftDown(A, 0, i);
        _test_while:                                                    ;    end;
                test    ecx,    ecx
        jnz     _while
        popad                                                           ;  end;
        ret
HeapSort        endp
 
ShowArray       proc    lpArray:DWORD, uiAmount:DWORD
        pushad
 
        mov     ecx,    [uiAmount]
        mov     esi,    [lpArray]
        @@ForI:
                push    ecx
                lodsd
                invoke  wsprintf,       ADDR Buffer, ADDR aszInteger, eax
                mov     [BufLen],       eax
                invoke  WriteConsole,   hConsoleOutput, ADDR Buffer,\
                                        BufLen, ADDR BufLen, NULL
                pop     ecx
        loop    @@ForI
 
        popad
        ret
ShowArray       endp
 
main    proc
 
        ; получение описателей ввода и вывода консоли
        invoke  GetStdHandle,   STD_INPUT_HANDLE
        mov     hConsoleInput,  eax
 
        invoke  GetStdHandle,   STD_OUTPUT_HANDLE
        mov     hConsoleOutput, eax
 
        invoke  ClearScreen
 
        ;вывод исходных данных
        invoke  WriteConsole,   hConsoleOutput, ADDR aszMsgInstant,\
                                LENGTHOF aszMsgInstant - 1,\
                                ADDR BufLen, NULL
        invoke  ShowArray,      ADDR Array, [ASize]
 
        ;обработка массива - сортировка
        invoke  HeapSort,       ADDR Array, [ASize]
        ;вывод результата
        invoke  WriteConsole, hConsoleOutput, ADDR aszMsgResult,\
                LENGTHOF aszMsgResult - 1, ADDR BufLen, NULL
        invoke  ShowArray,      ADDR Array, [ASize]
 
        ;ожидание нажатия ENTER
        invoke  WriteConsole,   hConsoleOutput, ADDR aszPressEnter,\
                                LENGTHOF aszPressEnter - 1, ADDR BufLen, NULL
        invoke  ReadConsole,    hConsoleInput, ADDR Buffer,\
                                LENGTHOF Buffer, ADDR BufLen, NULL
 
        invoke  ExitProcess,    0
main    endp
 
end     main

Это учебная реализация, не претендующая на максимальную производительность, но показывающая связь алгоритма с кодом.

Возможные пути улучшения данной реализации:
1. Т.к. и HeapSort и siftDown работают с одним массивом, то можно не передавать адрес массива отдельным параметром, условившись, что он будет неизменно находится в одном из регистров (например, в esi).
2. Т.к. при выполнении сортировки фактически требуется сохранение не более двух регистров (ecx и ebx), можно заменить в siftDown инструкции pushad/popad на инструкции для двух конкретных регистров. Или же, переработать программу для передачи параметров в siftDown через глобальные переменные - как это сделано у Mikl___ - или через локальные для HeapSort, т.к. для неё siftDown является, по сути, вложенной процедурой.

ФедосеевПавел · 17.04.2021, 23:26

Сортировка массива процедурой qsort из MSVCRT (Windows 32 бит)

В состав "msvcrt.dll" (Windows) входит процедура qsort, позволяющая сортировать массив с элементами произвольного типа.

Описание процедуры со странички Microsoft:

Кликните здесь для просмотра всего текста

Выполняет быструю сортировку. Существует более безопасная версия этой функции, см. раздел qsort_s.

Синтаксис

C
1
2
3
4
5
6
void qsort(
   void *base,
   size_t number,
   size_t width,
   int (__cdecl *compare )(const void *, const void *)
);

Параметры
base
Начало целевого массива.

number
Размер массива в элементах.

width
Размер элементов в байтах.

compare
Указатель на пользовательскую подпрограмму, которая сравнивает два элемента массива и возвращает значение, показывающее, как соотносятся их значения.

Примечания
qsort Функция реализует алгоритм быстрой сортировки для сортировки массива number элементов, каждый из которых равен width байтам. Аргумент base — это указатель на базовую часть массива, который необходимо отсортировать. qsort перезаписывает этот массив с помощью отсортированных элементов.
qsort вызывает compare подпрограммы один или несколько раз во время сортировки и передает указатели на два элемента массива при каждом вызове. Если compare параметр указывает, что два элемента одинаковы, их порядок в результирующем отсортированном массиве не определен.

C
1
compare( (void *) & elem1, (void *) & elem2 );

Подпрограмма сравнивает элементы и возвращает одно из следующих значений.

Сравнение возвращаемого значения функции	Описание
< 0	`elem1` меньше `elem2`
0	`elem1` эквивалентно `elem2`
> 0	`elem1` больше `elem2`

Массив сортируется по возрастанию, как определено функцией сравнения. Для сортировки массива по убыванию измените смысл значений "больше" и "меньше" на противоположный в функции сравнения.
Эта функция проверяет свои параметры. Если параметр или имеет значение или имеет значение compare number NULL base NULL и number является ненулевым или значение width меньше нуля, вызывается обработчик недопустимых параметров, как описано в разделе Проверка параметров. Если выполнение может быть продолжено, функция возвращает и errno устанавливается в значение EINVAL.
По умолчанию глобальное состояние этой функции ограничивается приложением. Чтобы изменить это, см. раздел глобальное состояние в CRT.

Пример

C
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
// crt_qsort.c
// arguments: every good boy deserves favor
 
/* This program reads the command-line
* parameters and uses qsort to sort them. It
* then displays the sorted arguments.
*/
 
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
 
int compare( const void *arg1, const void *arg2 );
 
int main( int argc, char **argv )
{
   int i;
   /* Eliminate argv[0] from sort: */
   argv++;
   argc--;
 
   /* Sort remaining args using Quicksort algorithm: */
   qsort( (void *)argv, (size_t)argc, sizeof( char * ), compare );
 
   /* Output sorted list: */
   for( i = 0; i < argc; ++i )
      printf( " %s", argv[i] );
   printf( "\n" );
}
 
int compare( const void *arg1, const void *arg2 )
{
   /* Compare all of both strings: */
   return _stricmp( * ( char** ) arg1, * ( char** ) arg2 );
}

Использование в синтаксисе masm32 схематично выглядит

Assembler
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
.686
.model flat, stdcall
option casemap :none
        .nolist
        include \masm32\include\msvcrt.inc
        ...............................
 
        includelib \masm32\lib\msvcrt.lib
        ...............................
        .list
.data
        Array                   dd      1, 8, -5, 97, 100, 45
.code
 
Compare proc    C       ;lpA:DWORD, lpB:DWORD
        ...............................
        ret
Compare endp
 
main    proc
        ...............................
        ;сортировка массива
        invoke  crt_qsort,      ADDR Array,  LENGTHOF Array, TYPE Array, ADDR Compare
        ...............................
main    endp
 
end     main

По поводу весовой функции сделаю примечание.
Предполагаю, что когда-то достаточно было возвращать из весовой функции не полный результат сравнения, а только один из двух вариантов - "больше" или "меньше или равно".
Проверяя работу crt_qsort для неполной весовой функции столкнулся со следующим поведением:
- при длине массива не более 8 элементов результат сортировки ожидаемый
- при длине массива более 8 элементов массив будет лишь частично отсортирован.
Но после реализации весовой функции, различающей все три состояния ("больше", "равно", "меньше"), результат сортировки стал ожидаемым и корректным.

На форуме уже встречались примеры применения этой процедуры, например,
для masm32 Преобразовать массив, расположив сначала отрицательные, затем положительные, а затем нулевые элементы
Скопирую из сообщения по ссылке пример Charles Kludge сортировки массива целых чисел так, чтобы сначала располагались отрицательные, затем положительные и после них нули (очевидно, что достаточно сортировать, как массив чисел без знака, т.к. отрицательные числа представлены в дополнительном формате и при сравнении без учёта знака будут больше положительных чисел).
Сразу исправлю опечатку и весовую функцию.

Кликните здесь для просмотра всего текста

Assembler
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
.486                ; create 32 bit code
.model  flat, stdcall       ; 32 bit memory model
option  casemap :none       ; case sensitive
 
include \masm32\include\windows.inc
include \masm32\include\masm32.inc
include \masm32\include\user32.inc
include \masm32\include\kernel32.inc
include \masm32\include\msvcrt.inc
 
includelib  \masm32\lib\masm32.lib
includelib  \masm32\lib\user32.lib
includelib  \masm32\lib\kernel32.lib
includelib  \masm32\lib\msvcrt.lib
 
.data
arr dd  101,34,0,11,-24,12,54,16,0,9,12,-19,72,0,1,-14,121,61,22,3,-26,5,37
tpd db  '%d, ',0
titl    db  'Lab3', 0Dh,0Ah
msg1    db  'x=',0 ;
    .code
 
; ф-ция сортировки массива
cmp_subr:
    mov eax, [esp+4]
    mov edx, [esp+8]
    mov eax, dword ptr [eax]
    cmp eax, dword ptr [edx]
    setb    al
    seta    ah
    sub     al, ah
@@: movsx   eax, al
    ret
 
start:  invoke  crt_puts, ADDR titl
    call    prn_arr
    invoke  crt_qsort, ADDR arr, (tpd-arr)/4, 4,  ADDR cmp_subr
    invoke  crt_puts, ADDR msg1
    call    prn_arr
    invoke crt_exit, 0
 
; п/п печати массива
prn_arr:    lea esi, arr
    mov ecx, (tpd-arr)/4
@@: lodsd
    push    ecx
    invoke  crt_printf, ADDR tpd, eax
    pop ecx
    loop    @B
    ret
    end start

Можно добавить ещё примеров
Сортировка целых чисел с учётом знака

Кликните здесь для просмотра всего текста

Assembler
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
.686
.model flat, stdcall
option casemap :none
        .nolist
        include \masm32\include\windows.inc
 
        include \masm32\include\user32.inc
        include \masm32\include\kernel32.inc
        include \masm32\include\msvcrt.inc
        include \masm32\include\masm32.inc
        include \masm32\macros\macros.asm
 
        includelib \masm32\lib\user32.lib
        includelib \masm32\lib\kernel32.lib
        includelib \masm32\lib\msvcrt.lib
        includelib \masm32\lib\masm32.lib
        .list
.const
        aszPressAnyKey          db      0Dh, 0Ah, 0Dh, 0Ah, "Press any key to exit", 0
.data
        Array                   dd      1, 8, -5, 97, 100, 45
.data?
 
.code
 
ShowArray       proc    lpArray:DWORD, nCount:DWORD
        mov     esi,    [lpArray]
        mov     ecx,    [nCount]
        @@:
                push    ecx
                push    esi
                printf("%8d", dword ptr[esi])
                pop     esi
                pop     ecx
                add     esi,    4
        loop    @b
        ret
ShowArray       endp
 
Compare proc    ;lpA:DWORD, lpB:DWORD
        mov     eax,    [esp+4]
        mov     edx,    [esp+8]
        mov     eax,    [eax]
        cmp     eax,    [edx]
        setg    al
        setl    ah
        sub     al,     ah
        movsx   eax,    al
        ret
Compare endp
 
 
main    proc
 
        ;вывод исходного массива
        printf("Before sort:\n")
        invoke  ShowArray,      ADDR Array, LENGTHOF Array
        ;сортировка массива
        invoke  crt_qsort,      ADDR Array,  LENGTHOF Array, TYPE Array, ADDR Compare
        ;вывод обработанного массива
        printf("\n\nAfter sort:\n")
        invoke  ShowArray,      ADDR Array, LENGTHOF Array
 
        ;ожидание нажатия любой клавиши
        invoke  crt_printf,     ADDR aszPressAnyKey
        invoke  crt__getch
        ;завершение программы
        invoke  ExitProcess,    0
main    endp
 
end     main

Сортировка массива действительных чисел (в формате с "плавающей запятой") двойной точности (double):

Кликните здесь для просмотра всего текста

Assembler
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
.686
.model flat, stdcall
option casemap :none
        .nolist
        include \masm32\include\windows.inc
 
        include \masm32\include\user32.inc
        include \masm32\include\kernel32.inc
        include \masm32\include\msvcrt.inc
        include \masm32\include\masm32.inc
        include \masm32\macros\macros.asm
 
        includelib \masm32\lib\user32.lib
        includelib \masm32\lib\kernel32.lib
        includelib \masm32\lib\msvcrt.lib
        includelib \masm32\lib\masm32.lib
        .list
.const
        aszPressAnyKey          db      0Dh, 0Ah, 0Dh, 0Ah, "Press any key to exit", 0
.data
        Array                   dq      1.0, 8.0, -5.2, 97.3, 100.2, 45.4
.data?
 
.code
 
ShowArray       proc    lpArray:DWORD, nCount:DWORD
        mov     esi,    [lpArray]
        mov     ecx,    [nCount]
        @@:
                push    ecx
                push    esi
                printf("%10.4lf", qword ptr[esi])
                pop     esi
                pop     ecx
                add     esi,    8
        loop    @b
        ret
ShowArray       endp
 
Compare proc    ;lpA:DWORD, lpB:DWORD
        ;по соглашению можно не сохранять значения регистров eax, edx
        mov     eax,    [esp+4]
        mov     edx,    [esp+8]
        ;загружаем сравниваемые числа в стек FPU
        fld     qword ptr [eax]
        fld     qword ptr [edx]
        ;сравниваем числа и сразу освобождаем стек FPU
        fcomip  st(0),  st(1)
        fstp    st(0)
        ;т.к. при сравнении выставляются те же флаги, что
        ;и для целых чисел без знака
        setb    al
        seta    ah
        sub     al,     ah
        movsx   eax,    al
        ret
Compare endp
 
 
main    proc
 
        ;т.к. в ходе программы будет работа с FPU - сразу инициализируем
        finit
        ;вывод исходного массива
        printf("Before sort:\n")
        invoke  ShowArray,      ADDR Array, LENGTHOF Array
        ;сортировка массива
        invoke  crt_qsort,      ADDR Array,  LENGTHOF Array, TYPE Array, ADDR Compare
        ;вывод обработанного массива
        printf("\n\nAfter sort:\n")
        invoke  ShowArray,      ADDR Array, LENGTHOF Array
 
        ;ожидание нажатия любой клавиши
        invoke  crt_printf,     ADDR aszPressAnyKey
        invoke  crt__getch
        ;завершение программы
        invoke  ExitProcess, 0
main    endp
 
end     main

В этих примерах весовая функция (функция сравнения) достаточно простая, поэтому при реализации можно и нужно обходиться без стекового фрейма. В синтаксисе это выразилось в отсутствии описания параметров, а значит в результате компиляции инструкция ret не будет чистить стек от параметров, как по умолчанию предписывает параметр stdcall в директиве .model.
При более сложной весовой функции и необходимости иметь кадр (фрейм) стека нужно убедиться, что функция объявлена с соглашением о вызове для языка C (cdecl):

Assembler
1
2
3
4
Compare proc    C A:DWORD, B:DWORD
        ..........................
        ret
Compare endp

Например, нужно сортировать по возрастанию площади массив прямоугольников, заданных длинами сторон.
В этом примере также можно было перед вызовом сортировки очистить стек FPU и поддерживать его пустым после выхода из весовой функции. Но, для учебного примера, создаётся излишне сложная функция, демонстрирующая необходимость явного объявления соглашения о вызове при описании процедуры.

Кликните здесь для просмотра всего текста

Assembler
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
.686
.model flat, stdcall
option casemap :none
        .nolist
        include \masm32\include\windows.inc
 
        include \masm32\include\user32.inc
        include \masm32\include\kernel32.inc
        include \masm32\include\msvcrt.inc
        include \masm32\include\masm32.inc
        include \masm32\macros\macros.asm
 
        includelib \masm32\lib\user32.lib
        includelib \masm32\lib\kernel32.lib
        includelib \masm32\lib\msvcrt.lib
        includelib \masm32\lib\masm32.lib
        .list
.const
        aszFmt                  db      "A = %8.4lf, B = %8.4lf, A*B = %8.4lf", 0Dh, 0Ah, 0
        aszPressAnyKey          db      0Dh, 0Ah, 0Dh, 0Ah, "Press any key to exit", 0
.data
        TRectangle      struc
                SideA   dq      ?
                SideB   dq      ?
        TRectangle      ends
 
        Array   TRectangle      <10.0, 12.3>,\
                                <12.3, 13.5>,\
                                <10.3,  1.5>,\
                                < 2.3,  3.5>,\
                                < 1.3, 17.7>,\
                                < 0.3, 43.5>,\
                                < 7.1,  5.1>
.data?
 
.code
 
ShowArray       proc    lpArray:DWORD, nCount:DWORD
        LOCAL   @StateFPU[108]:byte     ;108 use32, 94 use16
        ;перед очисткой стека FPU сохраним:
        fsave   [@StateFPU]     ; состояние FPU
        mov     esi,    [lpArray]
        mov     ecx,    [nCount]
        push    esi
        push    ecx
        sub     esp,    3*8
        push    offset aszFmt
        @@:
                mov     [esp+28],       ecx
                mov     [esp+32],       esi
                fld     qword ptr [esi]
                fst     qword ptr [esp+4]
                fld     qword ptr [esi+8]
                fst     qword ptr [esp+12]
                fmulp   st(1),  st(0)
                fstp    qword ptr [esp+20]
                call    crt_printf
                mov     esi,    [esp+32]
                mov     ecx,    [esp+28]
                add     esi,    2*8
        loop    @b
        add     esp,    3*8+4
        ;восстановление состояния FPU
        frstor  [@StateFPU]
        ret
ShowArray       endp
 
Compare proc    C A:DWORD, B:DWORD
        LOCAL   @StateFPU[108]:byte     ;108 use32, 94 use16
        ;перед очисткой стека FPU сохраним:
        fsave   [@StateFPU]     ; состояние FPU
        mov     eax,    [A]
        fld     TRectangle.SideA([eax])
        fmul    TRectangle.SideB([eax])
        mov     eax,    [B]
        fld     TRectangle.SideA([eax])
        fmul    TRectangle.SideB([eax])
        fcomi   st(0),  st(1)
        setb    al
        seta    ah
        sub     al,     ah
        movsx   eax,    al
        ;восстановление состояния FPU
        frstor  [@StateFPU]
        ret
Compare endp
 
main    proc
 
        printf("Before sort:\n")
        invoke  ShowArray,      ADDR Array, LENGTHOF Array
 
        invoke  crt_qsort,      ADDR Array, LENGTHOF Array, TYPE Array, ADDR Compare
 
        printf("\n\nAfter sort:\n")
        invoke  ShowArray,      ADDR Array, LENGTHOF Array
 
        ;ожидание нажатия любой клавиши
        invoke  crt_printf,     ADDR aszPressAnyKey
        invoke  crt__getch
        ;завершение программы
        invoke  ExitProcess, 0
main    endp
 
end     main

Новые блоги и статьи Все статьи Все блоги /
Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .	Фото: Daniel Greenwood kumehtar 13.11.2025	Расскажи мне о Мире, бродяга kumehtar 12.11.2025 — Расскажи мне о Мире, бродяга, Ты же видел моря и метели. Как сменялись короны и стяги, Как эпохи стрелою летели. - Этот мир — это крылья и горы, Снег и пламя, любовь и тревоги, И бескрайние. . .	PowerShell Snippets iNNOKENTIY21 11.11.2025 Модуль PowerShell 5. 1+ : Snippets. psm1 У меня модуль расположен в пользовательской папке модулей, по умолчанию: \Documents\WindowsPowerShell\Modules\Snippets\ А в самом низу файла-профиля. . .

@novic-di 1 / 1 / 0 Регистрация: 10.02.2011 Сообщений: 46

	Программа для сортировки любого массива 23.11.2011, 19:25. Показов 92690. Ответов 15 Метки нет (Все метки) Отсортировать любой массив. Создать программу для отсортировки любого массива. 0

@Vadimych 639 / 482 / 12 Регистрация: 10.01.2011 Сообщений: 1,045
	23.11.2011, 20:18
	novic-di, поищите по разделу, тут таких программ навалом уже. 0