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

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

Иллюстрации

Показать все

Реферат

 

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

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

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

РЕСПУБЛИК (19) (И) 6 F 0 (5)) 4

g(;Fpp >w );)

1)

1 )) ЛЯ () Т (I

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

К АSTOPCKOMY СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3991959/24-24 (22) 16. 12,85 (46) 23.05.87. Бюл. Р 19 (71) Харьковский авиационный институт им. Н.Е.Жуковского (72) Ю И.Ялинич, В.Ю.Ларченко, В.И.Хлестков и М.Ф.Холодный (53) 68 1.325 (088.8) (56) Авторское свидетельство СССР

В 1065854, кл. G 06 F 7/06, 1982.

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

В 1019439, кл. G 06 F-7/04, 1981. (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ (57) Изобретение относится к автоматике и вычислительной технике. Цель изобретения — расширение области применения за счет обеспечения возможности сортировки массива, содержащего равные числа. Устройство содержит п групп по (n-1) элементов сравнения, где и — количество сортируемых чисел, 2п сумматоров, п блоков памяти (например, ПЗУ), и групп по п подгрупп элементов И и и групп элементов ИЛИ. Сортируемые числа элементами сравнения сравниваются попарно каждое с каждым. Для каждого из и чисел счетчиками подсчитывается количество Е .чисел, равных а;.му, и количество L .чисел меньшее à.. Be1

Э

1 личины Е . и L; поступают на адресные

1 входы соответствующего блока памяти, который, сформировав на своих соответствующих выходах сигналы логической единицы, открывает элементы И так, что число а формируется на

t (Е;+1)-м смежном выходе устройства, начиная с (L-+1)-го. 1 ил.

1 13

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

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

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

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

1,1

1,...,1 1,,1,1,.. °,1

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

f1 И-

2 -2 и 3 -3 и блоков памяти 4 -4

Ьь л выполненных, например, в виде ПЗУ, и групп по и подгрупп элементов И

5,, -5 „ (каждая из которых содер-

1 I жит m — по количеству разрядов сортируемых чисел — элементов И), п групп элементов ИЛИ 6 -6, входы 7„ -7„ сортируемых чисел, выходы 8„ -8„ отсортированных .чисел.

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

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

2, „ -2 „, сравнения, где попарно сравниваются каждое с каждым. В каждой i-й группе, где i = 1,2. ..n, сумматором 2i подсчитывается E; — количество чисел, равных поступившему по -му входу числу а., и сумматором

1

3 подсчитывается I, — количество

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

5 °,...,5 .. . и число а„

i L1Ô9 э 1, ° 1Ф 1Ф поступает на выходы 8 . „,8

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

12565 2

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

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

i=1,2,...,п, q = 1,2,...,m, m — количество разрядов сравниваемых чисел, 10 соединен с q-ми входами первых групп входов всех элементов сравнения -й группы, с q-ми входами вторых групп входов (i-1)-х элементов сравнения с первой по (i-1)-ю группу и с q-ми

15 входами вторых групп входов i-х элементов сравнения с (i+1)-й .по и-ю группу, отличающееся тем, что, с целью расширения области применения за счет обеспечения возмож20 ности сортировки массива, содержащего равные, числа, оно содержит первую и вторую группы из и сумматоров, и блоков памяти., n групп по и подгрупп из и элементов И, и групп по ш элементов ИЛИ, причем выход "Равно" Х-ro элемента сравнения i-й группы, где — 1,2,.. °,(п-1), соединен с 2-и входом i-го сумматора первой группы, р-й выход которого, где p=glog пГ,3

30 Х! — ближайшее целое, большее Х, соединен с р-м адресным входом i-го блока памяти, выход "Меньше" 3-го элемента сравнения i-й группы соединен с (-м входом i-ro сумматора второй

35 группы, р-й выход которого соединен с (р+ lkoe u C )-м адресным входом i-го 2 блока памяти, j-й выход которого, где

1,2,...,n, соединен с первыми входами элементов И j-подгруппы i-й

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

45 входом ц-го элемента KIN i-й группы, выход которого является выходом q-го разряда i-ro отсортированного числа устройства.

13! 2565

Составитель В.Иванова

Техред Л. Олийнык Корректор С.Черни

Редактор В.Данко

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

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

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

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