__________________________________________
Привет. Как-то 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) за помощь.
И еще раз: главное в нашем деле -
оптимизация! Тут уж сами выкручивайтесь.
__________________________________________
