Радио-86РК/Радио 03-91/Сортировка

Материал из Emuverse
Данный материал защищён авторскими правами!

Использование материала заявлено как добросовестное, исключительно для образовательных некоммерческих целей.

Автор: M. ОВЕЧКИН

Источник: http://retro.h1.ru/RK86/Programm/Sort.html

Каталоги, таблицы, справочники, результаты соревнований, QSL-почта, списки деталей — вот далеко не полный перечень информации, требующий сортировки. Конечно, список из 20 строк можно привести в порядок редактором ED. «МИКРОН» с помощью директивы (AP2+S). Но и в этом случае упорядочение, скажем, по первым восьми позициям уже представляет определенную трудность. А если текст имеет 500 строк и отсортировать его требуется по нескольким признакам? Очевидно, необходимо иметь специальную программу, способную взять эту утомительную работу на себя.

Программа «SORT UT», машинные коды и поблочные контрольные суммы которой приведены соответственно в табл.1 и 2, и предназначена для этих целей.

Таблица 2

ДАМП 	КОНТР. СУММА
800-8FF 	0F7B
900-9FF 	F638
A00-AFF 	Е979
B00-BFF 	4ЕЕ7
C00-CFF 	ЕА40
D00-DFF 	7860
Е00-Е95 	4019 
800-E95 	3E09

Принцип сортировки основан на пузырьковом методе, суть которого заключается в том, что наиболее «легкие строки» списка (по их весу кода ASCII) благодаря взаимному обмену с соседними строками «всплывают» на «поверхность», а тяжелые, наоборот, «падают» на «дно» списка.

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

После окончания сортировки автоматически происходит «сжатие строк» — операция, обратная предыдущей, удаляющая все незначащие пробелы из всех строк, и, также как и в предыдущем случае, в «SORT UT» предусмотрен самостоятельный режим сжатия строк — директива (—).

Может оказаться необходимым до или после сортировки пронумеровать строки списка — для этого предназначена директива (N), вставляющая в начале строки ее порядковый номер (от 0001 до 0999). Номер впечатывается прямо «поверх строки», поэтому часть информации утрачивается. Чтобы этого не произошло, сортируемый список перед нумерацией необходимо сдвинуть вправо на 5 позиций — этим, даже в несколько большем объеме, в программе «SORT UT» занимается директива </>— сдвиг строк.

Загружают текстовый файл, подлежащий обработке, редактором ED. «МИКРОН». Запускают программу «SORT UT» командой G800 или директивой (СТР) редактора. Передать управление из программы «SORT UT» обратно редактору можно директивой (Е).

После запуска программа выводит на экран основное меню:

  • <S> — сортировка
  • <=> — расширение
  • <—> — сжатие
  • </> — сдвиг

Ввод директив возможен после появления на экране точки, но может оказаться, что на экран будет выведено два вопросительных знака — «??». Это означает, что либо размер текстового файла превышает 74FFH, либо одна из строк в нем содержит более 63 символов. Последнее случается, как правило, при отсутствии самого файла.

Введем, например, директиву <S>. Выбор подтвердиться «загоранием» квадратика левее соответствующей строки меню. Надо отметить, что все операции дублируются вопросом — «УВЕРЕН?». Для продолжения выполнения операции следует ответить утвердительно — «Y». Нажатие любой иной клавиши вызывает перезапуск программы.

Спустя некоторое время, необходимое для автоматического расширения строк сортируемого списка и вычисления его конечного адреса, на экране возникает меню сортировки:

В следующей строке на экран будет выведен конечный адрес расширенного списка. Следом за ней — первая строка списка, а еще ниже выводится строка точек, «символизирующая» все доступные позиции, с которых может быть начата сортировка.

Нажатием соответствующей клавиши выбирают вид сортируемого списка: русский (Р) или латинский (L), а клавиши «+» — «направление» сортировки. Далее пользуясь клавишами управления курсором «->», «<-», выведенной на экран первой строкой списка и строкой всех доступных позиций устанавливают курсор в нужную позицию и нажимают клавишу «ВК». Появлением над курсором прямоугольника позиция будет «утверждена». Это означает, что код символа в данной позиции строки будет сравниваться с кодом символа, находящегося в такой же позиции следующей строки. При их совпадении будут сравниваться следующие (справа) позиции и далее, вплоть до конца строки. Осталось на вопрос «УВЕРЕН?» ответить «Y» и ждать результатов сортировки — окончание всех операций индицируется звуковым сигналом и выводом на экран начального фрагмента (23 строки) обработанного текста.

Как уже упоминалось выше, в некоторых случаях может понадобиться сдвиг всех строк списка на определенное количество позиций вправо или влево. После выбора в основном меню режима сдвига на экран выводится меню сдвига:

  • <Z> — позиция
  • < — влево
  • > — вправо
  • <N> — нумерация

При нажатии клавиши «Z» появляется запрос Z 1…9? и мигающий курсор приглашает к вводу необходимого значения. После задания направления сдвига и подтверждения выбора текст будет сдвинут в соответствующую сторону на заданное число позиций. Если ограничится выбором только направления сдвига, то текст будет по умолчанию сдвинут на пять позиций. После сдвига текст может быть тут же пронумерован (директива <N> находится в меню сдвига), впрочем, это можно сделать и до сдвига текста.

Для желающих разобраться в алгоритме сортировки русскоязычного списка может оказаться полезной табл.3, а также следующая информация. Начальный адрес текстового буфера 2100Н находится в ячейках 0D3FH, 0D40H, адрес верхней границы допустимой области ОЗУ — в ячейках 0CDFH, 0СЕ0Н. В ячейках 815Н, 816Н — начало области ОЗУ, занимаемое стеком.

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

  • При расширении и сдвиге вправо на экран выводится конечный адрес ОЗУ, который займет будущий файл. Если он превышает значение 74FFH, выводится сообщение: «МАЛО ПАМЯТИ», операция не проводится.
  • Сортировка и расширение не проводятся, если список состоит только из символов «ВК».
  • Сдвиг запрещен, если в результате операции может произойти потеря строки, то есть число позиций в одной из строк может стать меньше 1 или, наоборот, больше 63. В этом случае на экран выводится сообщение: «63 <<1 ?»
  • Нумерация занимает пять первых позиций в каждой строке. Если строка короче, то нумерация не проводится, а на экран будет выведено: «<5*??».

M. ОВЕЧКИН, г. Серпухов

Отсканировано с журнала Радио № 3 1991 г.
Отредактировано Лесных Ю.