На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! Перед отправкой сообщения внимательно прочтите правила раздела!!!
1. Все статьи должны быть оформлены согласно Правил оформления статей.
2. Любые обсуждения должны происходить в специальной теме, обсуждение в любых других темах раздела запрещены.
3. Запрещается писать статьи о создании и распространении вирусов, троянов и других вредоносных программ!
4. За грамотно написанные и правильно оформленные статьи авторы награждаются DigiMoney.

Дополнительные ссылки:
Желаю творческих успехов! ;)
Модераторы: Jin X
  
    > Умная быстрая сортировка , TASM/MASM, DOS, Sort

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

      Заморочился и сделал не просто быструю сортировку, но ещё и умную :)

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

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

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

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

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

      Модуль умной быстрой сортировки для массивов с одиночными элементами IQSortS1.inc:
      ExpandedWrap disabled
        ;##################################################
        ;##                                              ##
        ;##        [ 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:
      ExpandedWrap disabled
        ;##################################################
        ;##                                              ##
        ;##        [ 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:
      ExpandedWrap disabled
        ;##################################################
        ;##                                              ##
        ;##        [ 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:
      ExpandedWrap disabled
        ;##################################################
        ;##                                              ##
        ;##        [ 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

      Вызов:
      ExpandedWrap disabled
                lea dx,Array        ; DS:DX = адрес массива
                mov cx,Count        ; CX = кол-во элементов массива
                call    IQSort      ; вызов процедуры умной быстрой сортировки

      Настройка и добавление модуля IQSort.inc:
      ExpandedWrap disabled
          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 Кбайт, скачиваний: 171)
        Сделана ещё одна коллекция модулей сортировки. Полная копия описанных выше, но работающая с 32-битными элементами! :victory:

        Теперь вы можете использовать дальние указатели во втором двойном слове, либо 2 ближних указателя, а также 32-битные элементы в первом (опорном) двойном слове (в котором можно расположить, например, дату рождения).
        Например:
        ExpandedWrap disabled
          +0  BYTE  День рождения
          +1  BYTE  Месяц рождения
          +2  WORD  Год рождения
          +4  WORD  Ближний указатель на фамилию
          +6  WORD  Ближний указатель на имя

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

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

        ExpandedWrap disabled
          ;##################################################
          ;##                                              ##
          ;##        [ 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 Кбайт, скачиваний: 162)
        0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
        0 пользователей:


        Рейтинг@Mail.ru
        [ Script execution time: 0,0739 ]   [ 17 queries used ]   [ Generated: 19.03.24, 03:39 GMT ]