Устройство для сортировки чисел Советский патент 1986 года по МПК G06F7/06 

11247860

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

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

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

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

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

нения 1 интервала изменения j l,....i-K.

В результате этого на первую груп- 3,числа X:

знаки сравнения Р, последующими числами х

со всеми

1

массива, а на

вторую группу входов - двоичные признаки сравнения т- числа х- со всеми предыдущими числами х- массива, где

«О 1 1+1, 1+2,...,п, j 1,2,...,После суммирования на выходе сумматора 3,- формируется управляющий сигнал f , который является суммой результа тов сравнения m,-j числа со всеми

15 числами массива и результатов сравнения Г;. числа к,- со всеми последующи1,ьI

ми числами массива:

1 ,..,,1р1 устройства поступает массив

2

из п чисел X

,х.

20 . ,« ЙГЛе 2,3,...,п-1 р - „(4)

И А

- т„р

;ли/

..,Xj,, подлежащих

сортировке. В блоках 2,,,... , сравнения 1-й группы число х сравни- в ается со всеми последующими числами массива, т.е. с х.х . . . ,х„. В ре- Признаки сравнения т,,.тЛ отличны зультате сравнения двух чисел х, и х - сравнении неравньк чисел . на выходах каждого блока 2.„ сравне- э

v

ния формируется двоичный признак сравг. „ отличен

массива, в то время как если х х,

™i c ™е-1 признак от 0.

нения соответствии с выражением;

Че

где r,.g

1,,.

.ет,

х„

1,е 1, при к

0,при Xj 5 Xg

1,при х. X

(1); (2)

(3)

0, при X у i Хр Двоичные признаки сравнения &;, jpXi-fz ,h i-ой группы поступают н первую группу (n-i) входов сумматора , кроме последнего сумматора 4п

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

чисел XV и X

1

т.е. х Xj

H.X.Xg,

при инвертировании двоичного признака сравнения Ь , формируется двоичный 1Тризнак сравнения ,.,который является результатом сравнения числа с предшествующим ему числом х;, где j 1,2,...,1-1 и определяется выражением (3) после замены индекса t на J и введения вместо интервала изменения 1 интервала изменения j l,....i-K.

В результате этого на первую груп- 3,числа X:

знаки сравнения Р, последующими числами х

со всеми

1

массива, а на

вторую группу входов - двоичные признаки сравнения т- числа х- со всеми предыдущими числами х- массива, где

1 1+1, 1+2,...,п, j 1,2,...,. После суммирования на выходе сумматора 3,- формируется управляющий сигнал f , который является суммой результатов сравнения m,-j числа со всеми

числами массива и результатов сравнения Г;. числа к,- со всеми последующи1,ьI

ми числами массива:

. ,« ЙГЛе 2,3,...,п-1 р - „(4)

И

- т„р

;ли/

Признаки сравнения т,,.тЛ отличны сравнении неравньк чисел .

Признаки сравнения т,,.тЛ отличны сравнении неравньк чисел .

г. „ отличен

массива, в то время как если х х,

™i c ™е-1 признак от 0.

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

m

{,е

по 1 от 1 до п, при этом такое преобразование не нарушает исходных

соотношений в сортируемом массиве.

X

при которых из условиях х следует { /с, где 1 ГТп; , ff 0,,,.,п-, fj 0,...,и-1. . В том случае, если в сортируемом массиве все числа одинаковы, тогда все признаки т(( в соотношении (4) равны О и величина управляющего сигнала равна f, п-1, для 1 1 ,п. Поэтому для массива равных чисел на входах устройства значения управляющих сигналов /, на вьпсодах сумматоров 4 ,4 ,. . . ,4р, принимают последовательность дискретных несовпадающих значений (h-i) , (п-2),...,0. В результате массиву равньк входных чисел х X ,...,х ставится в соответствие .соотношение управлякяцих сигналов (р ftj которое числу х на входе с наименьшим номером при- письгаает наибольшее значение управ31

яющего сигнала, а числу х на ходе с наибольшим номером - наименьшее значение, что обеспечивает сортировку массива равных чисел.

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

Коммутаторы 5,, выполняют сортировку чисел х- входного массива в зависимости от номера позиции числа на выходе сумматора А, при этом коммутатор 5j пропускает число xj на выход 6j в том только, случае если 5. S-1.

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

сива чисел х,,х„

,х на выходы

устройства 6. ,6, .. . ,6, поступает последовательность неубьшающих чисел X g / X g .. . / Xjj, при этом каждые Р равных чисел оказываются рассортированными по Р соседним выходам.

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

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

10

t5

2478604

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

20

25

30

35

К иидзорнационньгм входам копнутотороВ 2-й группы

Выходы

KaHif)Of3Mat4(jOHHbiM Входом конмутоторов З-й группы

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