Написать код реализации быстрой сортировки - Assembler

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

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

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

Решение задачи: «Написать код реализации быстрой сортировки»

textual
Листинг программы
@stack  segment para stack
        db      1024 dup(?)
@stack  ends
 
@data   segment
        MsgBefore       db      'Before sort:', 0Dh, 0Ah, '$'
        MsgAfter        db      'After sort:', 0Dh, 0Ah, '$'
        CrLf            db      0Dh, 0Ah, '$'
 
        N               dw      10
        Array   dw       -3,-78, 53, 68,-56,-91,-53, 69, 29,-25
 
@data   ends
 
@code   segment
        assume  cs:@code, ds:@data, ss:@stack
main    proc
        ;инициализация сегментного регистра данных
        mov     ax,     @data
        mov     ds,     ax
        ;показать массив перед сортировкой
        mov     ah,     09h
        lea     dx,     [MsgBefore]
        int     21h
        mov     cx,     [N]
        lea     dx,     [Array]
        call    ShowArray
        mov     ah,     09h
        lea     dx,     [CrLf]
        int     21h
        ;сортировка массива
        mov     cx,     [N]
        lea     dx,     [Array]
        call    QuickSort
        ;показать массив после сортировки
        mov     ah,     09h
        lea     dx,     [MsgAfter]
        int     21h
        mov     cx,     [N]
        lea     dx,     [Array]
        call    ShowArray
        mov     ah,     09h
        lea     dx,     [CrLf]
        int     21h
 
        ;завершение программы
        mov     ax,     4C00h
        int 21h
main    endp
 
;Вывод массива слов (word)
;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
 
; выводит знаковое 16-разрядное число из регистра 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
 
;Быстрая сортировка
;на входе:
;  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 = s_arr[left];
                                ;                s_arr[left] = s_arr[right];
                                ;                s_arr[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:
                                ;        qs(s_arr, first, right);
        mov     cx,     si
        pop     si
        call    qsort
                                ;        qs(s_arr, 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                    ;}
 
 
 
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
 
@code   ends
 
        end     main

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

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

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