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

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано для формирования упорядоченного массива чисел. Цель изобретения - расширение функциональных возможностей за счет возможности сортировки чисел в едином массиве из исходных массивов. Устройство содержит блок 1 памяти входных массивов, коммутатор 2, два блока памяти 3 и 7, дешифратор 4, блок 5 подсчета массива из исходных массивов неравных объемов, элементы И 6,9 и 14, блок сравнения , блок элементов ИЛИ, буферный блок 11 памяти, выходной блок 12 памяти и группы 10 и 13 элементов И. 2 ил.

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

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

РЕСПУБЛИК (51)5 G 06 F 7/06

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) с й

ОПИСАНИЕ ИЗОБРЕТЕНИЯ- —::..

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4860073/24 (22) 14.08.90 (46) 23.08.93. Бюл. Ит 31 (72) Э.B.Áîðèñî8, А.В.Кошкарев и Д.А.Са-. панкевич (56) Авторское свидетельство СССР

М 538358, кл. 6 06 F 7/04, 1976.

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

М 881735, кл. G 06 F 7/06, 1979, (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ (57) Изобретение относится к автоматике и вычислительной технике и может быть ис„„59„1835543 А1 пользовано для формирования упорядоченного массива чисел. Цель изобретения— расширение функциональных возможностей за счет возможности сортировки чисел в едином массиве из исходных массивов.

Устройство содержит блок 1 памяти входных массивов, коммутатор 2, два блока памяти 3 и 7, дешифратор 4, блок 5 подсчета массива из исходных массивов неравных обьемов, элементы И 6,9 и 14, блок сравнения, блок элементов ИЛИ, буферный блок 11 памяти, выходной блок 12 памяти и группы

10 и 13 элементов И. 2 ил.

1835543

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

Цель изобретения — расширение функциональных возможностей устройства за счет возможности сортировки чисел в едином массиве из исходных массивов нерав- 10 кых объемов.

На фиг.1 представлена электрическая структурная схема устройства для сортировки чисел; на фиг.2 — схема блока подсчета массивов. 15

Устройство для сортировки чисел (фиг.1) содержит блок 1 памяти входных массивов, коммутатор 2, второй блок 3 памяти, дешифратор 4, блок 5 подсчета массивов, первый элемент И 6, первый блок 7 памяти, блок 8 20 сравнения, вторую группу 9 элементов И, группу 10 элементов ИЛИ, буферный блок

11 памяти, выходной блок 12 памяти, первую группу 13 элементов И, второй элемент

И 14. 25

Блок 5 подсчета массивов (фиг.2) содержит элемент ИЛИ 15, одновибратор 16, счетчик 17, блок 18 сравнения, регистр 19 и генератор 20 тактовых. импульсов (ГТИ).

Устройство для сортировки чисел раба- 30 тает следующим образом, Предварительно опишем решаемую задачу.

Пусть имеется N исходных массивов, в каждом из которых находится п = (1=1, N) 35 упорядоченных чисел. Необходимо из элементов этих исходных массивов составить

N единый массив, содержащий и = Х (ni) !

=1 40 упорядоченных чисел. Рассматриваемые массивы представляют собой, в нашем понимании, наборы чисел, записанных в фор- медвоичных кодов, последним элементом в каждом из которых является признак конца 45 массива, т.е. некоторый специфичный код, выходящий за рамки представления чисел.

Перед началом работы устройства на вход регистра 19 блока 5 подается число N упорядоченных массивов. Первый массив подается на информационный вход первого

50 блока 7 памяти, а остальные N-1 массивов

При вкЛючении блока 5 нэ его выходе последовательно формируются адреса регистров 1-i блока 1 памяти входных массивов, которые поступают нэ управляющий.. заносятся в блок 1 памяти входных массивов. Кроме того, обнуляется содержимое. первого блока 7 памяти, второго блока 3 55 памяти и буферного блока 11 памяти. вход коммутатора 2. В результате этого первый массив из блока 1 через коммутатор 2 поступает на информационный вход второго блока 3 памяти.

На четвертом выходе блока 5 появляется импульс, при поступлении которого на первый управляющий вход первого блока 7 памяти в него записывается первый массив чисел, а при поступлении этого импульса на второй управляющий вход второго блока 3 памяти происходит запись массива с выхода коммутатора 2 во второй блок 3 памяти.

Первое число из первого блока 7 памяти и первое число из второго блока 3 памяти поступают на первый и второй входы блока

8 сравнения, первый и второй входы дешифратора 4, а также на информационные входы первой 13 и второй 9 групп элементов И соответственно.

Если число, поступающее на первый вход блока 8 сравнения, меньше или равно числу, поступающему на его второй вход, то на втором выходе блока 8 появляется единичный потенциал, который поступает на второй вход первой группы 13 элементов И и открывает их. В результате этого число с информационного входа и первой группы 13 элементов И поступает на первый вход группы 10 элементов ИЛИ. Так как вторая группа элементов И в этот момент закрыта, то число через группу 10 элементов ИЛИ поступает в буферный блок 11 памяти. Кроме того, единичный потенциал со второго выхода блока 8 сравнения поступает на второй вход первого элемента И 6, В результате управляющий импульс с третьего выхода блока 5 через первый элемент И 6 поступает на второй управляющий вход первого блока 7 памяти. При этом содержимое первого блока

7 памяти продвигается на одну ячейку и на его выходе появляется второе число упорядочиваемого массива. После этого процесс сравнения. двух чисел повторяется.

Если число, поступающее на первый вход блока 8 сравнения, больше числа; поступающего нэ его второй вход, то íà первом выходе блока 8 сравнения появляется единичный потенциал, который, поступая на первый вход второй группы элементов И

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

9 поступает на второй вход группы 10 элементов ИЛИ. Так как первая группа элементов И 13 в этот момент закрыта, то число через группу 10 элементов ИЛИ поступает в буферный блок 11 памяти. Кроме того, единичный потенциал с первого выхода блока 8 сравнения поступает нэ первый вход второго элемента И 14 и управляющий импульс с третьего выхода блока 5 через второй эле1835543 мент И 14 поступает на первый управляю- И, о т л и ч а ю щ е е с я тем. что. с целью щий вход второго блока 3 памяти. При этом расширения функциональных возможносодержимое второго блока 3 памяти сдвига- стей за счет возможности сортировки чисел ется на одну ячейку и на его выходе появля-, в едином массиве из исходных массивов не ется второе число упорядочиваемого 5 равных объемов, в него введены второй массива. После этого процесс сравнения блок памяти, буферный блок памяти, выходдвух чисел повторяется. ной блок памяти, блок подсчета массивов, При появлении на выходе первого блока две группы элементов И, группа элементов

7 или второго блока 3 признака конца мас- ИЛИ, второй элемент И, дешифратор и блок сива происходит запись в буферный блок 11 10 памяти входных массивов, выходы которого памяти числа;появившегося на выходедру- соедияены с информационными входами гого блока памяти, поскольку блок 8 сравне- коммутатора, адресные входы которого соения интерпретирует признак конца массива - динены с информационными выходами блокак очень большое число. ка подсчета массивов, а выходы соединены

Описанный выше процесс сравнения 15 с информационными входами второго блодвух чисел заканчивается в тот момент, ког- ка памяти, выходы которого соединены с да на выходах первого 7 и второго 3 блоков входами второй группы блока сравнения, устанавливаются признаки конца массива. входы первой и второй групп блока сравB результате поступления двух признаков нения объединены с соответствующими конца массива на входы блока 8 сравнения 20 входами первой и второй групп дешифраодин из них записывается в буферный блок тора и с информационными входами эле11 памяти и становится признаком конца ментов И соответственно первой и второй упорядоченного массива, сформированного групп, управляющие входы которых соедииз элементов первого и второго массивов. нены соответственно с выходами "МеньКроме того, оба признака поступают на вхо- 25 ше" и "Больше" блока сравнения, а выходы ды дешифратора 4, который при этом фор- соединены с соответствующими первыми мирует на выходе единичный потенциал, и вторыми. входами элементов ИЛИ груп поступающий на вход блока,5, который из- пы, выходы которых соединены с информаменяет адрес на своем первом выходе и. ционными входами буферного блока формирует на своем четвертом выходе уп- 30 памяти, выходы которого соединены с инравляющий импульс, который поступает на формационными входами первого блока папервый управляющий вход первого блока 7 мяти и выходного блока па дяти, вход записи памяти, второй управляющий вход второго которого соединен с выходом результата блока 3 памяти и второй управляющий вход блока подсчета массивов, информационные буферного блока 11 памяти. 35 входы которого являются входами числа

При этом его содержимое записывается массивов устройства, а вход запуска — вхов первый блок 7 памяти, а во второй блок 3 дом запуска устройства, выход "Больше" памяти через коммутатор 2 записывается блокасравнения соединен с первым входом следующий упорядочиваемый массив из второго элемента И, второй вход которого блока 1 памяти входных массивов, адрес 40 соединен с тактовым выходом блока подсчекоторого поступает на.вход коммутатора 2 с та массивов, входом записи буферного блопервого выхода блока 5.. ка памяти и вторым входом первого

Описанный процесс упорядочивания элемента И, выходы первого и второго элеповторяется до тех пор, пока не будут отра- ментов И соединены с входами сдвига соотботаны все массивы из блока 1 памяти вход- .45 ветственно. первого и второго блоков ных массивов. После этого на втором памяти,входызаписикоторыхивходсчитывыходе блока 5 появляется единичный им- вания буферного блока памяти соединены с пульс, который поступает на управляющий выходом разрешения записи блока подсчевход выходного блока 12 памяти, и в выход- та массивов, вход приращения адреса катаной блок 12 памяти из буферного блока 11 50 рого соединен с выходом дешифратора. памяти. записывается результирующий ynO- . 2. Устройство по п,1. о т л и ч а ю щ е е-.. рядоченный массив. с я тем, что блок подсчета массивов содерФ о р м у л а и з о б р е т е н и я жит генератор тактовых импульсов, регистр, 1. Устройство для сортировки чисел, со- одновибратор. схему сравнения, счетчик, держащее-первый блок памяти блок сравне- 55, элементы ИЛИ и задержки, причем вход зания, коммутатор и первый элемент И, пуска блока соединен с входом запуска гепричем выходы первого блока памяти сое- нератора тактовых импульсов, входом динены с входами первой группы блока сброса счетчика, записи регистра и первым сравнения, выход "Меньше" которого под- входом элемента ИЛИ, второй вход котороключен к первому входу первого элемента . го является входом приращения адреса бло1835543

Вкл

Составитель Д. Сапанкевич

Техред М.Моргентал Корректор В. Петраш

Редактор А. Козлова

Заказ 2982 Тираж Подписное

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101 ка, а выход соединен с входом одновибратора, выход которого является выходом рэзр-ешения записи блока и подключен к счетному входу счетчика и через элемент задержки к входу разрешения счета счетчика, выходы разрядов которого являются информационными выходами блока и входами первой группы схемы сравнения, входы второй группы которого соединены с выходами регистра, информационные входы которого являются информационными входами блока, выход схемы сравнения является выхо5 дом результата блока и подключен к входу останова генератора тактовых импульсов, выход которого является тактовым выходом блока,