Двоичная поразрядная сортировка массива целых чисел - Assembler

Узнай цену своей работы

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

Выполнить двоичную поразрядную сортировку массива целых чисел

Решение задачи: «Двоичная поразрядная сортировка массива целых чисел»

textual
Листинг программы
LOCALS
 
.model small, Pascal
 
.stack 1000h
 
.data
 
        A               dw      100, 20, 500, 800, 600, 42, 32, 7894, 6541
        N               dw      ($-A)/2
 
        CrLf            db      0Dh, 0Ah, '$'
        msgBefore       db      'Before sort:', 0Dh, 0Ah, '$'
        msgAfter        db      'After sort:', 0Dh, 0Ah, '$'
.code
 
main    proc
        mov     ax,     @data
        mov     ds,     ax
        ;вывод массива до сортировки
        mov     ah,     09h
        lea     dx,     msgBefore
        int     21h
        lea     dx,     A
        mov     cx,     N
        call    ShowArray
 
        mov     ah,     09h
        lea     dx,     CrLf
        int     21h
 
        ;сортировка массива
        lea     ax,     A
        push    ax
        mov     ax,     N
        push    N
        mov     ax,     8000h
        push    ax
        call    RadixSort
 
        ;вывод массива после сортировки
        mov     ah,     09h
        lea     dx,     msgAfter
        int     21h
        lea     dx,     A
        mov     cx,     N
        call    ShowArray
 
        mov     ah,     09h
        lea     dx,     CrLf
        int     21h
 
        mov     ax,     4C00h
        int     21h
main    endp
 
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
 
 
;Вывод массива
;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 - кол. цифр в числе
 
@@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

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

  1. LOCALS: В данном разделе описываются локальные переменные для процедур, которые используются в коде.
  2. .model small, Pascal: Устанавливается модель памяти и формат исходного кода.
  3. .stack 1000h: Выделение памяти для стека.
  4. .data: Объявление сегмента данных программы.
  5. A: Массив целых чисел для сортировки.
  6. N: Количество элементов в массиве.
  7. CrLf: последовательность символов возврата каретки и перевода строки.
  8. msgBefore: строка с текстом Before sort: для вывода на экран.
  9. msgAfter: строка с текстом After sort: для вывода на экран.
  10. main: Начало процедуры main.
  11. RadixSort: Процедура для двоичной поразрядной сортировки.
  12. arg pBegin:WORD, uiSize:WORD, uiMask:WORD: Параметры процедуры RadixSort.
  13. ShowArray: Процедура для вывода массива.
  14. Show_AX: Процедура для вывода числа из регистра AX на экран.
  15. end main: Окончание процедуры main.

Оцени полезность:

15   голосов , оценка 3.867 из 5
Похожие ответы