Demo or Die #02 31 июля 1999

Программирование

Demo-строение - о некоторых методах сортировки.

__________________________________________

    Привет.  Как-то  WOLF  обещал в первом
номере  DEMO OR DIE рассказать о некоторых
методах  сортировки.  Но  в  силу стечения
разных  обстоятельств эту задачу возложили
на меня, Kenotron'a.

    Под сортировкой массива чисел понимают
их   упорядочивание  по  возрастанию.  Эта
задача     является     классической     в
программировании, и существует ряд методов
ее решения. Сделаем небольшой обзор оных.

    1.   Сортировка массива методом
                 'пузырька'

Метод заключается в следующем:

    -  производим  последовательный  прос-
мотр массива и попарно сравниваем соседние
числа, располагая их в порядке возрастания
    -  в  результате  такого  просмотра на
последнем  месте  окажется  самое  большое
число (всплыл 'пузырек');
    -  повторяем эту процедуру до тех пор,
пока   во   время   просмотра   не   будет
произведено НИ ОДНОЙ перестановки.

    Выглядит это примерно так:

;--------------------------------------;
;         Процедура СОРТИРОВКИ         ;
;      одномерного массива чисел       ;
;          методом 'ПУЗЫРЬКА'          ;
;--------------------------------------;
; >: HL=[адрес массива]                ;
;     B=[длина массива]                ;
;--------------------------------------;

        LD HL,DATA
        LD B,10

        DEC B
SORT1   PUSH BC,HL

        LD D,1      ; счетчик перестановок

SORT2   LD A,(HL)   ; сравниваем
        INC HL      ;  соседние
        CP (HL)     ;    числа
        JR C,SORT3
        JR Z,SORT3

        LD C,(HL)   ; вот он где,
        LD (HL),A   ;  поплыл пузырь
        DEC HL
        LD (HL),C
        INC HL

        INC D       ; фиксируем
                    ; перестановку
SORT3   DJNZ SORT2

        POP HL,BC

        DEC D       ; была перестановка?
        JR NZ,SORT1
        RET

DATA    DB 1,9,2,8,3,7,4,6,5,5


Примечание:   здесь   и   далее  приведены
исходники,    написанные    в   ассемблере
STORM by X-Trade (rulez!).

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

    2.  Сортировка  массива  методом
       перестановки (простого выбора)

Вот его суть:

    -  первый элемент массива (X1) сравни-
вается со всеми остальными;
    -  если  на каком-либо этапе сравнения
окажется,   что  X1>Xi,  то  они  меняются
местами;
    -  в  результате  на  месте  X1  будет
стоять наименьший элемент;
    -  теперь  сравнивается X2 с последую-
щими элементами на тех же условиях;
    -  после  этого  просмотра на месте X2
будет стоять число, бОльшее X1, но мЕньшее
всех оставшихся;
    -  далее  проводятся аналогичные срав-
нения  для всех остальных элементов до тех
пор, пока не будут сравнены два последних;
    -  в  итоге  мы  получим  возрастающую
последовательность чисел.

    Это можно изобразить так:

;--------------------------------------;
;         Процедура СОРТИРОВКИ         ;
;      одномерного массива чисел       ;
;        методом 'ПЕРЕСТАНОВКИ'        ;
;--------------------------------------;
; >: HL=[адрес массива]                ;
;     B=[длина массива]                ;
;--------------------------------------;

        LD HL,DATA
        LD B,10

SORT1   PUSH BC,HL

        LD A,(HL)    ; взяли элемент
        DEC B
        JR Z,SORT4   ; конец массива?

SORT2   INC HL
        CP (HL)      ; сравниваем
        JR C,SORT3
        JR Z,SORT3

        LD C,(HL)    ; переставляем
        LD (HL),A
        LD A,C

SORT3   DJNZ SORT2

        POP HL,BC

        LD (HL),A   ; самый маленький :)
        INC HL
        DJNZ SORT1
        RET

SORT4   POP BC,HL
        RET

DATA    DB 1,9,2,8,3,7,4,6,5,5

    По  сравнению с предыдущим, этот метод
