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

 

Изобретение относится к области автоматики и вычислительной техники и может быть использовано в устройствах обработки и сортировки данных систем контроля и регулирования, в ассоциативных процессорах, в системах распознавания образов. Цель изобретения - упрощение устройства. Устройство для сортировки чисел содержит п-1 групп блоков сравнения Двух чисел по n-(i-l) блоков сравнения в i-й группе, п сумматоров, п групп коммутаторов по п коммутаторов в каждой группе и п-1 групп элементов НЕ, количество которых в каждой группе разно i-1. Устройство позволяет сократить количество оборудования за счет сравнения каждого сортируемого числа только с последующими числами массива и формирования результатов сравнения каждого числа за счет инвертирования результатов сравнения предыдущих чисел с данным. 1 ил. -i сл г сх Од

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (gl) 4 G 06 F 7/06

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К А ВТОРСНОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

Il0 ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21 ) 3836696/24-24 (22) 07.01.85 (46) 30.07 .86. Бюл, ¹ 28 (72) Э.Д, Еремеева и В.А. Черепов (53) 681.325(088.8) (56) Братальский Е.А. и Крупский А.А.

Способы упорядочения массива с помощью ассоциативного устройства. — Вопросы радиоэлектроники. Сер, ЭВТ.

Вып. 7, 1973, с. 90 93.

Авторское свидетельство СССР

¹ 1065854, кл. G 06 F 7/06, 1982. (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ (57) Изобретение относится к области автоматики и вычислительной техники и может быть использовано в устройствах обработки и сортировки данных систем контроля и регулирования, в

„,SU„„1247860 А1 ассоциативных процессорах, в системах распознавания образов. Цель изобретения — упрощение устройства. Устройство для сортировки чисел содержит п-1 групп блоков сравнения двух чисел по п-(i-1) блоков сравнения в i-й группе, п сумматоров, и групп коммутаторов по п коммутаторов в каждой группе и и-1 групп элементов НЕ, количество которых в каждой группе рав- но i-1. Устройство позволяет сокра- тить количество оборудования эа счет сравнения каждого сортируемого числа только с последующими числами массива и формирования результатов сравнения каждого числа за счет инвертиро- .Я вания результатов сравнения предыдущих чисел с данным, 1 ил.

1247860

Изобретение относится к автоматике и вычислительной технике и может быть использовано в устройствах обработки и сортировки данных систем контроля и регулирования, в ассоциативных про- 5 цессах, в системах распознавания образов.

Цель изобретения — упрощение устройства.

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

Устройство для сортировки чисел содержит входы 1, блоки 2 сравнения, группы элементов НЕ 3, сумматоры 4, коммутаторы 5, выходы 6.

Устройство для сортировки чисел 15 работает следующим образом.

В момент времени t, на входы 1

1,...,1„ устройства поступает массив и из п чисел х, х,..., х „, подлежащих

1У сортировке. В блоках 2,;„,21;,...,2; „ 2О сравнения i-й группы число х сравнивается со всеми последующими числами массива, т.е. с х., х,„ . ° .,х„. В результате сравнения двух чисел х; и х на выходах каждого блока 2; сравнения формируется двоичный признак сравнения biе в соответствии с выражением: (l) (2) Г!, Ш ),ф

1, при х = х„ где r

",е О, прих; 4х

1, при х; ) х

m = (3)

1,å О, прих, х, Двоичные признаки сравнения Ь;, Jpt3;„° ° . ; t, -.ой группы поступают на первую группу (n-i) входов сумматора 4;, кроме последнего сумматора 4!!.

На вторую группу входов всех сум40 маторов 4;, исключая первый сумматор 4,, поступают признаки сравнения,В,,...,В; которые сформированы блоками сравнения 2,,2 ;,...,2„ „ и проинвертированы (i-1)-м элементом НЕ (i-1)-й группы 3;,. Вследствие того, что двоичные признаки сравнения Ь и m представляют полную груп-

6,!

Ф пу возможных результатов сравнения чисел х„и х1, т.е. х; 3 х и х <х, S0 .ч при инвертировании двоичного призйака ! равнения В;; формируется двоичный ! признак сравнения m;, !êoòoðü!M является результатом сравнения числа х; с предшествующим ему числом х, где

1,2,...,i-l и определяется выра.жением (3) после замены индекса Ю на

;1 и введения вместо интервала изменения 1 интервала изменения

l,...,i-l.

В результате этого на первую группу входов сумматора 3; поступают признаки сравнения В; числа х; со всеми последующими числами х массива, а на вторую группу входов — двоичные признаки сравнения m;> числа х; со всеми предыдущими числами х массива, где

J .

1 = i + 1, i+2,...,n, j= 1,2,...,i-!.

