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