работает немного(намного) быстрее.

    3.  Сортировка массива методом
             Дж. фон Неймана

    Пусть   нам  необходимо  отсортировать
последовательность чисел A длиной  N, типа
A(N):

    1)  Установим  некую величину K равную
единице, т.е. K=1;
    2)  Разбиваем последовательность чисел
на ПОДпоследовательности длиной K;
    3)  Объединяем рядом стоящие подпосле-
довательности в одну;
    4)  Делаем K=K*2;
    5)  Если K<N, то переходим к п.2.

По-подробнее:
    Что значит:  РАЗБИВАЕМ  последователь-
ность?   Значит   СОЗДАЕМ,  например,  два
указателя:  i  и j (j=i+K), указывающие на
начала    ПОДпоследовательностей.
    А    ОБЪЕДИНЯЕМ    -   сортируем   две
подпоследовательности  между  собой, т.е.:
A(i)  сравнивается  с  A(j) и, если нужно,
меняются  местами, затем A(i+1) с A(j+1) и
т.д., получая упорядоченную последователь-
ность. При следующем проходе подпоследова-
тельности будут в два раза длиннее.

    Даже не знаю, что сказать о реализации
этого метода на Спектруме. Сделать конечно
можно,   но   как   оно   будет  работать!
Оперировать  не  указателями,  а адресами,
каждый  раз  пересчитывая  их. Ну в общем,
если    долго    мучиться   -   что-нибудь
получиться :)

    4.  Побитовая сортировка массива
                  (BITSORT)

    Очень   даже  быстрый  метод  (говорят
быстрее  чем QUICKSORT), заключается вот в
чем:
    -  создается   два,   так  называемых,
СТЕКА: первый назовем '0', а второй - '1';
    -  дальше берется первое число массива
и  анализируется  его нулевой бит: если он
равен  нулю,  то  число  заносится на стек
'0',  иначе  на стек '1'. И так аналогично
для всех чисел массива;
    -  затем  на  место  исходного массива
переписываются  все  числа из стека '0', а
следом  из  стека  '1'.  Таким  образом мы
получим      последовательность     чисел,
отсортированных по нулевому биту;
    -  ну   а  дальше   массив  аналогично
сортируется  по  первому  биту,  и т.д. до
последнего. Все, сортировка закончена.

    Вроде   все  просто,  но  на  практике
сортировать по биту бывает иногда медленно
(особенно  если  вы  сортируете  16-ти или
32-х  битовые числа). Поэтому анализ можно
проводить  сразу  по  двум,  трем  и более
битам    (чтобы    уменьшить    количество
проходов),      создавая      при     этом
соответственное    (4,8,...)    количество
стеков (что требует бОльше памяти).
    На   Спектруме   такой   метод   можно
применить  в случае анализа сразу 8 битов,
т.е.   байта.   В  связи  с  этим  битовая
сортировка    'вырождается'   в   БАЙТовую
(bytesort),   для  которой  необходимо  аж
256(!) стеков.

    И    тут    возникает   идея   сделать
сортировку,   результатом  работы  которой
будет  массив  чисел  в упакованной форме,
т.е.:
    что   если  в  каждый  из  256  стеков
записывать  не сами числа, а их КОЛИЧЕСТВО
повторений  в  массиве, а 0 на стеке будет
значить,  что  такого  числа  вообще нет в
массиве! Это выглядит примерно так:

    -  для  начала необходимо обнулить все
256  стеков,  расположенных с адреса #xx00
(это конечно займет времени, но для такого
дела не жалко);
    -  берем  первое число из массива, оно
указывает   нам  номер  стека,  содержимое
которого увеличиваем на 1;
    -  повторяем   аналогично   для   всех
остальных чисел;
    -  в результате с адреса #xx00 получа-
ем отсортированную упакованную  последова-
тельность.

    Не  знаю, может Вы и придумаете как ее
