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

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

Иллюстрации

Показать все

Реферат

 

УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ по авт. св. № 981988, о тличающееся тем, что, с целью расширения функциональных возможностей за счет обеспечения возможности сортировки массива, содержащего равные числа, в него введены n-l элементов запрета, где тколичество сортируемых чисел, причем прямой вход 1-го ( 1 1, 2, ..., trrt) элемента запрета подключен к выходу Равно ( л + 1)-го элемента сравнения, а выход соединен с (tri-ь i )-м входом счетчика, 2rv-n вход которого подключен к выходу Равно первого элемента сравнения, -к выход распределителя импульсов ( i 1, 2 , . .. , rn-l) соединен с i-ми инверсными входами элементов запрета с i-ro по (т-1)-й включительно .

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

СО1 1ИАЛИСТИЧЕСНИХ

РЕСПУБЛИН (19) (И) у С 06 F 7/06

ГОСУДАРСТВЕННЫЙ HOMHTET СССР

ПО ДЕЛАМ ИЭОБРЕТЕНИЙ И ОТКРЫТИЙ

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

Н АВТОРСНОМУ СВИДЕТЕЛЬСТВУ (61) 981988 (21) 3418209/18-24 (22) 05.04.82 (46) 15.05.84. Бюл. ¹ 18 (72) Э.П. Чернаков и В.М. Цыганков (53) 681 ° 325.66(088.8) (56) 1 ° Авторское свидетельство СССР № 981988, кл. G 06 F 7/06, 1980. (54) (57) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ

ЧИСЕЛ по авт. св. № 981988, о тл и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет обеспечения возможности сортировки массива, содержащего равные числа, в него введены в-1 элементов запрета, где rn - количество сортируемых чисел, причем прямой вход i-го (1 = 1, 2, тг1) элемента запрета подключен к выходу "Равно" (+ 1)-го элемента сравнения, а выход соединен с

1 (л + )-м входом счетчика, 2m-и вход которого подключен к выходу

"Равно" первого элемента сравнения, 1-й выход распределителя импульсов (1 = 1, 2, ...,m-1) соединен с

i-ми инверсными входами элементов запрета с i-ro no (rn-1)-й включительно.

92494 2 ства за счет обеспечения воэможнос1 10

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

По основному авт. св. У 981988 известно устройство для сортировки чисел, содержащее распределитель импульсов, т регистров, rn элементов сравнения, m групп элементов И, счетчик, сумматор и регистр результата, причем выходы 1-го (i = 1, 2, ...,п ) регистра соединены с первой группой входов 1 -ro элемента сравнения и с первыми входами элементов И 1-й группы, выходы которых соединены с -й группой входов регистра результата с (i -й)-ми группами входов элементов сравнения с первого по (i — 1)-й и с 1 -ми группами входов элементов сравнения с (i + 1)-го по m-é, первый управляющий вход устройства является входом распределителя импульсов, каждый 1 -й выход которого соединен 25 с вторыми входами элементов И 1 -й группы, выход i --rn элемента сравнения соединен с i --м входом счетчика, выходы которого соединены с первой группой входов сумматора, вто- ЗО рая группа входов которого соединена с группой информационных входов устройства, а выходы — с первыми входами элементов И первой выходной группы, выходы которых являют35 ся первой группой выходов устройства, первые входы элементов и второй выходной группы соединены с выходами регистра результата, а выходы являются второй группой выходов устройства ii). ти сортировки массива, содержащего равные числа.

Поставленная цель достигается тем, что в устройство для сортировки чисел введены т — 1 элементов запрета, где e — количество сортируемых чисел, причем прямой вход j -го (= 1, 2, ...., ю -a) элемента запрета подключен к выходу "Равно (i + 1)-го элемента сравнения, а выход соединен с (m+ 1)-м входом счетчика, 2m -й вход которого подключен к выходу Равно первого элемента сравнения, 1 -й выход распределителя импульсов (i = 1, 2, ... m — 1) соединен с 1-ми инверсными входами элементов запрета с

>-го по (rn-1)-й включительно, На чертеже приведена схема устройства.

Устройство содержит распределитель 1 импульсов, группу регистров

2 2, руопу эл нения, группы 41-4, 5 и 6 элементов И, счетчик 7, сумматор 8, регистр 9 результата, управляющие входы 10 и 11, группу 12 информационных входов, группы 13 и 14 информационных выходов и группу элементов 15„- 15„ запрета.

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

