Сортировка массивов алгоритмом "пузырька"

Сортировка массивов алгоритмом пузырька на ASM

Йол напок киванок! Вот и добрались мы с Вами до "программистских дебрей" - асемблера. Помнится, купил я книгу "учебник для ВУЗ-ов и для профессионалов" (бр-р-р). В этом "учебнике" дается такой листинг "алгоритма, похожего на метод пузырька"... Нет, у автора нет чувства экономии :-) Я попытался его (алгоритм) укоротить.

Итак, начнем с алгоритма пузырька (кто знает - можно пропускать).

Алгоритм:

1. Проверяется: конец массива? Если да - заканчиваете алгоритм. Если нет - переходите к п. 2

2. Берете текущий элемент массива

3. Берете следующий элемент массива

4. Сравниваете их: если первый меньше за второй - п.5, если больше - п.7

5. Меняете их между собой

6. Число, по которой Вы берете текущий элемент равно -1

7. Увеличиваете цифру, по которой Вы берете текущий элемент на 1

8. Переходите к п.1

Этот алгоритм медленный, зато легек в написании. Листинг-пример на С++:

#include <iostream.h>

int main(int argc, char* argv[])
{

int i = 0, tmp = 0;
int mas[5] = {0,9,8,4,3};

while(i<5)
{
if(mas[i]<mas[i+1])
{
tmp = mas[i+1];
mas[i+1] = mas[i];
mas[i] = tmp;
i=0;
}
i++;
}

return 0;
}

Листинг 0

Но это на языке высокого уровня. На Ассемблере не все так просто - там играет роль размер переменной. На С++ или на Pascal начинающий программист может даже не знать размера переменной - компилятор все делает за него. А "поле деятельности" ассемблера - процессор и память, а не ОС. Знание размера переменной, а фактически "знание памяти", играет основную роль.

Название	Разрядность	MIN и MAX
Байт	8 бит	-128; 127
Слово	16 бит	-32768; 32767
Двойное слово	32 бита	-2^31; 2^31
Учетверенное слово	64 бита	-2^63; 2^63

Таб. 1 Размеры памяти

В таблице даны основные целые числа. С дробными разбирается препроцессор - их мы не будем трогать. Рассмотрим только первые две строки (т.е. байт и слово) и Вы поймете почему. В ассемблере (далее ASM) все программирование построено на регистрах. Их немного (порой их даже не хватает). Базовых регистров всего четыре: ay, by, cy, dy (y принимает значения x, h, l). Для примера:

eax -> ax -> al и ah - это значит, что регистры al и ah принадлежат ax, а тот в свою очередь - eax

Я решил пойти рекурсивно (т.е. от конца к началу) - на результате это никак не скажется:

1. Проверяется: начало массива? Если да - заканчиваете алгоритм. Если нет - переходите к п. 2

2. Берете текущий элемент массива

3. Берете предыдущий элемент массива

4. Сравниваете их: если первый больше за втотой - п.5, если меньше - п.7

5. Меняете их между собой

6. Число, по которой Вы берете текущий элемент равно количеству элементов массива

7. Уменьшаете цифру, по которой Вы берете текущий элемент на 1

8. Переходите к п.1

Приведем два листинга (байт и слово) - в них я Вам подробно все обьясню.

; <<<<<<<<<<<<<<<<<<>>>>>>>>>>>>>>>>>
; Anton (Liloi) Moskalenko
; e-mail: liloi@mail.ru
; <<<<<<<<<<<<<<<<<<>>>>>>>>>>>>>>>>>
; Create time & date: 12:39 14.07.2006
; Note: Sorting "bubble" (db)

.model small

; для маленких DOS-программ

.data

; тут я объявляю переменные (сегмент DATA)

mas db -1,3,3,4,50

; объявление массива, типа db (байт), 5 элементов

num db 00005h

; объявление числа элементов массива

.stack 256h

; стек

.code

; а здесь мы будем писАть алгоритм

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
lbubblesortb proc

; объявление процедуры

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

xor cx, cx

;чистим регистр cx

j2:
mov cl, num

; заносим num в cl

dec cl

; отнимаем 1 из cl

c0:
mov bx, cx

; заносим cx в bx

mov al, mas[bx]