(последовательность)  использовать в таком
виде,  но  при  большом  желании  ее можно
распаковать   в   любое  место,  что  тоже
отнимет кусок времени ;-(
    Но   есть   еще  и  одно  ограничение:
повторяемость  какого-либо числа не должна
превышать  255.  Хотя  это  можно  обойти,
сделав стеки двухбайтовыми.
    В    качестве   примера   предлагается
программка,    реализующая   вышеописанную
идею.   Программа   рабочая,  но  подлежит
оптимизации :)

;--------------------------------------;
;         Процедура СОРТИРОВКИ         ;
;      одномерного массива чисел       ;
;          методом 'BYTESORT+'         ;
;--------------------------------------;
; >: HL=[адрес массива]                ;
;    BC=[длина массива]                ;
;                                      ;
; <: #8000..#81FF: 256 стеков (packed) ;
;    #C000.. : отсортированный массив  ;
;--------------------------------------;

        LD HL,DATA
        LD BC,10

        DI
        PUSH HL
        PUSH BC

        LD (NORMA+1),SP
        LD SP,#8200     ; чистим стеки
        LD HL,0         ; всего 512 байт
.255    PUSH HL
        PUSH HL
NORMA   LD SP,0

        POP DE
        POP BC
        LD H,#80

SORT    LD A,(DE)    ; собственно
        LD L,A       ;   сортировка с
        INC (HL)     ;      упаковкой
        JR NZ,SORT1
        INC H        ; если чисел >255 -
        INC (HL)     ; изменяем старший
        DEC H        ; байт
SORT1   INC DE
        DEC BC
        LD A,B
        OR C
        JP NZ,SORT

        LD DE,#8000  ; а это распаковка
        LD HL,DEP_3
        LD C,E
        EXX
        LD BC,#C000  ; вот сюда
        LD DE,OPEN_CL-2
        EXX

DEP_2   INC D
        LD A,(DE)    ; сначала смотрим
        DEC D        ; старший байт
        OR A
        LD B,A
        LD A,E
        JP Z,BYTE_D
DEP_1   EXX
        CALL OPEN_CL
        DJNZ DEP_1

BYTE_D  EX AF,AF
        LD A,(DE)    ; а потом - младший
        INC E
        NEG          ; это проверка на 0:
        JR Z,DEP_3   ; есть ли такое число
        PUSH HL
        EXX
        LD H,0       ; рассчитываем
        LD L,A       ; прыжок в
        ADD HL,HL    ; раскрытый цикл
        ADD HL,DE
        EX AF,AF
        PUSH HL
        RET

DEP_3   DEC C
        JP NZ,DEP_2
        EI
        RET

OPEN_CL                  ; это раскрытый
.255    LD (BC),A:INC BC ; цикл распаковки
        EXX
        RET

DATA    DB 1,9,2,8,3,7,4,6,5,5

    Была  поставлена  задача отсортировать
массив  из  60  чисел,  и  вот  результаты
тестирования:
    BYTESORT с распаковкой показала лучшие
результаты  -  чуть  меньше 1/2 прерывания
(около  30000  тактов, frame! :) Причем на
сортировку приходится лишь 14(!) процентов
всего    времени,    остальное    занимает
распаковка.  Интересно  заметить,  что при
увеличении  длины массива время сортировки
пропорционально   увеличивается,  а  время
распаковки растет медленнее!
    Метод   перестановки    проявил   себя
немного  хуже  -  чуть  больше  прерывания
(эдак  тысяч 85 тактов), и это всего-то на
каких-то 60 байт!
    Метод  пузыря  затратил...  аж 3 (три)
прерывания! Без коментариев.

    Я  думаю,  методу  BIT/BYTE sort можно
найти применение.

    Существует  еще  очень много различных
методов сортировки, рассматривание которых
выходит     за    рамки    этой    статьи,
ориентированной на возможности SPECCY.

    При  написании данного текста частично
были     использованы     материалы     из
RU.ALGORITHMS.   Спасибо   также  Копытину
Павлу (DIZZY) за помощь.

    И  еще  раз:  главное  в  нашем деле -
оптимизация! Тут уж сами выкручивайтесь.
__________________________________________