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

(9) (06 Р 7/06 УДАРСТВЕННОЕ ПАДОМСТВО СССРСПАТЕНТ СССР) И ИЗОБ АВТОРСКО У СВИДЕТЕЛ ологоас Д.А.Са-.(56) Авторское свидетельство СССРВ 538358, кл. 6 06 Г 7/04, 1976.Авторское свидетельство СССРМ 881735, кл. 0 06 Е 7/06, 1979,(54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИСЕЛ(57) Изобретение относится к автоматиквычислительной технике и может быть ьзовано для формирования упорядоченмассива чисел. Цель изобретения - ширение функциональных возможноза счет возможности сортировки чисел ином массиве из исходных массивов. ойство содержит блок 1 памяти вход- массивов, коммутатор 2, два блока па и 7, дешифратор 4, блок 5 подсчета ива из исходных массивов неравных мов, элементы И 6,9 и 14, блок сравнеблок элементов ИЛИ, буферный блок 11 ти, выходной блок 12 памяти и группы 13 элементов И, 2 ил. в ед Устр ных мяти масс обье ния, памя 10 иИзобретение относится к автоматике ивычислительной технике и может быть использовано для формирования упорядоченного массива чисел из и исходныхупорядоченных массивов неравных объемов.Цель изобретения - расширение функциональных возможностей устройства засчет возможности сортировки чисел в едином массиве из исходных массивов неравкых обьемов,На фиг.1 представлена электрическаяструктурная схема устройства для сортировки чисел; на фиг,2 - схема блока подсчетамассивов. 15Устройство для сортировки чисел фиг.1)содержит блок 1 памяти входных массивов,коммутатор 2, второй блок 3 памяти, дешифратор 4, блок 5 подсчета массивов, первыйэлемент И 6, первый блок 7 памяти, блок 8 20сравнения, вторую группу 9 элементов И,группу 10 элементов ИЛИ, буферный блок11 памяти, выходной блок 12 памяти, первую группу 13 элементов И, второй элементИ. 14. 25Блок 5 подсчета массивов (фиг.2) содержит элемент ИЛИ 15, одновибратор 16, счетчик 17, блок 18 сравнения, регистр 19 игенератор 20 тактовых. импульсов (ГТИ).Устройство для сортировки чисел рабатает следующим образом,Предварительно опишем решаемую задачу.Пусть имеется ч исходных массивов, вкаждом из которых находится и= (1=1, М) 35упорядоченных чисел. Необходимо из элементов этих исходных массивов составитьМединый массив, содержащий и = Х (и)= 40упорядоченных чисел. Рассматриваемыемассивы представляют собой, в нашем понимании, наборы чисел, записанных в фор-медвоичных кодов, последним элементом вкаждом из которых является признак конца 45массива , т,е. некоторый специфичный код,выходящий за рамки представления чисел.Перед началом работы устройства навход регистра 19 блока 5 подается число й упорядоченных массивов. Первый массив подается на информационный вход первого 50 блока 7 памяти, а остальные Ймассивов При вкЛючении блока 5 нэ его выходе последовательно формируются адреса регистров 1- блока 1 памяти входных массивов, которые поступают нэ управляющийзаносятся в блок 1 памяти входных массивов. Кроме того, обнуляетСя содержимое. первого блока 7 памяти, второго блока 3 55 памяти и буферного блока 11 памяти. вход коммутатора 2. В результате этого первый массив из блока 1 через коммутатор 2 поступает на информационный вход второго блока 3 памяти.На четвертом выходе блока 5 появляется импульс, при поступлении которого на первый управляющий вход первого блока 7 памяти в него записывается первый массив чисел, а при поступлении этого импульса на второй управляющий вход второго блока 3 памяти происходит запись массива с выхода коммутатора 2 во второй блок 3 памяти.Первое число из первого блока 7 памяти и первое число из второго блока 3 памяти поступают на первый и второй входы блока 8 сравнения, первый и второй входы дешифратора 4, а также на информационные входы первой 13 и второй 9 групп элементов И соответственно.Если число, поступающее на первый вход блока 8 сравнения, меньше или равно числу, поступающему на его второй вход, то на втором выходе блока 8 появляется единичный потенциал, который поступает на второй вход первой группы 13 элементов И и открывает их. В результате этого число с информационного входа и первой группы 13 элементов И поступает на первый вход группы 10 элементов ИЛИ. Так как вторая группа элементов И в этот момент закрыта, то число через группу 10 элементов ИЛИ поступает в буферный блок 11 памяти. Кроме того, единичный потенциал со второго выхода блока 8 сравнения поступает на второй вход первого элемента И 6, В результате управляющий импульс с третьего выхода блока 5 через первый элемент И 6 поступает на второй управляющий вход первого блока 7 памяти. При этом содержимое первого блока 7 памяти продвигается на одну ячейку и на его выходе появляется второе число упорядочиваемого массива. После этого процесс сравнения двух чисел повторяется.Если число, поступающее на первый входблока 8 сравнения, больше числапоступающего нэ его второй вход, то на первом выходе блока 8 сравнения появляется единичный потенциал, который, поступая нэ первый вход второй группы элементов И 9, открывает его, поэтому число с информационного входа второй группы элементов И 9 поступает на второй вход группы 10 элементов ИЛИ. Так как первая группа элементов И 13 в этот момент закрыта, то число через группу 10 элементов ИЛИ поступает в буферный блок 11 памяти. Кроме того, единичный потенциал с первого выхода блока 8 сравнения поступает нэ первый вход второго элемента И 14 и управляющий импульс с третьего выхода блока 5 через второй эле 1835543мент И 14 поступает на первый управляю- И, отл и ч а ю щ вес я тем. что. с целью щий вход второго блока 3 памяти. При этом расширения функциональных возможно- содержимое второго блока 3 памяти сдвига- стей за счет возможности сортировки чисел ется на одну ячейку и на его выходе появля-, в едином массиве из исходных массивов не ется второе число упорядочиваемого 5 равных объемов, в него введены второй массива, После этого процесс сравнения блок памяти, буферный блок памяти, выход- двух чисел повторяется. ной блок памяти, блок подсчета массивов,При появлении на выходе первого блока две группы элементов И, группа элементов 7 или второго блока 3 признака конца мас- ИЛИ, второй элемент И, дешифратор и блок сива происходит запись в буферный блок 11 10 памяти входных массивов, выходы которого памяти числа;появившегося на выходедру- соедияены с информационными входами гого блока памяти, поскольку блок 8 сравне- коммутатора, адресные входы которого соения интерпретирует признак конца массива динены с информационными выходами блокак очень большое число, ка подсчета массивов, а выходы соединеныОписанный выше процесс сравнения 15 с информационными входами второго блодвух чисел заканчивается в тот момент, ког- ка памяти, выходы которого соединены с да на выходах первого 7 и второго 3 блоков входами второй группы блока сравнения, устанавливаются признаки конца массива. входы первой и второй групп блока срав- В результате поступления двух признаков нения объединены с соответствующими конца массива на входы блока 8 сравнения 20 входами первой и второй групп дешифраодин из них записывается в буферный блок тора и с информационными входами эле памяти и становится признаком конца ментов И соответственно первой и второй упорядоченного массива, сформированного групп, управляющие входы которых соедииз элементов первого и второго массивов. нены соответственно с выходами "Мень- Кроме того, оба признака поступают на вхо ше" и "Больше" блока сравнения, а выходы ды дешифратора 4, который при этом фор- соединены с соответствующими первыми мирует на выходе единичный потенциал, и вторыми. входами элементов ИЛИ груп-поступающий на вход блока,5, который из- пы, выходы которых соединены с информаменяет адрес на своем первом выходе и ционными входами буферного блока формирует на своем четвертом выходе уп памяти, выходы которого соединены с инравляющий импульс, который поступает на формационными входами первого блока папервый управляющий вход первого блока 7 мяти и выходного блока памяти,.вход записи памяти, второй управляющий вход второго которого соединен с выходом результата блока 3 памяти и второй управляющий вход блока подсчета массивов, информационные буферного блока 11 памяти. 35 входы которого являются входами числаПри этом его содержимое записывается массивов устройства, а вход запуска - вхов первый блок 7 памяти, а во второй блок 3 дом запуска устройства, выход "Больше" памяти через коммутатор 2 записывается блокасравнения соединен с первым входом следующий упорядочиваемый массив из второго элемента И, второй вход которого блока 1 памяти входных массивов, адрес 40 соединен с тактовым выходом блока подсчекоторого поступает на.вход коммутатора 2 с та массивов, входом записи буферного блопервого выхода блока 5,. ка памяти и вторым входом первогоОписанный процесс упорядочивания элемента И, выходы первого и второго элеповторяется до тех пор, пока не будут отра-ментов И соединены с входами сдвига соотботаны все массивы из блока 1 памяти вход- .45 ветственно первого и второго блоков ных массивов. После этого на втором памяти,входызаписикоторыхивходсчитывыходе блока 5 появляется единичный им- вания буферного блока памяти соединены с пульс, который поступает на управляющий выходом разрешения записи блока подсчевход выходного блока 12 памяти, и в выход- та массивов, вход приращения адреса катаной блок 12 памяти из буферного блока 11 50 рого соединен с выходом дешифратора. памяти. записывается результирующий упо- . 2. Устройство по п,1. о т л и ч а ю щ е е- рядоченный массив. с я тем, что блок подсчета массивов содерФ о р м у л а и з о б р е т е н и яжит генератор тактовых импульсов, регистр, 1. Устройство для сортировки чисел, со- одновибратор. схему сравнения, счетчик, держащее. первый блок памяти блок сравне, элементы ИЛИ и задержки, причем вход зания, коммутатор и первый элемент И, пуска блока соединен с входом запуска гепричем выходы первого блока памяти сое- нератора тактовых импульсов, входом динены с входами первой группы блока сброса счетчика, записи регистра и первым сравнения, выход "Меньше" которого под- входом элемента ИЛИ, второй вход котороключен к первому входу первого элемента . го является входом приращения адреса бло1835543 Вкл Фиг оставитель Д. Сапанкевичехред М.Моргентал Ко Редактор А, Козлова В. Петра Заказ 2982 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям и 113035. Москва. Ж, Раушская наб 4/5 ТСС Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101 ка, а выход соединен с входом одновибратора, выход которого является выходом разрешения записи блока и подключен к счетному входу счетчика и через элемент задержки к входу разрешения счета счетчика, выходы разрядов которого являются информационными выходами блока и входами первой группы схемы сравнения, входы второй группыкоторого соединены с выходами регистра, информационные входы которого являются информационными входами блока, выход схемы сравнения является выхо дом результата блока и подключен к входуостанова генератора тактовых импульсов, выход которого является тактовым выходом блока,