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

БРЕТЕН ТЕЛЬ М ут- тМ 3 ОСУДАРСТВЕННЫИ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИИ ОПИСАНИЕ И АВТОРСКОМУ СВИД(56) Авторское свидетельство СССРУ 911513, кл, С 06 Р 7/06, 1980,Авторское свидетельство СССРУ 993251, кл. С 06 Р 7/08, 1981.(54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ (57) Изобретение относится к автоматике и вычислительной технике. Цель изобретения - расширение области применения эа счет обеспечения возможности сортировки массивов неограниченной длины. Устройство содержит счетчики, триггеры, блок сравнения, блок выделения крайней единицы, генератор импульсов, сумматор-вычита тель, элементы И, ИЛИ, ИЛИ-НЕ, 2 ИИЛИ, дифференцирующие элементы, Первые ш чисел записываются в счетчики,содержимое которых начинает уменьшаться по единице, одновременно ввыходном счетчике происходит подсчетимпульсов. В момент установления внекотором счетчике нуля содержимоевыходного счетчика выводится во внешнее запоминающее устройство (ВЗУ),а в освободившийся счетчик заноситсяследующее число из массива. Есливновь заносимое число больше, чемтолько что выведенное, перед записьюв счетчик оно уменьшается на величину только что выведенного числа, если меньше - то записывается без, изменения в счетчик, который затеммаскируется нулевым состоянием триггера блокировки. Когда все счетчикиокажутся замаскированными, они размаскируются, и процесс повторяется свывода в ВЗУ нового отрезка отсортированных чисел. После сортировкивсего массива процесс повторяется,при этом числа последовательно берся из всех ранее отсортированных орезков. 1 ил, 1377852Изобретение относится к автоматике и вычислительной технике,Цель изобретения - расширение области применения за счет обеспечениявозможности сортировки массивов не 5ограниченной длины,На чертеже представлена схемаустройства.Устройство содержит группу счетчикав 1, - 1 , где ш - количество одновременно сортируемых чисел, выходной счетчик 2, триггеры блокировки3 - 3 группы, триггер 4 управления,сумматор-,вычитатель 5, блок 6 выделения крайней единицы (БВКЕ), генератор 7 импульсов, блок 8 сравнения,группы элементов И 9, - 9 10, 11 -11, группу элементов ИЛИ 12, - 12группу дифференцирующих элементов 2013, - 13 , элементы И 14-16, элементИЛИ 17, элемент 2 И-ИЛИ 18, элементИЛИ-НЕ 19, группу информационных входов 20, входы 21 и 22 запуска и оста-,нова, группу информационных выходов 2523, выход 24 синхронизации и выход 25окончания работы 25.Единичный сигнал на выходе блока 8сравнения формируется при наличииединичного сигнала на его управляющем входе и если Р, т Р где РР , - числа, находящиеся соответственно в счетчике 2 и поступающие на вход20. Сумматор-вычитатель.5 формируетразность Р = Р - РлР, Где Рсигнал на выходе блока 8 сравнения.БВКЕ 6 формирует единичный .сигнал навыходе с минимальным номером изтехвходов, на которых присутствуют единичные сигналы. Предварительно счет 40чики 1, 2 установлены в нулевое состояние, триггеры 3, 4 - в единичное.Устройство работает следующим.образом,После запуска по входу 21 генератора 7 импульсов сортируемые числа,предварительно поступающие по входу20, без изменения проходят через сумматор-вычитатель 5 и записываютсяпоследовательно в счетчики 1- 1(после записи числа в счетчик 1 50где 1 = 1, 2.ш - 1, на инверсном выходе элемента ИЛИ 12присутствует нуль и единичный сигнал будетсформирован на (1 + 1)-м выходе БВКЕ6) по импульсу от генератора 7 импульСов, проходящему через элемент2 И-ИЛИ 18 на входы синхронизациивсех счетчиков 1. После записи числа в счетчик 1 единичный сигнал, сформированный на прямом выходе элементаИЛИ 12 , установит триггер 4 в нулевое состояние,Затем импульсы от генератора 7 поступают на вычитающие входы счетчиков 1 и суммирующий вход счетчика 2.Через некоторое время в счетчике 2окажется записанным минимальное изш чисел, а в некотором счетчике 1-в 0, который распознается элементомИЛИ 12 С, При этом выделенное число,сопровождаемое синхроимпульсом на выходе 24, поступает на выходы 23 устройства и записывается во внешнеезапоминающее устройство (ВЗУ), Восвободившийся счетчик 1 заноситсяследующее число из сортируемого массива, При этом возможны два варианта.Если вновь вводимое число не меньше числа, накопленного в счетчике 2,т. е. Р з Р, что определяется блоком 8сравнения, то вычисляется разностьР - Р, , которая заносится в счетчик 1, и работа устройства продолжается. Если же РР, это означает, что число Р должно находитьсясреди уже записанных во ВЗУ чисел.В этом случае числа Р без изменениязаписывается в .счетчик 1 о, а триггер3устанавливается в нулевое состояние, чем блокируется уменьшение числа, записанного в счетчик 1 с. Процесс сортировки продолжается без учета этого числа.ьЧерез некоторое время все триггеры 3, - 3 будут установлены в нулевое состояние, что распознается элементом ИЛИ-НЕ 19, сигналы на выходе ко" торого устанавливаются в единичное состояние, все триггеры 3- 3, счетчик 2 устанавливаются в "0", а устройство,начинает формировать следующий отрезок отсортированных чисел и выводить его на ВЗУ. После просмотра всего массива числа на вход 20 устройства начинаютпоступать числа последовательно из всех отсортированных отрезков, приэтом устройство функционирует аналогично,Далее процесс повторяется до техпор, пока в ВЗУ не будет записанестественный отрезок, являющийся отсортированным массивом.формула изобретения Устройство для сортировки чисел, содержащее группу из ш счетчиков, где ш - количество одновременно сор 5 тируемых чисел, выходной счетчик, первую группу из ш элементов И, вторую группу из и элементов И, где ив разрядность сортируемых чисел, группу из ш дифференцирующих элементов, элемент ИЛИ, группу из ш элементов ИЛИ и первый элемент И, выход которого соединен с первыми входами элементов И первой группы, и суммирующим входом выходного счетчика, выход 1- го разряда которого, где 1 = 1,. 2,и, соединен с первым входом 1-го элемента И второй группы, выход которого является выходом 1-го разряда отсортированного числа устройства, выход д-го элемента И первой группы, где 1 = 1, 2 , ш, соединен с вычитающим входом 1-го счетчика группы ВыхОдГО Разряда кОтО 25 рого соединен,с 1-входом 1-элемента ИЛИ группы, прямой выход которого соединен с вторым входом д-Го элемента И первой группы, выход 1-го диф 30 ференцирующего элемента группы соединен с 1-м входом элемента ИЛИ, выход которого соединен с вторыми входами элементов И второй группы, о тл и ч а ю щ е е с я тем, что, с целью расширения области применения за счет обеспечения возможности сорти-З 5 ровки массивов неограниченной длины, в него введены генератор импульсов, сумматор-вычитатель, блок выделения крайней единицы, блок сравнения, триггер управления, группа из ш тригге ров блокировки, третья группа из ш элементов И, элемент ИЛИ-НЕ, второй и третий элементы И и элемент 2 И-ИЛИ, причем входы запуска и останова устройства соединены соответственно с 45 входами запуска и останова генератора импульсов, выход которого соединен с прямым входом первого элемента И и первыми прямыми входами первого и второго элементов И элемента 2 И-ИЛИ, 50 вторые прямые входы которых подключены соответственно к инверсному и прямому выходам триггера управления,вход установки в нулевое состояниекоторого подключен к выходу второгоэлемента И, прямой вход которого подключен к прямому выходу ш-го элементаИЛИ группы, инверсный выход 1-го элемента ИЛИ группы соединен с-м входом третьего элемента И, входом 1-годифференцирующего элемента первымвходом -го элемента И третьей группыи 1 - м входом блока выделения крайнейединицы, -й выход которого соединенс входом разрешения записи -го счетчика группы, выход элемента ИЛИ является входом синхронизации устройстваи соединен с инверсными входами первого и второго элементов И и первогоэлемента И элемента 2 И-ИЛИ, выход которого соединен с входами синхронизации счетчиков группы и инверсным вхо-,дом элемента ИЛИ-НЕ, выход которогосоединен с входами установки в единичное состояние триггеров блокировкигруппы и входом установки в нулевоесостояние выходного счетчика, выходыразрядов которого соединены с первойгруппой информационных входов блокасравнения и группой входов вычитаемого сумматора-вычитателя, группавходов уменьшаемого которого обьединены с второй группой информационныхвходов блока сравнения и являетсягруппой информационных входов устройства, инверсный выход триггера управления соединен с входом разрешениясуммирования выходного счетчика.иуправляющим входом блока сравнения,выход которого соединен с вторымивходами элементов И третьей группыи управляющим входом сумматора-вычитателя, выходы которого соединены ссоответствующими информационнымивходами счетчиков группы, выход ь-гоэлемента И .третьей группы соединенс входом установки в нулевое состояние д-го триггера блокировки группы,прямой выход которого соединен с третьим входом -го элемента И первойгруппы и с -м прямым входом элемента ИЛИ-НЕ, выход третьего элементаИ является выходом окончания работыустройства.осудар ам изо Москва Тираж 704 венного комиетений и откЖ, Раушск ета СССытийя наб.,