Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.144.102.239] |
|
Сообщ.
#1
,
|
|
|
Умная быстрая сортировка Заморочился и сделал не просто быструю сортировку, но ещё и умную Алгоритм работы умной сортировки заключается в следующем. По умолчанию используется быстрая сортировка, однако если кол-во элементов массива на первой или последующей итерации меньше некоего порогового значения (по умолчанию 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) ## ;## ## ;## (c) 2017 by Jin X (jin.x@sources.ru) ## ;## 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) ## ;## ## ;## (c) 2017 by Jin X (jin.x@sources.ru) ## ;## http://xk7.ru/p/a/i ## ;## ## ;################################################## IFDEF ??Version ; TASM LOCALS ENDIF IQSortS2_ver = 100h ; версия данного модуля (word: старший байт - целая часть, младший - дробная) ; !!! В данном модуле используется ЗНАКОВОЕ сравнение значений и сортировка по ВОЗРАСТАНИЮ (от меньшего к большему) ; !!! Для замены на БЕЗзнаковое сравнение или сортировку по УБЫВАНИЮ необходимо изменить соответствующие инструкции, помеченные в комментариях символами *** ; IQSortInsThrs = порог использования сортировки вставками (когда кол-во элементов меньше указанного здесь значения) [минимум 2; по умолчанию 16] ; Если кол-во элементов (на первой или последующей итерации) больше или равно значению IQSortInsThrs, используется быстрая сортировка, иначе ; используется сортировка вставками - это немного ускоряет процесс (при правильном выборе значения IQSortInsThrs, например, при значении по умолчанию) ; и уменьшает глубину рекурсии, защищая стек от переполнения IQSortInsThrs = 16 ; IQSortMaxStk = максимальный размер стека в байтах, который допустимо использовать процедуре IQSortDE (включая call из основного кода) [минимум 12; по умолчанию 128] ; Каждый уровень вложенности использует 4 байта (2 слова) стека (первый уровень - до 4-х слов, последний может использовать на 2 слова больше, итого минимум 12 байт), ; т.о. 128 байт позволяют организовать до 30 уровней рекурсии, что достаточно даже для очень больших массивов IQSortMaxStk = 128 ;----------------------------------------------------------------------------------------------------------------------- ;-- IQSortDE: Умная БЫСТРАЯ СОРТИРОВКА массива (комбинированным методом) ----------------------------------------------- ; > Входные данные: DS:DX = адрес массива, CX = кол-во элементов массива (знаковое значение) ; > Результат: отсортированный массив (по тому же адресу) ; Элементы массива содержат по 2 значения типа WORD: ; * первое слово содержит опорное значение (по которому происходит сравнение), ; * второе слово - связанные с элементом данные (обычно это указатель на данные); ; при сортировке связанные данные переносятся вместе с опорными значениями ; Если кол-во элементов (на первой или последующей итерации) больше или равно значению IQSortInsThrs, используется быстрая сортировка, ; иначе используется сортировка вставками ; Сортировка вставками также используется, если для следующего уровня рекурсии потребуется более IQSortMaxStk байт стека в общем сложности ; Процедура изменяет регистры 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 jl @@addI ; {*** сортировка по возрастанию: jl - знаковое сравнение, jb - беззнаковое; по убыванию: jg - знаковое, ja - беззнаковое} jmp @@cmpJ @@subJ: sub di,4 ;; 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 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 jle @@break ; прыгаем, если [I] <= T {*** сортировка по возрастанию: jle - знаковое сравнение, jbe - беззнаковое; по убыванию: jge - знаковое, jae - беззнаковое} 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) ## ;## ## ;## (c) 2017 by Jin X (jin.x@sources.ru) ## ;## 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 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 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) ## ;## ## ;## (c) 2017 by Jin X (jin.x@sources.ru) ## ;## 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 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 Вызов: 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 (79,64 Кбайт, скачиваний: 175) |
Сообщ.
#2
,
|
|
|
Сделана ещё одна коллекция модулей сортировки. Полная копия описанных выше, но работающая с 32-битными элементами!
Теперь вы можете использовать дальние указатели во втором двойном слове, либо 2 ближних указателя, а также 32-битные элементы в первом (опорном) двойном слове (в котором можно расположить, например, дату рождения). Например: +0 BYTE День рождения +1 BYTE Месяц рождения +2 WORD Год рождения +4 WORD Ближний указатель на фамилию +6 WORD Ближний указатель на имя Сортировка будет идти по дате рождения, а указатели на строку с фамилией и именем будут переноситься вместе с датой. Правда, здорово? Если 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+) ## ;## ## ;## (c) 2017 by Jin X (jin.x@sources.ru) ## ;## 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 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 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 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 (81,06 Кбайт, скачиваний: 165) |