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

 

Изобретение относится к вычислительной технике и может быть использовано в системах, ориентированных на обработку упорядоченных массивов данных. Цель изобретения - повышение быстродействия устройства при увеличении количества чисел за счет одновременного попарного их анализа. Устройство содержит N блоков 1 анализа, каждый из которых со второго по (N-1)-й включает два элемента И 3 и 8, элемент ИЛИ, схему сравнения, регистр 2 и две группы элементов И 4, 5. Первый блок анализа содержит два элемента И 3 и 8, схему 7 сравнения, регистр 2 и группу элементов И 5, а N-й блок анализа - элемент И 3 регистр 2 и группу элементов И 4. Изобретение обеспечивает сортировку чисел в возрастающем либо убывающем порядке путем одновременного сравнения пар чисел с последующей при необходимости перезаписью их в соответствующие регистры в чередующихся тактах генератора импульсов. В четных тактах производится сравнение чисел нечетного слева и четного справа, а в нечетных - четного справа и нечетного слева. Такое чередование позволяет продвигать большие числа слева направо. При сортировке чисел в порядке убывания их массивов они подаются в устройство в обратных кодах. 1 ил.

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

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

РЕСПУБЛИК (19) (И)

А1 (51)5 G 06 F 7/06

P :((iiqrlg P

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

ll0 ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

Н А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Съ (21) 4622461/24-24 (22) 20.12.88 (46) 15.11.90. Бюл. Р 42 (72) В.Г.Попов, С.А,Удинцев и В.В.Туравинин (53) 681.325.5(088,8) (56) Авторское свидетельство СССР

lli 981988, кл, G 06 F 7/06, 1981.

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

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

Устройство содержит и блоков 1 анализа, каждый из которых со второго по (n-l)-й включает два элемента

И 3 и 8, элемент ИЛИ, схему сравнения, регистр 2 и две группы элементов

И 4, 5. Первый блок анализа содержит два элемента И 3 и 8, схему 7 сравнения, регистр 2 и группу элементов

И 5, а и-й блок анализа — элемент

И 3, регистр 2 и группу элементов

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

В четных тактах производится сравнение чисел нечетного слева и четного справа, а в нечетных — четного спр;— ва и нечетного слева ° Такое чередование позволяет продвигать большие числа слева направо. При сортировке чисел в порядке убывания их массивов они подаются в устройство в обратных кодах. 1 ил.

1606973

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

Целью изобретения является повышение быстродействия при увеличении количества чисел за счет одновременного понарного анализа чисел. !О

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

Устройство содержит блоки 1 анализа, каждый из которых, кроме,первого и последнего, включает регистр !5

2, элемент И 3, группы.элементов

И 4 и 5, элемент ИЛИ б, схему ? сравнения и элемент И 8, Первый блок 1 содержит регистр 2, элемент

И 3, группу элементов И 5, схему 7 20 сравнения и элемент И 8, а последний блок 1 — регистр 2, элемент

И 3, группу элементов И 5.

Кроме того, устройство содержит триггер 9 коммутации и элемент 10 25 задержки, элемент ИЛИ-НЕ 11, первый

12 и второй 13 элементы И, генератор

14. импульса;в, триггер 15 управления, информационные выходы 16 устройства, выход 17 готовности устройства и 30 вход 18 запуска устройства.

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

Исходное состояние устройства характеризуется тем, чта триггеры 9 и 15 установлены в нулевое состояние (цепи установки в "0" не показаны), В соответствующих регистрах 2 блоков 1 размещается массив исходных чисел. Работа устройства начинается 40 по сигналу пуска, поступающего по входу 18. Этим сигналом н единичное состояние устанавливается триггер

15. Единичным сигналом с единичного выхода триггера 15 открывается элемент И 12, чем обеспечивается подача импульсов с выхода генератора 4 на элементы схемы устройства.

Сортировка чисел массива, например, н возрастающем порядке, состоит из последовательности циклов, число которых определяется характером размещения исходного массива в регистрах 2.

Каждый цикл состоит из двух этапов, управляемых сигналами с единичного и нулевого выходов триггера 9. . Первый этап определяется нулевым сэстоянием триггера 9. На этом этапе производится одновременно попарное сравнение содержимого регистра 2 нечетных блоков 1 с содержимым регистра

2 соседних справа четных блоков 1.

Если в паре сравниваемых чисел большее из них оказалось в левом блоке I, то ана передается в правый блок 1, а число из этого блока переписывается в регистр левого блока 1, Таким образам, производится обмен числами между регистрами в каждой паре при соблюдении указанных условий сравни,мости. Па окончании первого этапа цикла триггер 9 устанавливается в единичное состояние. При этом сравниваются одновременно попарно числа четных и нечетных блоков 1 с аналогичным выполнением обменов как и в первом этапе.

Затем циклы повторяются до тех пар, пока все блоки 1 не сформируют сигналы о там, чта н соседнем справа блоке 1 находится большее число, Такой метод выявления больших чисел известен как метод пузырьков .

Рабату устройства рассмотрим при п=-4, и в регистрах 2 размещен массив чисел: А!=10, А =Я, Ay=4 Аз=5.

На входы схемы 7 сравнения блока ! < подаются числа А н A q на входы схемы 7 сравнения блока — числа А и Ag на входы схемы 7 сравнения блока 1 — числа Аэ и А1-, При этом на выходах " Больше" схемы 7 сравнения блока 1! формируется единичный curIl нал, так как А, ) А, на выходе Боль, ше" схемы 7 сравнения блока 1 — также единичный сигнал, так как А Аз, а на выходе "Больше" схемы 7 сравне ния блока 1> — нулевой сигнал, так как A А .

Так как триггер 9 находится в нулевом состоянии, то единичным сигналом с его нулевого выхода открыты элементы И 8 па вторым входам ва всех нечетных блоках l, т,е. в блоках 1 и 1, а также группы элементов И 3 по управляющим входам в этих грут пах.

Кроме того, так как только схемы 7 сравнения в блоках l и 1 формируют

33 ев единичный сигнал на выходах Больше то в блоке l! открыт элемент И 8, единичным сигналом с выхода которого открыт элемент И 3 по первому входу, а в блоке 1 — элемент И 3, На входах элемента ИЛИ-НЕ 11 ус сананливается позиционный кад !10, определяющий нулевой сигнал на ега выходе, 10

ЗО

5 . 1606

Этим нулевым сигналом элемент И 13 закрыт по первому входу. После поступления сигнала пуска по входу 18 триггер 15 устанавливается в единичное состояние, открывая элемент И 12 по второму входу.

По первому импульсу генератора, проходящему через элемент И !2 и далее через элементы И 3 в блоках 1 и

)g на синхровходы регистров 2, производится передача числа А в регистр

