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

11

Изобретение относится к автоматике и вычислительной технике..

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

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

Устройство содержит п групп по (п-1)-му элементу сравнения 1

J,, .

п,1 п,а а,п-1

1.,1 1.

,...,(

1.

0,П-1

са

п,1 п,г две группы по п сумматоров

IJ i ylllLDl 11 II Л111С1 1 JjLJUJO

2-2 И 3 -3, n блоков памяти выполненных, например, в виде ПЗУ, п групп по п подгрупп элементов И 1,1 п,п (каждая из которых содержит m - по количеству разрядов сортируемых чисел - элементов И), п групп элементов ИЛ11 6-6 , входы 7-7 сортируемых чисел, выходы отсортированных .чисел.

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

Сортируемые числа поступают по входам 7 -7 на входы элементов

,, сравнения, где попарно сравниваются каждое с каждым. Б каждой i-й группе, где i 1,2,..,,п, сумматором 21 подсчитывается Е - количество чисел, равных поступившему по i-му входу числу а., и сумматором

3. подсчи тываетЬя L j - количество чисел, меньших а-. С выходов с;умма- торов 2 и 3 - величины Е и L поступают на адресные входы блока 4 памяти, который формирует сигнал логической единицы на своем ()-м выходе, начиная с (Ц-+1)-го. В результате открываются элементы И соответствующих групп 5; .....

55

, ь , 4й - -(Дм Е,--и

поступает на выходы SL,, .,.., 5°ьц-г2

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

и число а

5 2

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

Устройство для сортировки чисел, содержащее п групп по (п-1) элементов сравнения, где п - количество сортируемых чиселj причем вход q-ro разряда i-ro числа устройства, где ,2,...,п, q 1,2,...,m, m - количество разрядов сравниваемых чисел,

соединен с q-ми входами первых групп входов всех элементов сравнения 1-й группы, с q-ми входами вторых групп входов (1-1)-х элементов сравнения с первой по (1-1)-ю группу и с q-ми

входами вторых групп входов 1-х элементов сравнения с (1+1)-и -по п-ю группу, отличающееся тем, что, с целью расширения области применения эа счет обеспечения возможности сортировки массива, содержащего равные .числа, оно содержит первую и вторую группы из п сумматоров, п блоков памяти, п групп по п подгрупп из п элементов И, п групп по m элементов ИЛИ, причем выход Равно Г-го элемента сравнения 1-й группы, где I 1,2,...,(п-1), соединен с 1-м входом 1-го сумматора первой группы, р-й выход которого, где nt,l

Х - ближайшее целое, большее X, соединен с р-м адресным входом 1-го блока памяти, выход Меньше Е-го элемента сравнения 1-й группы соединен с f-M входом 1-го сумматора второй

группы, р-й выход которого соединен с (p -ltop пС )-м адресным входом 1-го блока памяти, j-й выход которого, где j 1,2,...,п, соединен с первьми входами элементов И j-подгруппы 1-й

группы, вход q-ro разряда 1-го числаj устройства соединен с вторыми входами q-x элементов И всех подгрупп 1-й группы, выход q-ro элемента И 1-й подгруппы j-й группы соединен с j-M

входом q-rc элемента ИЛИ 1-й группы, выход которого является выходом q-ro разряда 1-го отсортированного числа устройства.

Составитель В.Иванова Редактор В.Данко Техред Л.Олийнык

Заказ 1972/47 Тираж 673Подписное

БНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно

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

Изобретение относится к автоматике и вычислительной технике. Цель изобретения - расширение области применения за счет обеспечения возможности сортировки массива, содер- жащегв равные числа. Устройство содержит п групп по (п-1) элементов сравнения, где п - количество сортируемых чисел, 2п сумматоров, п блоков памяти (например, ПЗУ), п групп по п подгрупп элементов И и п групп элементов ИЛИ. Сортируемые числа элементами сравнения сравниваются попарно каждое с каждым. Для каждого из п чисел счетчиками подсчитывается количество Е . чисел, равных а;-му, и количество L чисел, меньшее а-. Величины Е и L, поступают на адресные входы соответствующего блока памяти, который, сформировав на своих соответствующих выходах сигналы логической едини1ды, открывает элементы И так, что число а. формируется на ()-м смежном выходе устройства, начиная с ()-ro. 1 ил. о S (Л 0 СП ся У