В регистры 2 заносятся сортируемые числа, в регистр 9 результата — нуль, а распределитель 1 импульсов устанавливается в начальное состояние (на схеме не показано). После этого устройство готово к сортировке чисел в порядке возрастания.

Недостатком данного устройства являются ограниченные функциональные возможности, так как оно не позволяет сортировать массив чисел, содержащий равные элементы. В спучае, если в массиве находятся К равных чисел, то для них устройством определяется один и тот же адрес области памяти, куда они должны быть помещены. Поэтому все эти числа будут записаны по одному адресу, оставив незаполненными предыдущие

К- 1 ячеек. Таким образом, из К равных чисел при сортировке потеряно

k — 1 число.

Цель изобретения — расширение функциональных возможностей устройТеперь на вход 10 устройства подается первый тактовый сигнал, по которому появляется импульс на первом выходе распределителя 1 импульсов. При этом открывается первая группа 4 элементов И и число из первого регистра 2 переписывается в регистр 9 результата и одновременно с этим подается на соответствующие группы входов элементов 3 — 3 срав2 rn нения, которыми оно сравнивается со всеми остальными сортируемыми числами. Сигнал "Меньше на выходах элементов 3 сравнения появляется лишь в том случае, если числа, находящиеся в соответствующем регистре 2, меньше числа, поступаемого

1092494 на вторые входы элемента 3 сравнения через группы 4 элементов И. В случае равенства числа из первого регистра 2 нескольким числам на выходах "Равно" соответствующих элементов сравнения появляются сигналы.

Эти сигналы поступают на схему приоритета, состоящую из элементов 15 запрета. В данном случае сигналом с первого выхода распределителя 1 им-. 1О пульсов все элементы 15 запрета закрыты. Счетчик 7 подсчитывает количество поступающих сигналов с элементов 3 сравнения, т.е. подсчитывает количество чисел, которые меньше, чем 1 выделенное распределителем 1 импульсов и записанное в регистр 9 результата с учетом порядкового номера этого числа среди равных чисел. Это число поступает на первую группу 2О входов сумматора 8, а на его вторую группу входов — код адреса области памяти, начиная с которого необходимо разместить отсортированный массив чисел. Тогда адрес области памя- 2", ти, по которому следует записать число, находящееся в регистре 9 результата, определяется следующим образом:

4нич где А — адрес области памяти, нан ч чиная с которого необходимо разместить отсортированные числа;

М вЂ” количество чисел, меньших числа, записанного в регистре 9 результата; порядковый номер числа среди равных чисел в массиве.

Сумматор 8 вычисляет сумму

А„„ч +I< 1. По сигналу.на управляющем входе 11 устройства число, 4> находящееся в регистре 9 результата, переписывается в запоминающее устройство по адресу, находящемуся в сумматоре 8. Следующий такт работы устройства начинается с подачи следующего тактового сигнала на вход 10 устройства. При этом появляется импульс на следующем выходе распределителя 1 импульсов, который открывает следующую группу

4 элементов И, вследствие чего в регистр 9 результата переписывается число из следующего регистра

2 и одновременно с этим осуществ2 ляется сравнение этого числа с остальными числами. Если второе число равно первому, то элемент 3

1 сравнения, соответствующий первому регистру 2,выдаст сигнал равенства, который поступит на вход счетчика 7. Если в массиве сортируемых чисел окажутся еще числа, равные второму числу, импульсы с соответствующих элементов 3 сравнения не поступят на вход счетчика 7, так как все остальные элементы 15 — 15 зап3 rn-s рета будут закрыты импульсом с второго выхода распределителя 1 импульсов. В дальнейшем устройство работает аналогично описанному.

Для сортировки чисел в порядке убывания необходимо в регистры 2 записать инверсные коды сортируемых чисел.

Таким образом, предлагаемое устройство по сравнению с известным имеет более широкие функциональные возможности, так как позволяет сортировать массивы чисел, содержащие равные числа. Введение в схему элементов запрета и использование дополнительных выходов "Равно" элементов сравнения позволяет изменять адреса равных чисел таким образом, что эти числа располагаются подряд в ячейках памяти, благодаря чему в предлагаемом устройстве исключается потеря K — 1 числа в сортируемом массиве, содержащем К равных чисел.

1092494

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

Редактор М. Петрова Техред Ж.Кастелевич Корректор C° . Шекмар

Заказ 3255/32 Тираж 699 Подписное

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

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

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4