Форум на Исходниках.RU

Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=411583&view=findpost&p=3749067 Sat, 11 Nov 2017 19:58:46 +0000 Умная быстрая сортировка https://forum.sources.ru/index.php?showtopic=411583&view=findpost&p=3749067 32-битными элементами! :victory:

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

+0 BYTE День рождения

+1 BYTE Месяц рождения

+2 WORD Год рождения

+4 WORD Ближний указатель на фамилию

+6 WORD Ближний указатель на имя

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

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

;##################################################

;## ##

;## [ 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+) ##

;## ##

;## 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

_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

_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

_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

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

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

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

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

asm7x
IQSort_16bit_DWORD_1.00.zip (, : 234) ]]> Jin X Assembler FAQ https://forum.sources.ru/index.php?showtopic=411583&view=findpost&p=3749026 Sat, 11 Nov 2017 11:09:56 +0000 Умная быстрая сортировка https://forum.sources.ru/index.php?showtopic=411583&view=findpost&p=3749026
Умная быстрая сортировка
Заморочился и сделал не просто быструю сортировку, но ещё и умную :)

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

Иногда при сортировке массивов необходимо упорядочить не только числовые элементы, но и соответствующие им данные. Например, имеется список людей с указанием года рождения и фамилии для каждого из них. Год рождения записан в виде числового значения, а фамилия – в виде указателя на строку. Таким образом, каждый элемент массива будет содержать 2 записи размером WORD каждая:

+0 WORD Год рождения

+2 WORD Адрес (смещение) строки с фамилией

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

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

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

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

;##################################################

;## ##

;## [ Asm7x.List ][ IQSortS1.inc ] ##

;## ##

;## -= Smart Quick Sort =- ##

;## (for single element arrays) ##

;## ##

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

;## (для массивов с одиночными элементами) ##

;## ##

;## [ v1.00 :: 11.11.2017 ] ##

;## MASM/TASM (16 bit) ##

;## ##

;## 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

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

;##################################################

;## ##

;## [ Asm7x.List ][ IQSortS2.inc ] ##

;## ##

;## -= Smart Quick Sort =- ##

;## (for double element arrays) ##

;## ##

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

;## (для массивов с двойными элементами) ##

;## ##

;## [ v1.00 :: 11.11.2017 ] ##

;## MASM/TASM (16 bit) ##

;## ##

;## http://xk7.ru/p/a/i ##

;## ##

;##################################################

IFDEF ??Version ; TASM

LOCALS

ENDIF

IQSortS2_ver = 100h ; версия данного модуля (word: старший байт - целая часть, младший - дробная)

; и уменьшает глубину рекурсии, защищая стек от переполнения

IQSortInsThrs = 16

; IQSortMaxStk = максимальный размер стека в байтах, который допустимо использовать процедуре IQSortDE (включая call из основного кода) [минимум 12; по умолчанию 128]

; Каждый уровень вложенности использует 4 байта (2 слова) стека (первый уровень - до 4-х слов, последний может использовать на 2 слова больше, итого минимум 12 байт),

; т.о. 128 байт позволяют организовать до 30 уровней рекурсии, что достаточно даже для очень больших массивов

IQSortMaxStk = 128

;-----------------------------------------------------------------------------------------------------------------------

;-- IQSortDE: Умная БЫСТРАЯ СОРТИРОВКА массива (комбинированным методом) -----------------------------------------------

; > Входные данные: DS:DX = адрес массива, CX = кол-во элементов массива (знаковое значение)

; > Результат: отсортированный массив (по тому же адресу)

; Элементы массива содержат по 2 значения типа WORD:

; * первое слово содержит опорное значение (по которому происходит сравнение),

; * второе слово - связанные с элементом данные (обычно это указатель на данные);

; при сортировке связанные данные переносятся вместе с опорными значениями

; иначе используется сортировка вставками

; Процедура изменяет регистры 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 = уровень рекурсии

@@IQSortDEMain:

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

jmp @@cmpJ

@@subJ: sub di,4 ;; Dec(J)

@@cmpJ: cmp [di],ax ;; while [J] > T

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 + адрес возврата из InsSortDE + bp

jae @@callins2 ; если число рекурсий достигло максимума, идём на вызов сортировки вставками: InsSortDE(L, J)

inc bp ; иначе увеличиваем глубину рекурсии и идём на рекурсию

jmp @@IQSortDEMain ;; IQSortDE(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 @IQInsSortDE ; вместо call + jmp @@finish делаем push + jmp

@@callins2:

push offset @@recursret ; адрес возврата

jmp @IQInsSortDE ; вместо 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

@IQInsSortDE:

ELSE ; MASM

@IQInsSortDE::

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

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

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

;##################################################

;## ##

;## [ Asm7x.List ][ QSortS1.inc ] ##

;## ##

;## -= Quick Sort =- ##

;## (for single element arrays) ##

;## ##

;## Быстрая сортировка ##

;## (для массивов с одиночными элементами) ##

;## ##

;## [ v1.00 :: 11.11.2017 ] ##

;## MASM/TASM (16 bit) ##

;## ##

;## 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

jmp @@cmpJ

@@subJ: sub di,2 ;; Dec(J)

@@cmpJ: cmp [di],ax ;; while [J] > T

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:

;##################################################

;## ##

;## [ Asm7x.List ][ ISortS1.inc ] ##

;## ##

;## -= Insertion Sort =- ##

;## (for single element arrays) ##

;## ##

;## Сортировка вставками ##

;## (для массивов с одиночными элементами) ##

;## ##

;## [ v1.00 :: 11.11.2017 ] ##

;## MASM/TASM (16 bit) ##

;## ##

;## 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

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

Вызов:

lea dx,Array ; DS:DX = адрес массива

mov cx,Count ; CX = кол-во элементов массива

call IQSort ; вызов процедуры умной быстрой сортировки

Настройка и добавление модуля IQSort.inc:

inclInsSort = 1 ; включить в код полную процедуру сортировки вставками для использования её отдельно от процедуры умной быстрой сортировки (по умолчанию включается только используемая процедурой IQSort часть)

SortSignCmp = 0 ; беззнаковое сравнение

SortAscending = 0 ; сортировка значений по убыванию

SortElemWords = 2 ; элементы массива имеют 2 слова в каждом элементе (допускается использовать только значение 1 или 2)

IQSortInsThrs = 16 ; использовать сортировку вставками для массивов, в которых меньше 16 элементов [это значение установлено по умолчанию]

IQSortMaxStk = 128 ; максимальный размер стека в байтах, который допустимо использовать процедуре IQSort (включая call из основного кода) [это значение установлено по умолчанию]

INCLUDE IQSort.inc ; включить модуль в проект

Хочу заметить, что единственной требуемой настройкой из этого списка является SortElemWords, остальные могут быть опущены – в этом случае используются значения по умолчанию. Подробное описание каждой настройки смотрите в исходниках :)

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

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

asm7x[/COLOR]
IQSort_16bit_1.00.zip (, : 226) ]]> Jin X Assembler FAQ