2 блока )q через группу элементов

И 4, а числа Ао — регистр 2 блока 1 через группу элементов И 5 ° Затем импульсом, задержанным элементом !О задержки, устанавливается в единичное состояние триггер 9, чем определяется второй этап первого цикла.

Таким образом, после первого эта" па в регистрах 2 блоков ) из последовательности чисел 10, 8, 4, 5 формиру ется последовательность 8, 10, 4, 5.

При таком расположении чисел схема 7 сравнения блока 1) формирует на выходе "Больше" нулевой сигнал (8 "- 10), схема 7 сравнения блока lq - единичный сигнал ()0 ) 4) и схема 7 сравнения блока I з — нулевой (4 < 5).

Поэтому, поскольку триггер 9 находится в единичном состоянии, в блоке 1 открыт элемент И 8, единичный сигнал с выхода которого через элементы

ИЛИ 6 в блоках I и 13 открывает по первым входам элементы И 3. На выходе элемента ИЛИ-НЕ 11 поддерживается нулевой сигнал, т.е. Hà его входах устанавливается позиционный код 010.

Вторым импульсом генератора )4, проходящим через элементы И )2 и И 3 в блоках 1 и на синхровходы регистров 2, обеспечивается перезапись кодов чисел через группы элементов

И 5 и 4 соответственно. По окончании переходных процессов н регистрах 2 блоков )q и )э последовательность чисел 8, 10, 4, 5 преобразуется в последовательность 8, 4, 10, 5, Через некоторое время импульсом, задержанным элементом 10 задержки, триггер 9 устанавливается в нулевое состояние.

Аналогично рассмотренному, но теперь уже по единичным сигналам с выходов "Больше" схем 7 сравнения в блоках I и 1 через открытые .элементы И 8 в этих блоках производится перезапись чисел в соседних блоках

