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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК Р 7 РЕТЕН ф. гфМй 1 у,.ЕТЕЛЬСТ данов СССР980.ССР1985.ОРТИРО к автома Цель изоб льных воз возможн жащих ра гистр-сче оличество ов сравнетике рете- можости вные тчик, сорния,ГОсудАРстВенный НОмитет сссР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТ ОПИСАНИЕН АВТОРСКОМУ( СВИ(54) УСТРОЙСТВО ДЛЯ СЧИСЕЛ(57) Изобретение относитсяи вычислительной технике.ния - расширение функционаностей за счет обеспечениясортировки массивов, содерчисла. Устройство содержит ре,801325463 а групп элементов И, счетчик, сумматор, выходную группу элементов и и элемент задержки. Сортируемые числа записываются в регистры. Затем число из и-го регистра сраь нивается блоками сравнения со всеми остальными числами, Счетчик подсчитывает количество чисел, меньших, чем содержащиеся в и-м регистре. К этому количеству сумматором прибавляется начальный адрес области памяти, в которую нужно занести отсортированный массив. После выдачи результата сортируемые числа сдвигаются по регистрам и затем анализируется число, ранее записанное в (и - 1)-м регистре, При этом из числа, записываемого в регистр-счетчик, вычитается единица, что обеспечивает устранение дыр в запоминающем устройстве при наличии в сортируемом массиве равных чисел. 1 ил.1Изобретение относится к автоматике ивычислительной технике.Цель изобретения - расширение функциональных возможностей за счет обеспечения возможности сортировки массивов, со.держащих равные числа,На чертеже представлена схема устройства.Устройство содержит регистр-счетчик 1 ьрегистры 1 - 1 где пколичество сортируемых чисел, блоки 2 - 2, сравнения,группы из гпэлементов И 3 - 3, где щ - количество разрядов сортируемых чисел, счетчик 4, сумматор 5, группу выходных элементов И 6, элемент 7 задержки, тактовыйвход 8, вход 9 начального адреса, группуинформационных 10 и адресных 11 выходов.Устройство работает следующим образом.В регистры 1 - 1 заносятся сортируемые числа. После этого содержимое регистра 1 сравнивается блоками 21 - 2 сравнения со всеми остальными сортируемыми числами, находящимися в регистрах 11 - 1Блоки 2 сравнения выдают единичный сигнал лишь в том случае, если числа, находяш,иеся в соответствующих регистрах 1 е (1= - 1,2 и - 1), меньше числа, записанного в регистре 1. Счетчик 4 подсчитывает количество блоков сравнения, имеющих единичный сигнал на своем выходе.С выхода счетчика 4 ца один из входовсумматора 5 подается код количества сортирусмых чисел, мецыпцх числа, записанногов регистре 1. На второй вход сумматора 5поступает код адреса области памяти, начиная с которого необходимо разместить отсортированный массив чисел. Тогда адресячейки памяти, по которому нужно записатьчисло, находящееся в регистре 1 п, определяется как 5 10 15 20 А = Амяч+Кгде Андч - адрес области памяти, начиная скоторого необходимо разместить отсортированные числа;К - количество чисел, меньших числа,записанного в регистре 1.Сумматор 5 вычисляет сумму А;.+ К.По сигналу с тактового входа 8 устройства число, находящееся в регистре 1, через открывшуюся группу элементов И 3 записывается в запоминающее устройство по адресу, выдаваемому сумматором 5 через группу выходных элементов И 6.Одновременно по этому же тактовому сигцалу через группы элементов И 3, - 3, каждое цз сортируемых чисел, находящихся в регцсграх 11 - -1, сдвигается в последуюций регистр цо кольцу, и начинается второй такт работы устройства, ца котором со всеми числами массива сравнивается число, первоначально находившееся в регист. ре 1 ь При этом тот же тактовый иМпульс, поступая через элемент 7 задержки ца вычитающий вход регистра-счетчика 11, умень 25 30 35 40 45 50 55 шает содержимое последнего на единицу. Эта операция приводит к тому, что на втором и последующих тактах числа, уже записанные в запоминающее устройство, участвукт в процессе сортировки уменьшенными на единицу и, следовательно, число а= =а 1 будет размещено по адресау Анач+К - 1. Это обеспечивает правильное формирование адресов и устранение дыр в запоминающем устройстве при наличии в сортируемом массиве равных чисел.Дальнейшая работа устройства аналогична, Через и тактов в запоминающем устройстве, начиная с адреса, заданного на входе 9 устройства, будет записан отсортированный массив в порядке возрастания.Для сортировки чисел в порядке убывания необходимо в регистры 1 записывать инверсные значения кодов сортируемых чисел.Формула изобретенияУстройство для сортировки чисел, содержащее и регистров, где о - количество сортируемых чисел, ив 1 блоков сравнения, счетчик, сумматор, п групп по лт элементов И, где т - количество разрядов сортируемых чисел, и группу из р выходных элементов И, где р = - 1 одл ,Х- ближайшее целое, большее х, причем выход -го элемента И -й группы, где = 1,2т, = 1,2 (а - 1), соединен с -м информационным входом (1+1)-го регистра, выход -го элемента И и-й группы является -м информационным выходом устройства и соединен с -м информационным входом первого регистра, выход -го разряда -го регистра соединен с первым входом г-го элемента И 1-й группы и с 1-м входом первой группы у-го блока сравнения, выход которого соединен с у-м входом счетчика, Ф-й выход которого, где й = 1,2р, соединен с 7 г-м входом первой группы сумматора, Й-й вход начального адреса устройства соединен с Й-м входом второй группы сумматора, Й-й выход которого соединен с первым входом А-го выходного элемента И группы, выход которого является Й-м адресным выходом устройства, выход -го разряда и-го регистра соединен с -ми входами второй группы всех блоков сравнения и с первым входом -го элемента И п-й группы, тактовый вход устройства соединен с вторыми входами элемента И всех групп и всех выходных элементов И группы, отличающееся тем, что, с целью расширения функциональных возможностей за счет обеспечения возможности сортировки массивов, содержащих равные числа, в него введец элемент задержки, а первый регистр выполнен в виде регистра-счетчика, вычитающий вход которого подключен к выходу элемента задержки, вход которого подключен к тактовому входу устройства.Составите.чь В. ГороховРедактор В. Петраш Техред И. Верес Корректор Л. ТаскаЗаказ 3 10/44 Тираж 672 ПодписноеВНИИПИ Государственного комитета СССР по делам изобретений и открытий113035, Москва, Ж - 35, Раушская наб., д. 45Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная. 4