; заносим mas[bx] (текущий элемент массива) в al

cmp al, mas[bx-1]

; сравниваем текущий элемент массива с предыдущим

jg j1

; если al (а значит mas[bx]) больше, то перехидим на метку j1

loop c0

; если нет то: if(cx>0) (cx=cx-1, goto c0);

jmp j0

; заканчиваем алгоритм

; Метка j1 меняет текущий и предыдущий элемент мессива

j1:
mov    ah,    mas[bx-1];
mov    mas[bx],    ah
mov    mas[bx-01h],    al
jmp    j2

jmp    c0
j0:
ret

lbubblesortb    endp

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;Main PROC
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
main    proc
mov    ax,    @data
mov    ds,    ax
mov    ah,    09h
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; следующие 11 строк - вывод массива

xor    cx,    cx
xor    bx,    bx
mov    cl,    5
mov    bx,    0

c1:
mov    ah,    02h
mov    dl,    mas[bx]
add    dl,    030h
int    21h
inc    bx
loop    c1

call    lbubblesortb

; вызов процедуры

; следующие 11 строк - вывод отсортированного массива

xor    cx,    cx
xor    bx,    bx
mov    cl,    5
mov    bx,    0

c2:
mov    ah,    02h
mov    dl,    mas[bx]
add    dl,    030h
int    21h
inc    bx
loop    c2

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
mov    ax,    04C00h

; конец программы

int    21h

main    endp
end    main

Листинг 1

Надеюсь Вам все понятно (ASM "обладает" плохой читабельностью). Если же непонятно - скачайте файл с этим листингом и проделайте следующее (на TASM):

tasm /zi [имя файла]
tlink /v [имя объектного модуля]
td [имя exe]

Откроется программа пошагового выполнения (там еще много всяких интересностей). Со вторым листингом выйдет немножко сложнее. Дело вот тут в чем: если у нас в первом случае был массив типа byte (8 бит), то в следующем - массыв тип word (16 бит). Я буду комментировать только отличающиеся комманды.

; <<<<<<<<<<<<<<<<<<>>>>>>>>>>>>>>>>>
; Anton (Liloi) Moskalenko
; e-mail: liloi@mail.ru
; <<<<<<<<<<<<<<<<<<>>>>>>>>>>>>>>>>>
; Create time & date: 14:52 14.07.2006
; Note: Sorting "bubble" (dw)

.model small ;
.data ;

mas dw -2,500,5,-2,-1

; объявление массива, типа dw (слово), 5 элементов

num    db    00005h

.stack    256h ;
.code

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
lbubblesortb    proc
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

xor    cx,    cx
xor    ax,    ax

j2:
mov    cl,    num
dec    cl

; но у нас массив типа dw (2 вместо 1 байта), так что [адрес]*2

mov al, 02h
mul cl

; а можно было поступить проще: shl cx

mov    cl,    al

c0:
mov    bx,    cx
mov    ax,    mas[bx]

; тут уже не al (ah) а ax (al + ah)

cmp    ax,    mas[bx-2]
jg    j1

dec    cx
loop    c0

jmp    j0

; Метка j1 меняет текущий и предыдущий элемент мессива

j1:
mov    dx,    mas[bx-2]
mov    mas[bx],    dx
mov    mas[bx-2],    ax

jmp    j2
j0:
ret

lbubblesortb    endp

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;Main PROC
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
main    proc
mov    ax,    @data
mov    ds,    ax
mov    ah,    09h
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

xor    cx,    cx
xor    bx,    bx
mov    cl,    5
mov    bx,    0

c1:
mov    ah,    02h
mov    dx,    mas[bx]
add    dl,    030h
int    21h
inc    bx
inc    bx
loop    c1

call    lbubblesortb

xor    cx,    cx
xor    bx,    bx
mov    cl,    5
mov    bx,    0

c2:
mov    ah,    02h
mov    dx,    mas[bx]
add    dl,    030h
int    21h
inc    bx
inc    bx
loop    c2

mov    ax,    04C00h
int    21h

main    endp
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

end main

Листинг 2

Эти два листинга транслированны на TASM (и, возможно, MASM) можно скачать: листинг 1 и листинг 2

Это все что я хотел Вам сегодня поведать. Висонтлаташра друзья!