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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 19 151) ПИСАНИЕ ИЗОБРЕТЕНИЯА ВТОРСКОМУ СВИДЕТЕЛЬСТВУ 973260/24-24 О, 11.853.05.88. Бюл. .А.Мельник, Е,(21 (22 (46 соГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТ(56) Авторское свидетельство СССР У 637810, кл. С 06 Г 7/08, 1976,Авторское свидетельство СССР )1 1007099, кл. С 06 Р 7/08, 1981. (54)(57) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ, содержащее щ ячеек анализа, где ш - количество чисел в выходном массиве, каждая ячейка содержит приемный регистр, блок сравнения, регистр результата и коммутатор, причем информационный вход устройства соединен с информационным входом приемного регистра первой ячейки, выход приемного регистра 1-й ячейки, где д = 1,2щ, соединен с информационным входом регистра результата и первыми информационными входами блока сравнения и коммутатора той же ячейки анализа, выход регистра результата 1-й ячейки анализа соединен с вторыми информационными входами коммутатора и блока сравнения той же ячейки анализа, выход блока сравнения -й ячейки анализа соедине с управляющим входом коммутатора и первым входом разрешения записи регистра результата той же ячейки анализа, выход коммутатора 1-й ячейкианализа, где 1 = 1,2. . .(щ),единен с информационным входом приемного регистра (1+1)-й ячейки анализа, выход коммутатора п 1-й ячейки анализа является выходом устройства,тактовый вход устройства соединен свходами разрешения записи приемныхрегистров всех ячеек анализа и с вторыми входами разрешения записи регистров результата всех ячеек анализа,о т л и ч а ю щ е е с я тем, что, сцелью повьппения быстродействия присортировке нескольких массивов чисел,каждая ячейка анализа дополнительносодержит первый и второй триггеры,причем синхровходы триггеров всех,ячеек анализа подключены к тактовомувходу устройства, прямой выход первого триггера каждой ячейки анализасоединен с управляемым входом блокасравнения и информационным входом .второго триггера той же ячейки анализа, прямой выход второго триггера1-й ячейки анализа соединен с информационным входом первого триггера(1+1)-й ячейки анализа, вход началамассива устройства соединен с информационным входом первого триггерапервой ячейки анализа, прямой выходвторого триггера щ-й ячейки анализаявляется выходом окончания сортировки массива устройства.Изобретение относится к автоматике и вычислительной технике,Цель изобретения - повышение быстродействия при сортировке несколькихмассивов чисел.На чертеже приведена схема устройства.Устройство содержит ш ячеек анализа 1,-1 , где ш - количество чиселв выходном массиве, Каждая ячейкасодержит приемный регистр 2, регистр3 результата, блок 4 сравнения, коммутатор 5, триггеры 6 и 7. Устройство содержит также информационныйвход 8, вход 9 начала массива, тактовый вход 10, информационный вход 11и выход 12 окончания сортировки массива.Устройство работает следующим образом.На вход 8 устройства последовательно поступают числа сортируемыхмассивов, Каждое число сопровождается импульсом на тактовом входе 10, а 25первое число каждого массива - сигналом логической единицы на входе 9.Поэтому первое число массива записывается в регистр 21, а триггер 6,устанавливается в единичное состояние.30Единичный сигнал с выхода триггера6 1, поступающий на управляющий входблока 4 сравнения, предопределяетперезапись в следующем такте числаиз регистра 3 1 через коммутатор 5 в регистр 2, а из регистра 2, - в регистр Знезависимо от соотношения чисел, хранящихся в регистрах 2, и 3,. Единица из триггера 6, переписы - вается при этом в триггер 71. В третьем такте происходит сравнение чисел, находящихся в регистрах 2и 3 большее из них переписывается через коммутатор 5 1 в регистр 2(число из которого переписывается в регистр 3 ) а меньшее остается в регистре 31, В регистр 2 1 при этом записывается следующее число. Дальнейшая работа устройства аналогична.Таким образом, большие по величине числа продвигаются к ш-й ячейке, не перезаписываясь в регистры 3,-3 поэтому "обгоняют" меньшие числа. На выходе 11 формируется, последовательность отсортированных чисел.Сразу за загрузкой в регистр пос 1/ леднего числа первого массива а1 т может быть загружено, не ожидая окончания процесса сортировки первого массива первое число второго масси 2ва а,. При этом единичное значение в тр.ггерах 6,-6 , продвигаясь по цепочке ячеек одновременно с числом й 1 а запрещает сравнение чисел а иъ атем самым исключая воэможность 1 фперемешивания чисел из разных массивов. Конец сортировки очередного массива фиксируется наличием единичного сигнала на выходе 12 устройства.1397900Составитель В,Горохов Редактор И.Николайчук ТехредЛ,Олийнык Корректор А.Тяско Заказ 227 1/47 Тираж 704 Подписное ВНИИПИ Государственного комитета СССРпо делам изобретений и открытий113035, Москва, Ж, Раушская наб д, 4/5 Производственно-полиграфическое предприятие, г. Ужгород, ул, Проектная, 4