Устройство для сортировки чисел

 

Изобретение относится к авто матике и вычислительной технике. Цель изобретения - расширение области применения за счет обеспечения возможности сортировки массивов неограниченной длины. Устройство содержит счетчики, триггеры, блок сравнения, блок вьщеления крайней единицы, генератор импульсов, сумматор-вычита тель, элементы И, ИЛИ, ИЛИ-НЕ, 2И- ШШ, дифференцирующие элементы. Первые m чисел записываются в счетчики. содержимое которык начинает уменьшаться по единице, одновременно в выходном счетчике происходит подсчет импульсов. В момент установления в некотором счетчике нуля содержимое выходного счетчика выводится во внешнее запоминающее устройство (ВЗУ), а в освободившийся счетчик заносится следующее число из массива. Если вновь заносимое число больше, чем только что выведенное, перед записью в счетчик оно уменьшается на величину только что выведенного числа, если меньше - то записьгеается без, изменения в счетчик, который затем маскируется нулевым состоянием триггера блокировки. Когда все счетчики окажутся замаскированными, они размаскируготся, и процесс повторяется с вывода в ВЗУ нового-отрезка отсортированных чисел. После сортировки всего массива процесс повторяется, при этом числа последовательно берутся из всех ранее отсортированных отрезков . 1 ил. (Л со vi 00 СП ю

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (51) 4 С 06 F 7/08

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ.(2i) 4033273/24-24 (22) 06.03.86 (46) 29.02.88. Бюл. № 8 (72) С.Н.Ткаченко, В.И.Ярмонов, С.П. Козий, Ю.В. Перколаб, Г.А. Макаров и А.А. Касьянов (53) 681.325.5(088.8) (56) Авторское свидетельство СССР

¹- 911513, кл. G 06 F 7/06, 1980, Авторское свидетельство СССР № 993251, кл. С 06 F 7/08, 1981. (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ (52) Изобретение относится к автоматике и вычислительной технике.

Цель изобретения — расширение области применения эа счет обеспечения возможности сортировки массивов неограниченной длины. Устройство содержит счетчики, триггеры, блок сравнения, блок выделения крайней единицы, генератор импульсов, сумматор-вычита» тель, элементы И, ИЛИ, ИЛИ-НЕ, 2ИИЛИ, дифференцирующие элементы. Первые ш чисел записываются в счетчики, „„SU„„1377852 А 1 содержимое которых начинает уменьшаться по единице, одновременно в выходном счетчике происходит подсчет импульсов. В момент установления в некотором счетчике нуля содержимое выходного счетчика выводится во внешнее запоминающее устройство (ВЗУ), а в освободившийся счетчик заносится следующее число из массива. Если вновь заносимое число больше, чем только что выведенное, перед записью в счетчик оно уменьшается на величину только что выведенного числа, если меньше — то записывается без, изменения в счетчик, который затем маскируется нулевым состоянием триггера блокировки. Когда все счетчики окажутся замаскированными, они размаскируются, и процесс повторяется с вывода в ВЗУ-нового отрезка отсортированных чисел. После сортировки всего массива процесс повторяется, при этом числа последовательно берутся из всех ранее отсортированных отрезков. 1 ил, 1377852

Изобретение относится к автоматике и вычислительной технике, Цель изобретения — расширение области применения за счет обеспечения возможности сортировки массивов не5 ограниченной длины.

На чертеже представлена схема устройства.

Устройство содержит группу счетчи- 1р кав 1, — 1, где m — количество одновременно сортируемых чисел, выходной счетчик 2, триггеры блокировки

3„- 3 группы, триггер 4 управления, сумматор-,вычитатель 5, блок 6 выде- 15 ления крайней единицы (БВКЕ), генератор 7 импульсов, блок 8 сравнения, группы элементов И 9, — 9, 10, 11 —

i1„, группу элементов ИЛИ 12, — 12 группу дифференцирующих элементов 20

13, — 13, элементы И 14-16, элемент

ИЛИ 17, элемент 2И-ИЛИ 18, элемент

ИЛИ-НЕ 19, группу информационных входов 20, входы 21 и 22 запуска и оста-, нова, группу информационных выходов 25

23, выход 24 синхронизации и выход 25 окончания работы 25..

Единичный сигнал на выходе блока 8 сравнения формируется при наличии единичного сигнала на его управляю- 30 щем входе и если F, > F>,, где Г,, F, — числа, находящиеся соответственно в счетчике 2 и поступающие на вход

20. Сумматор-вычитатель.5 формирует разность F5 = F „— FклЕ, rpe сигнал на выходе блока 8 сравнения.

БВКЕ 6 формирует единичный .сигнал на выходе с минимальным номером из тех входов, на которых присутствуют единичные сигналы. Предварительно счет40 чики 1, 2 установлены в нулевое состояние, триггеры 3, 4 — в единичное.

Устройство работает следующим образом, После запуска по входу 21 генератора 7 импульсов сортируемые числа, предварительно поступающие по входу

20, без изменения проходят через сумматор-вычитатель 5 и записываются последовательно в счетчики 1„- 1 (после записи числа в счетчик 1 . 50 где 1 = 1, 2. ..,, m — - 1, на инверсном выходе элемента ИЛИ 12 присутствует нуль и единичный сигнал будет сформирован на (1 + 1)-м выходе БВКЕ

6) по импульсу от генератора 7 им- 55 пульСов, проходящему через элемент

2И-ИЛИ 18 на входы синхронизации всех счетчиков 1. После записи числа в счетчик 1„ единичный сигнал, сформированный на прямом выходе элемента

ИЛИ 12 „, установит триггер 4 в нулевое состояние.

Затем импульсы от генератора 7 поступают на вычитающие входы счетчиков 1 и суммирующий вход счетчика 2.

Через некоторое время в счетчике 2 окажется записанным минимальное из

m чисел, а в некотором счетчике 1 —

"0", который распознается элементом

ИЛИ 12>. При этом выделенное число, сопровождаемое синхроимпульсом на выходе 24, поступает на выходы 23 устройства и записывается во внешнее запоминающее устройство (ВЗУ). В освободившийся счетчик 1 заносится следующее число из сортируемого массива, При этом возможны два варианта.

Если вновь вводимое число не меньше числа, накопленного в счетчике 2, т.е. F „> F, что определяется блоком 8 сравнения, то вычисляется разность

F — Г,,, которая заносится в счетчик 1, и работа устройства продолжается. Если же Г„ F<, это означает, что число F, должно находиться среди уже записанных во ВЗУ чисел.

В этом случае числа F, без изменения записывается в .счетчик 1, а триггер

3 устанавливается в нулевое состояние, чем блокируется уменьшение числа, записанного в счетчик 1 . Процесс сортировки продолжается без учета этого числа. ь ь

Через некоторое время все триггеры 3, — 3 будут установлены в нулевое состояние, что распознается элементом ИЛИ-HE 19, сигналы на выходе ко" торого устанавливаются в единичное состояние, все триггеры 3 „ — 3„, счетчик 2 устанавливаются в "0", а устройство,начинает формировать следующий отрезок отсортированных чисел и выводить его на ВЗУ.

После просмотра всего массива числа на вход 20 устройства начинают поступать числа последовательно из всех отсортированных отрезков, при этом устройство функционирует аналогично, Далее процесс повторяется до тех пор, пока в ВЗУ не будет записан естественный отрезок, являющийся отсортированным массивом. (377852

Ф о р м у и а и з о б р е т е н и я

Устройство для сортировки чисел, содержащее группу из m счетчиков, где m Ko H eoT o o HoB eM HHo cop5 тируемых чисел, выходной счетчик, первую группу из ш элементов И, вторую группу из и элементов И, где п —разрядность сортируемых чисел, груп- .10 пу из m дифференцирующих элементов, элемент ИЛИ, группу из m элементов

ИЛИ и первый элемент И, выход которого соединен с первыми входами элементов И первой группы, и суммирующим входом выходного счетчика, выход 1го разряда которого, где j = 1,. 2, и, соединен с первым входом

j-ro элемента И второй группы, выход которого является выходом j-ro раз- 20 ряда отсортированного числа устройства, выход i-ro элемента И первой группы, где i = 1, 2 ..., m, соединен с вычитающим входом i-го счетчика группы, выход j-ro разряда которого соединен,с j-входом i-элемента

ИЛИ группы, прямой выход которого соединен с вторым входом i-го элемента И первой группы, выход i-го диф30 ференцирующего элемента группы соединен с i-м входом элемента ИЛИ, выход которого соединен с вторыми входами элементов И второй группы, о тл и ч а ю щ е е с я тем, что, с целью расширения области применения за счет обеспечения возможности сорти-- 5 ровки массивов неограниченной длины, в него введены генератор импульсов, сумматор-вычитатель, блок выделения крайней единицы, блок сравнения, триггер управления, группа из ш тригге- 40 ров блокировки, третья группа из m элементов И, элемент ИЛИ-HE второй и третий элементы И и элемент 2И-ИЛИ, причем входы запуска и останова устройства соединены соответственно с 45 входами запуска и останова генератора импульсов, выход которого соединен с прямым входом первого элемента И и первыми прямыми входами первого и второго элементов И элемента 2И-ИЛИ, 50 вторые прямые входы которых подключены соответственно к инверсному и прямому выходам триггера управления, вход установки в нулевое состояние которого подключен к выходу второго элемента И, прямой вход которого подключен к прямому выходу m-го элемента

ИЛИ группы, инверсный выход i-го элемента ИЛИ группы соединен с i -м входом третьего элемента И, входом i-го дифференцирующего элемента первым входом i-го элемента И третьей группы и i — м входом блока вьщеления крайней единицы, -й выход которого соединен с входом разрешения записи -ro счетчика группы, выход элемента ИЛИ является входом синхронизации устройства и соединен с инверсными входами первого и второго элементов И и первого элемента И элемента 2И-ИЛИ, выход которого соединен с входами синхронизации счетчиков группы и инверсным вхо-. дом элемента ИЛИ- HE выход которого соединен с входами установки в единичное состояние триггеров блокировки группы и входом установки в нулевое состояние выходного счетчика, выходы разрядов которого соединены с первой группой информационных входов блока сравнения и группой входов вычитаемого сумматора-вычитателя, группа входов уменьшаемого которого обьединены с второй группой информационных входов блока сравнения и является группой информационных входов устройства, инвеРсный выход триггера управления соединен с входом разрешения суммирования выходного счетчика.и управляющим входом блока сравнения, выход которого соединен с вторыми входами элементов И третьей группы и управляющим входом сумматора-вычитателя, выходы которого соединены с соответствующими информационными входами счетчиков группы, выход i-го элемента И -третьей группы соединен с входом установки в нулевое состояние i-го триггера блокировки группы, прямой выход которого соединен с третьим входом i-ro элемента И первой группы и с i-м прямым входом элемента ИЛИ-НЕ, выход третьего элемента

И является выходом окончания работы устройства.

1377852

Составитель В, Горохов

Техред М. Ходанич

Редактор М. Келемеш

Корректор В, Бутяга

Заказ 875/46 Тираж 704

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д, 4/5

Подписное

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4