Устройство для сортировки чисел
Изобретение относится к вычислительной технике. Цель изобретения - упрощение устройства. Устройство содержит п/2 ячеек S-ro типа, где п - количество сортируемых чисел, S 1,2,..., log,.n. Каждая ячейка первого типа содержит блок сравнения и два коммутатора, каждая ячейка i-ro типа (i 2, 3, ...,log п) содержит три подъячейки (i-l)-ro типа. На входы каждой ячейки i-ro типа поступают с выходов двух ячеек (i-1)- го типа две упорядоченные последовательности из 2 числа каждая. На выходе ячейки i-ro типа формируется объединенная упорядоченная последовательность из двух чисел. На выходе ячейки Jlog типа формируется упорядоченный исходный массив. 3 ил.
СОЮЗ COBETCHHX
Э
РЕСПУБЛИК (504 С 06F 7 06 зсмк(.ож. я я
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К А ВТОРСМОМ,Ф С ЕТЕЛЬСТВУ
ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР
ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3971597/24-24 (22) 03. 10.85 (46) 23.03.87. Бюл. У 11 (72) А.А. Мельник и И.Г. Цмоць (53) 681.325.66 (088 ° 8)
-(56) Авторское свидетельство СССР
В 1007099, кл. G 06 F 7/08, 1981.
Авторское свидетельство СССР
У 1123030, кл. С 06 F 7/06, 1983. (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ (57) Изобретение относится к вычислительной технике. Цель изобретения— упрощение устройства. Устройство соз -1 держит n/2 ячеек S-ro типа, где
„.SU„, 2 7 7 А1
n — - количество сортируемых чисел, S 1,2,..., )log n(. Каждая ячейка первого типа содержит блок сравнения и два коммутатора, каждая ячейка
i-го типа (i = 2, 3, ...,)log п() содержит три подъячейки (i-1) -ro типа.
На входы каждой ячейки i-го типа поступают с выходов двух ячеек (i-1)— го типа две упорядоченные последовательности из 2 числа каждая. На выходе ячейки i-ro типа формируется объединенная упорядоченная последовательность из двух чисел. На выходе ячейки ) log и(-го типа формируется
1 упорядоченный исходный массив. 3 нл.
98737 2
1 12
Изобретение относится к вычисли= тельной технике и может быть использовано в специализированных устройствах обработки информации.
Цель изобретения — упрощение уст— ройства.
На фиг. 1 дана схема устройства; на фиг. 2 и 3 — схемы ячеек первого и i-го типов.
З -1, Устройство содержит n/2 ячеек
1 «/2 «<14 38OQ < << L
1 — 1, 1 — 1, ..., 1
Ф
Б-го типа (где S = 1, 2, ...,)log n(;
n — количество сортируемых чисел;
1 ближайшее целое, не меньшее х), входы 2 и выходы 3. Каждая ячейка первого типа содержит блок 4 сравнения и коммутаторы 5, и 5, каждая ячейка i-го типа, где i = 2, 3,..., )log n(, содержит три подъячейки
6, 6, 6 (i-1) -го типа.
30 о 35
40 ь
Устройство работает следующим образом.
По входам 2 поступают числа, подлежащие сортировке. В каждой ячейке. первого типа блоком 4 сравнения срав ниваются два числа. Результат сравнения поступает на управляющие входы коммутаторов 5< и 5, которые формируют на выходах ячейки упорядоченную последовательность,из двух чисел.
Каждая ячейка 1 i-го типа, на
J входы которой поступают две упорядо1-1 ченные последовательности из 2 - r числа каждая, формирует на своих выходах упорядоченную последовательность из 2 чисел. Последняя ячейка
3Е1,(1, jlog n(-го типа формирует на своих выходах и на выходах 3 устройства упорядоченную последовательност из и чисел.
Формула изобретения
Устройство для сортировки чисел, содержащее (n-1) ячейку анализа первого типа, где п — количество сортируемых чисел, причем каждая ячейка анализа первого типа содержит блок сравнения и два коммутатора, первые информационные входы коммутаторов и блока сравнения объединены, вторые информационные входы коммутаторов и блока сравнения объединены, выход блока сравнения соединен с управляющими входами коммутаторов, выходы первого и второго коммутаторов являются выходами ячейки анализа первого типа, о т л и ч а ю щ е е с я тем, что, с целью упрощения устройства, оно содержит и-ю ячейку анали, -1 за первого типа и п/2 ячеек анализа i-го типа, где i = 2, 3, jlop n(, n — количество сортируемых чисел, )«(— ближайшее целое, не меньшее х, каждая ячейка анализа i ãî типа содержит первую, вторую и третью ячейки анализа (i — 1)-го типа, причем j é вход 1-й ячейки анализа . -го типа, где 3 =, 1, 2, ..., 2
1, 2, ..., n/2 подключен к (2 — mod j) ìó выходу ) 7/2(-й ячейки анализа (i-i)-ro типа, входы ячеек анализа первого типа являются входами сортируемых чисел устройства, выходы ячейки анализа j log nj-ro типа являются выходами устройства, К вЂ” и вход р-й ячейки анализа (i-1)-го ти— па каждой ячейки анализа i-ro типа, где К = 1, 2, ..., 2", р = 1, 2, является J К/2(+ 2 (1-mod2 K) + 2" (р — 1)-м входом данной ячейки анализа
i-ro типа, q-й выход первой ячейки анализа (i-1)-ro типа каждой ячейки анализа i-го типа, где q = 1, 2,..., 2" является q-м выходом этой ячейки анализа i-го типа, r-й вход третьей ячейки анализа (i — 1)-ro типа каждой ячейки анализа i — ro типа, где
«-1
r = 1, 2,..., 2 подключен к
r/2 + 2 (2-modzr) — му выходу (2-mod r)-й ячейки анализа (i — 1)-го
2 типа той же ячейки анализа (i-1) -го типа, r-й выход второй ячейки анализа (i-1)-го типа каждой ячейки анали—
«-2 за i-го типа является (r+2 )-м выходом той же ячейки анализа i-ro типа, (q + 2 )-й выход второй ячейки анализа (i-1) — ro типа каждой ячей« -2 ки анализа i-ro типа является (q+2 +
+2 „ )-м вьгходом той же ячейки анализа -го типа, первый и второй входы блока сравнения каждой ячейки анализа первого типа. являются соответственно первым и вторым входами ячейки анализа первого типа.
1298737
1 а/Я з
1„jk
13, и/р
/а/у
ФиИ
Фиа 2 г с вкюМ
Z дходо6 p 8xo3b8
ФигЗ
Составитель В. Горохов
Редактор Н. Егорова Техред М.Ходаиич Корректор А. Ильин
Заказ 890/51 Тираж 673 Подписное
ВНИИПИ Государственного комитета СССР по делам изобретений и открытий
113035, Иосква, Ж-35, Раушская наб., д. 4/5
Производственно-полиграфическое предприятие, г. Ужгород, ул.Проектная, 4