После суммирования на выходе сумматора 3; формируется управляющий сигнал который является суммой результатов сравнения m; числа х; со всеми ! числами массива и результатов сравнения r; < числа х; со всеми последующи-! ми числами массива: н ; =Ж" т, е= !! =!

m!!

+ Г-. !! =!+(=2,3,...,n-1 (4) !!,Е

Признаки сравнения m,,m; отличны ! от 0 при сравнении неравных чисел . массива, в то время как если .х =х, и ° = жВ1= Оq а, признак Г.) отличен 1e el 11 от О.

В том случае, если в массиве п сортируемых нет одинаковых чисел, т.е. все числа массива попарно не равны, тогда второе слагаемое в ооотношении (4) равно нулю. Поэтому формирование управляющего сигнала р; для массива неравных чисел заключается в суммировании признаков сравнения

mlе по 1 от 1 до и, при этом такое преобразование не нарушает исходных соотношений в сортируемом массиве, при которых из условиях х; < х следует g; < У <, где i= 1, и; =),и, В том случае, если в сортируемом массиве все числа одинаковы, тогда все признаки m; в соотношении (4) равны О и величина управляющего сигнала равна !; =- n-i, для i= I,n. Поэтому для массива равных чисел на входах устройства значения управляющих сигналов Я.; на выходах сумматоров 4„,4,...,4ц принимают последовательность дискретных несовпадающих значений (ь -1}, (и-2),...,О. В результате массиву равных входных чисел х, = х =,...,=х„ ставится в соответствие .соотношение управляющих сигналов p,)р ) ...р„, которое числу х„ на входе с наименьшим номером приписывает наибольшее значение управляющего сигнала, а числу х„ на входе с наибольшим номером — наименьшее значение, что обеспечивает сортировку массива равных чисел.

В общем случае для сортировки любого массива из и чисел преобразования (1) — (4) позволяют сформировать . на выходах сумматоров 4; последовательность несовпадающих дискретных значений управляющих сигналов р;, 10 принадлежащих интервалу 0,п-l, причем значение р. указывает номер по1 зиции числа х; в линейно упорядоченном по неубыванию массиве выходных чисел. 15

Коммутаторы 5 -5 выполняют сору тировку чисел х; входного массива в зависимости от номера позиции числа х; на выходе сумматора .4;, при этом коммутатор 5» пропускает число х; 20

1 на выход 66 в том только случае, если р. = в 1.

Таким образом, при поступлении на входы 1,1,...,l„ устройства мас-д сива чисел х,х,...,х„ на выходы

4У устройства 61,6,...,6„ поступает последовательность неубывающих чисел

Х6 )Z Х 6 . ° ° i Х6 ПРИ TOM,ÊÉÆËÛe равных чисел оказываются рассорти- З 0 рованными по 1 соседним выходам.

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

Устройство для сортировки чисел, 35 содержащее и-1 групп блоков сравнения двух чисел по п-(i-1) блоков в

1247860 4 каждой группе, где i= 2,3,...;,и", и — количество чисел в массиве, п групп коммутаторов, и сумматоров, причем входы первого сравниваемого числа устройства соединены с первыми группами входов блоков сравнения первой группы и с информационными .входами коммутаторов первой группы, входы i-го сравниваемого числа устройства соединены с первыми группами входов блоков сравнения i-й группы, информационными входами коммутаторов

i-й группь и вторыми группами входов

i-x блоков сравнения р-х групп, где р = 1,2,...,i-l, вход а-го сравниваемого числа устройства соединен с информационными входами коммутаторов и-й группы и вторыми группами входов (и-1)-х блоков сравнения всех групп, выходы блоков сравнения каждой k-й группы, где k = 1,2,...,п-l, соединены с первой группой входов k-ro суиматора, выходы всех и сумматоров соединены с управляющими входами коммутаторов соответствующих групп, разрядные выкоды J-х коммутаторов всех групп объединены, где = 1,2,.,п, и подключены к )-м выходам устрой" ства, о т л и ч а ю щ е е с я тем, что, с целью упрощения устройства, оно содержит и-1 групп элементов НЕ, причем входы элементов HE(i-1)-й группы соединены -соответственно с вы- .

Я ходами i-х блоков сравнения р-x . групп, а выходы элементов НЕ (i-1)-й группы подключены к второй группе входов i-ro сумматора.

124786(»

/ инооормационньич йодам

ВхОды

Кинюоркаццонным ходак кот уааторою юй ьруапы

Составитель А. Александров

Редактор И, Сегляник Техред М.Ходанич Корректор С. Шекмар

Заказ 4126/48 Тираж 671 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, r. Ужгород, ул.Проектная, 4