Блочная сортировка как реализовать? - Assembler

Формулировка задачи:

Нужна помощь в реализации алгоритма сортировки bucket sort на ассемблере x86 тасм

Решение задачи: «Блочная сортировка как реализовать?»

Листинг программы

LOCALS
 
.model small, NOLANGUAGE
 
.stack 1024h
 
.data
        CrLf    db      0Dh, 0Ah, '$'
 
        A       dw      4, 25, 45, 11, 15, 73, 53, 59, 25, 23, 27, 99, 7
        ArSize  equ     ($-A)/2
 
        hor     equ     10      ;т.к. остатки от деления на 10 в диапазоне 0..9
        ver     equ     ArSize+1
 
.code
 
main    proc
        mov     ax,     @data
        mov     ds,     ax
        ;вывод исходного массива
        mov     cx,     ArSize
        lea     dx,     A
        call    ShowArray
        mov     ah,     09h
        lea     dx,     CrLf
        int     21h
 
        ;обработка - сортировка массива
        mov     cx,     ArSize
        lea     dx,     A
        call    bucketSort
 
        ;вывод результата - отсортированного массива
        call    ShowArray
        mov     ah,     09h
        lea     dx,     CrLf
        int     21h
 
        mov     ax,     4C00h
        int     21h
main    endp
 
;блочная сортировка массива слов
;на входе
; cx    - длина массива
; ds:dx - указатель на массив
bucketSort      proc
;объявление переменных
LOCAL   buckets:word:(hor*ver), X:word, Count:word, Ten:word;
;выделение памяти в стеке под переменные (т.к. язык не указан - делаем вручную)
        push    bp
        mov     bp,     sp
        sub     sp,     hor*ver*2+3*2   ;размер локальных переменных
        ;сохранение регистров
        push    ax
        push    bx
        push    cx
        push    dx
        push    si
        push    di
        ;вспомогательная переменная
        mov     Ten,    10
        ;for(x=1; x<=100; x *= 10)
        mov     X,      1
