Устройство для сортировки чисел Советский патент 1988 года по МПК G06F7/08 

11377852

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

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

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

в счетчик 1 единичный сигнал, сформированный на прямом выходе элемента ИЛИ 12 , установит триггер 4 в нулевое состояние.

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

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

Устройство содержит группу счетчи- д окажется записанным минимальное из

ков 1,1 j, где m - количество одm чисел, а в некотором счетчике 1 О, который распознается элементом ИЛИ . При этом выделенное число, сопровождаемое синхроимпульсом на в

новременно сортируемых чисел, выходной счетчик 2, триггеры блокировки 3,- 3„ группы, триггер 4 управления, сумматор-вычитатель 5, блок 6 выделения крайней единицы (БВКЕ), генератор 7-импульсов, блок 8 сравнения, группы элементов И 9,- 9п,, 10, 1Ь- группу элементов ШШ 12,- 12„, группу дифференцирующих элементов 13,- 13„, элементы И 14-16, элемент

35

ИЛИ 17, элемент 2И-ИЛИ 18, элемент ШШ-НЕ 19, группу информационных входов 20, входы 21 и 22 запуска и останова, группу информационных вькодов 25 23, выход 24 синхронизации и выход 25 окончания работы 25,

Единичный сигнал на выходе блока 8 сравнения формируется при наличии единичного сигнала на его управляю- ЗО щем входе и если F F , где F,, - числа, находящиеся соответственно в счетчике 2 и поступающие на вход 20. Сумматор-вычитатель 5 формирует разность FS F20- Р,лР, где Fg - сигнал на выходе блока 8 сравнения. БВКЕ 6 формирует единичный .сигнал на выходе с минимальным номером из тех входов, на которых присутствуют еди-. ничные сигналы. Предварительно счетчики 1, 2 установлены в нулевое состояние, триггеры 3, 4 - в единичное.

Устройство работает следующим об- разом.

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

15

20

40

45

50

55

5

5

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

Если вновь вводимое число не меньше числа, накопленного в счетчике 2,. т.е.

0

5

0

5

F ,,,, F,, что определяется блоком 8 сравнения, то вычисляется разность F, - F2(, которая заносится в счетчик 1;/, и работа устройства продолжается. Если же FIO Р/г означает, что.число F,должно находиться среди уже записанных во ВЗУ чисел. В этом случае число , без изменения записывается в .счетчик , а триггер 3 устанавливается в нулевое состояние, блокируется уменьшение числа, записанного в счетчик 1. Процесс сортировки продолжается без учета этого числа,

6

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

После просмотра всего массива числа на вход 20 устройства начинают поступать числа последовательно из всех отсортированных отрезков, при этом устройство функционирует аналогично. .

Далее процесс повторяется до тех пор, пока в ВЗУ не будет записан естественный отрезок, являющийся отсортированным массивом.

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

Устройство для сортировки чисел, содержащее группу из ш счетчиков, где m - количество одновременно сортируемых чисел, выходной счетчик, первую группу из m элементов И, вторую группу из п элементов И, где п - разрядность сортируемых чисел, груп- .Q пу из m дифференцирую1цих элементов, элемент ИЛИ, группу из m элементов ИЛИ и первый элемент И,- выход которо-. го соединен с первыми входами элементов И первой группы, и суммирующим j входом выходного счетчика, выход j- го разряда которого, где j 1, 2, ..., п, соединен с первым входом j-ro элемента И второй группы, выход которого является выходом j-ro раз- 2Q ряда отсортированного числа устройства, выход 1-го элемента И первой группы, где i 1, 2 ..., m, соединен с вычитающим входом i-ro счетчика группы, выход j-ro разряда кото- 25 рого соединен .с j-входом i-элемента ИЛИ группы, прямой выход которого соединен с вторым входом i-ro элемен- та И первой группы, выход i-ro диференцирующего элемента группы соеинен с i-M входом элемента ИЛИ, выход которого соединен с вторыми вхоами элементов И второй группы, о т- ичающееся тем, что, с елью расширения области применения за счет обеспечения возможности сорти-35 овки массивов неограниченной длины, в него введены генератор импульсов, сумматор-вычитатель, блок вццеления крайней единицы, блок сравнения, триггер управления, группа из m тригге- ров блокировки, третья группа из m элементов И, элемент ИЛИ-НЕ, второй и третий элементы И и элемент 2И-ИЛИ, причем входы запуска и останова устойства соединены соответственно с входами запуска и останова генератора мпульсов, выход которого соединен с прямым входом первого элемента И и первыми прямыми входами первого и второго элементов И элемента 2И-ИЛИ, 50 вторые прямые входы которых подключены соответственно к инверсному и

30

Q Q 5 5 0

0

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

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

IM.

IFIJ

21/

25