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

112

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

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

На фиг. 1 дана схема устройства; на фиг. 2 и 3 - схемы ячеек первого и i-ro типов.

Устройство содержит п/2 ячеек

I n/ Z ( И)4.

1, 1, Ij 2

S-ro типа (где 5 1,2, . . . , п - количество сортируемых чисел; 1х - ближайшее целое, не меньшее х), входы 2 и выходы 3. Каждая ячейка первого типа содержит блок А сравнения и коммутаторы 5, и 5л, каждая ячейка i-ro типа, где i 2, 3,..., , содержит три подъячейки

, 6,

1-1

6j (i-l)-ro типа.

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

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

Каждая ячейка 1 i-ro типа, на входы которой поступают две упорядоченные последовательности из 2 -г числа каждая, формирует на своих выходах упорядоченную последовательность из 2 чисел. Последняя ячейка .. 1, Jlog nL-ro типа формирует на

своих выходах и на выходах 3 устройства 5 порядоченную последовательност из п чисел.

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

Устройство для сортировки чисел, содержащее (n-l) ячейку анализа первого типа, где п - количество сортируемых чисел, причем каждая ячейка анализа первого типа содержит блок сравнения и два коммутатора, первые информационные входы коммутаторов и блока сравнения объединены, вторые

37 .2

информационные входы коммутаторов м блока сравнения объединены, выход блока сравнения соединен с управляющими входами коммутаторов, выходы первого и второго коммутаторов являются выходами ячейки анализа первого типа,отличающееся тем, что, с целью упрощения устройства, оно содержит п-ю ячейку анализа первого типа и п/2 ячеек анализа i-ro типа, где i 2, 3, ... , jlogjn, n - количество сортируемых чисел, ближайшее целое, не меньшее X, каждая ячейка анализа i-ro типа содержит первую, вторую и третью ячейки анализа (i-l)-ro типа, причем j-й вход lf-й ячейки анализа i-ro типа, где j ,1, 2, ..., 2 , I 1, 2, ..., п/2 подключен к (2 - modjj)-My выходу ячейки анализа (i-1)-ro типа, входы ячеек анализа первого типа являются входами сортируемых чисел устройства, выходы ячейки анализа типа являются выходами устройства, К-й вход р-й ячейки анализа (i-1)-ro типа каждой ячейки анализа i-ro типа, где К 1. 2, ...,, , р 1, 2, является ( l-mod к) + 2 (р - 1)-м входом данной ячейки анализ i-ro типа, q-й выход первой ячейки анализа (i-l)-ro типа каждой ячейки анализа i-ro типа, где q 1, 2,..., 2 является q-м выходом зтой ячейки анализа i-ro типа, г-й вход треть ;ей ячейки анализа (i-l)-ro типа каждой ячейки анализа i-ro типа, где г 1, 2,. .. , 2 подключен к г/2 + (2-mod2r)-My выходу (2-modJr)-й ячейки анализа (i-l)--ro типа той же ячейки анализа (i-1)-ro типа, г-й выход второй ячейки анализа (i-1)ro типа каждой ячейки анализа i-ro типа является (г+2 )-м выходом той же ячейки анализа i-ro типа, (q,+ 2 )-й выход второй ячейки анализа (i-l)-ro типа каждой ячейки анализа i-ro типа является ( .)-м выходом той же ячейки анализа i-ro типа,первый и второй входы блока сравнения каждой ячейки анализа первого типа являются соответственно первым и вторым входами ячейки анализа первого типа.

|, 1ФФФ фффф .

1ПП . Г1/Jj

L

I

ГГП 11 И I 1

I I

ПИ III I 1 I ли

,,j,AAXJ.xj;j,a, 4f tf i -tf i/4f if -tf

1/Jj

ПИ III I 1 I ли

4f tf i -tf i/4f if -tf

L

It V

i Ф Ф ww vw V Vvv Фт J/ J u« Л J/

Фи.1

It V

vw V Vvv Фт J/ J u« Л J/

Изобретение относится к вычислительной технике. Цель изобретения - упрощение устройства. Устройство содержит п/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 ил.

5ГК- C5;

2 Sмдo8 i BxodoS

г -вхоЗо

л

Редактор Н. Егорова

.З

Составитель В. Горохов

Техред М.Ходанич Корректор А. Ильин

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

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

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

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