@@ForX:
        ;всем элементам buckets присваиваем метку "не использовалось" значение (-1)
        push    cx
        push    es
        push    ss
        pop     es
        mov     ax,     -1
        lea     di,     ss:buckets
        mov     cx,     (hor*ver)
        rep     stosw
        pop     es
        pop     cx
 
        ;count = 0      //обнуляем счётчик ячеек исходного массива чисел
        ;на самом деле Count - смещение в исходном массиве, а не просто индекс
        mov     Count,  0
        ;for(i=0; i < size; i++)
        push    cx
        push    dx
        mov     bx,     dx      ;задание базы для обращения к исходному массиву
        mov     si,     0       ;i=0
        @@ForI:
                mov     ax,     [bx+si] ;ax=array[i]
                mov     dx,     0       ;temp=array[i] / x
                div     X
                mov     dx,     0       ;oststok = temp % 10
                div     Ten
                mov     ax,     dx      ;ax - остаток от деления
 
                mov     di,     hor*2   ;получаем смещение в двумерном массиве
                mul     di
                add     ax,     si
                mov     di,     ax      ;di = смещение, соответствующее bucket[ostatok][i]
 
                mov     ax,     [bx+si] ;ax = array[i]
                mov     buckets[di],ax  ;buckets[oststok][i] = array[i]
 
                add     si,     2       ;i++ (т.к. si - смещение, то увеличиваем на размер элемента)
        loop    @@ForI
        pop     dx
        pop     cx
 
        ;вложенные циклы по всем элементам buckets проще представить
        ;одним циклом по всем элементам с индексом от 0 до (hor*ver-1)
        ;т.к. ячейки двумерного массива располагаются в памяти последовательно и
        ;построчно
        ;for(i=0; i<hor; i++)
        ;  for(j=0; j<ver;j++)
        push    cx
        push    dx
        mov     cx,     (hor*ver)
        mov     di,     0
        mov     bx,     dx
        @@ForIJ:
                mov     ax,     buckets[di]     ;if (buckets[i][j] != -1
                cmp     ax,     -1
                je      @@Skip
                mov     si,     Count           ;  array[count] = bucket[i][j]
                mov     [bx+si],        ax
                add     Count,  2               ;  count++
        @@Skip:
                add     di,     2               ;i++, j++
        loop    @@ForIJ
        pop     dx
        pop     cx
 
        mov     ax,     X       ;X:= X*10
        add     ax,     ax      ;ax = 2*X
        mov     bx,     ax      ;bx = 2*X
        add     ax,     ax
        add     ax,     ax      ;ax= 8*X
        add     ax,     bx      ;ax = 10*X
        mov     X,      ax
 
        cmp     X,      100
        ja      @@BreakForX
        jmp     @@ForX
 
@@BreakForX:
 
        ;восстановление регистров
        pop     di
        pop     si
        pop     dx
        pop     cx
        pop     bx
        pop     ax
        ;освобождение памяти от локальных переменных
        mov     sp,     bp
        pop     bp
        ;возврат из процедуры и освобождение памяти от аргументов
        ret     0
bucketSort      endp
 
;Вывод массива слов
;cx - количество выводимых элементов
;ds:dx - адрес массива
ShowArray       proc
        push    ax
        push    bx
        push    cx
        push    dx
        push    si
        push    di
 
        jcxz    @@Exit          ;если массив пустой - завершить
 
        mov     si,     1       ;индекс элемента массива
        mov     di,     dx      ;адрес текущего элемента массива
        @@ForI:
                mov     ax,     [di]
                call    Show_AX
                mov     ah,     02h
                mov     dl,     ' '
                int     21h
                ;переход к следующему элементу
                inc     si
                add     di,     2
        loop    @@ForI
@@Exit:
        pop     di
        pop     si
        pop     dx
        pop     cx
        pop     bx
        pop     ax
        ret
ShowArray       endp
 
; выводит число из регистра AX на экран
; входные данные:
; ax - число для отображения
Show_AX proc
        push    ax
        push    bx
        push    cx
        push    dx
        push    di
 
        mov     cx, 10
        xor     di, di          ; di - кол. цифр в числе
 
        ; если число в ax отрицательное, то
        ;1) напечатать '-'
        ;2) сделать ax положительным
        or      ax, ax
        jns     @@Conv
        push    ax
        mov     dx, '-'
        mov     ah, 2           ; ah - функция вывода символа на экран
        int     21h
        pop     ax
 
        neg     ax
 
@@Conv:
        xor     dx, dx
        div     cx              ; dl = num mod 10
        add     dl, '0'         ; перевод в символьный формат
        inc     di
        push    dx              ; складываем в стэк
        or      ax, ax
        jnz     @@Conv
        ; выводим из стэка на экран
@@Show:
        pop     dx              ; dl = очередной символ
        mov     ah, 2           ; ah - функция вывода символа на экран
        int     21h
        dec     di              ; повторяем пока di<>0
        jnz     @@Show
 
        pop     di
        pop     dx
        pop     cx
        pop     bx
        pop     ax
        ret
Show_AX endp
 
end     main

Объяснение кода листинга программы

Объявление секции LOCALS для определения локальных переменных
Определение модели выполнения программы и размера стека
Инициализация переменных в секции .data, включая массив A, содержащий 13 заранее заданных значений, и другие переменные.
Инициализация процедуры main
Загрузка адресного регистра ds и первоначальные шаги вывода исходного массива
Сортировка массива с помощью процедуры bucketSort
Вывод отсортированного массива
Выход из программы Процедура bucketSort:
Объявление локальных переменных
Выделение памяти в стеке под переменные и сохранение регистров
Производится блочная сортировка массива слов по указанной логике
Восстановление регистров и освобождение памяти от локальных переменных Процедура ShowArray:
Вывод массива слов на экран Процедура Show_AX:
Подготовка числа для отображения (поиск количества цифр в числе и обработка отрицательных чисел)
Вывод числа на экран, конвертированного в символьный формат Реализация программы заканчивается секцией end и выходом из процесса main.