1< и )а,.)э и )4-, При этом последо973 6 вательность чисел 8, 4, 10, 5 преобразуется в последовательность 4, 8, 5, 10.

После установки триггера 9 в единичное состояние открывается элемент

И 8 в блоке 1д (8 5), и по окончании второго этапа последовательность

4, 8, 5, 10 четвертым импульсом преобразуется в упорядоченную последовательность 4, 5, 8, 10. При этом на входах "Больше" схем 7 сравнения всех блоков 1 устацавливаются нулевые сигналы, по которым на выходе элемента ИЛИ-НЕ 11 формируется единичный сигнал, открывающий элемент И )3.

Пятым импульсом генератора 14 через элементы И !2, И 13 устанавливается триггер 1 в нулевое состояние.

Единичный сигнал с нулевого выхода триггера 15, поступающий на выход 17, используется в качестве сигнала готовности устройства к считыванию упорядоченного массива и сортировки очередного массива чисел.

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

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

Устройство для сортировки чисел, содержащее триггер управления, триггер коммутации, элемент задержки, два элемента И и и блоков анализа, где

n — - количество сравниваемых чисел, причем каждый блок анализа содержит регистр, элемент И и группу элементов

И, выходы которых соединены с информационными входами регистра, выходы разрядов которого являются информационными выходами блока анализа, каждый блок анализа, кроме n-ro, содержит дополнительно второй элемент И и схему сравнения, входы первой группы которой соединены с выходами регистра, блоки анализа с второго по (n-1)-й содержат дополнительно элемент ИЛИ и вторую группу элементов И, выходы которых объединены с выходами соответствующих элементов И первой группы, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия при увеличении количества соответствующих чисел, в него введены элемент

ИЛИ-НЕ и генератор импульсов, выход которого соединен с первым входом первого элемента И, выход которого

7 !606973 8

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

Техред Л.Олийнык Корректор И.Куска

Редактор Е.Копча

Заказ 35 i0 Тираж 564 Подписное

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

113035, Москва, )К"35„ Раушская наб., д. 4/5

Производственно-издательский комбинат Патент, г.ужгород, ул. Гагарина,!01

14 1Е соединен с первым входом второго элемента И, первыми входами первых элементов И всех блоков анализа и через элемент задержки подключен к счетному 5 входу триггера коммутации, инверсный выход которого подключен к управляющим входам элементов И первых групп нечетных блоков анализа, кроме п-го, управляющим входам элементов И вторых!О групп четных блоков анализа, кроме п-го, и к управляющим входам элементов И и-го блока анализа, а прямой выход — к управляющим входам элементов И первых групп четных блоков ана- 15 лиза и управляющим входам вторых групп нечетных блоков анализа, в каждом блоке анализа выход первого элемента И подключен к синхровходу регистра, в i-м блоке анализа, где 20

i=1,2,...,ï-1, управляющие входы элементов И первой группы соединены с первым входом второго элемента И, второй вход которого подключен к выходу схемы сравнения, в первом бло- 25 ке анализа выход второго элемента И соединен с вторым входом первого элемента И, выход второго элемента И

j-го блока анализа, где j=l 2,...„ã -2, соединен с первым входом элемента 30

ИЛИ (j+l)-ro блока анализа, выход второго элемента И (и-1)-го блока анализа соединен с вторым входом первого элемента И п-го блока анализа, в каждом блоке анализа с второго по (и-. !)-й выход второго элемента И дополнительно соединен с вторым входом элемента ИЛИ, выход которого подключен к второму входу первого элемента

И, выходы разрядов регистра j-го блока анализа соединены с информационными входами элементов И второй группы (3+1)-го блока анализа, выходы разрядов регистра (n-!)-го блока ана" лиза соединены с информационными входами элементов И и-го блока анализа, выходы разрядов регистра (i+l)-го блока анализа соединены с информационными входами элементов И первой группы -ro блока анализа, выходы схем сравнения всех блоков анализа подключены к входам элемента ИЛИ-ИЕ, выход которого соединен с вторым входом второго элемента И, выход которого соединен с входом установки в нулевое состояние триггера управления, вход установки в единичное состояние которого подключен к входу запуска устройства, прямой выход соединен с вторым входом первого элемента И, а инверсный выход триггера управления является выходом готовности устройства, информационные выходы блоков анализа являются выходами соответствующих отсортированных чисел устройства.