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

(51)5 С 06 Р 7/06 ОСУДАРСТВЕННЫО ИЗОБРЕТЕНИЯМРи ГКнт СССР ИТЕТЫТИЯМ с САНИЕ ИЗОБРЕТ нцев ельство СССР /06, 1981, ство СССР 7/06, 1983,АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИС(57) Изобретение относится к вычислительной технике и может быть использовано в системах, ориентированных на обработку упорядоченных массивов данных. Цель изобретения - повышение быстродействия устройства приувеличении количества чисел за счетодновременного попарного их анализа,Устройство содержит и блоков 1 анализа, каждый из которых со второгопо (и)-й включает два элемента И 3 и 8, элемент ИЛИ, схему сравне-.ния, регистр 2 и две группы элементовИ 4, 5. Первый блок анализа содержитдва элемента И 3 и 8, схему 7 сравнения, регистр 2 и группу элементовИ 5, а и-й блок анализа - элементИ 3, регистр 2 и группу элементовИ 4. Изобретение обеспечивает сортировку чисел в возрастающем либоубывающем порядке путем одновременного сравнения пар чисел с последующей при необходимости перезаписьюих в соответствующие регистры в чередующихся тактах генератора импульсов,В четных тактах производится сравнение чисел нечетного слева и четногосправа, а в нечетных - четного спр; -ва и нечетного слеваТакое чередование позволяет продвигать большиечисла слева направо. При сортировкечисел в порядке убывания их массивов они подаются в устройство в обратных кодах. 1 илИзобретение относится к вычислительной технике и может быть использовано в системах, ориентированныхна обработку упорядоченных массивовчисел.Целью изобретения является повышение быстродействия при увеличенииколичества чисел за счет одновременного понарного анализа чисел. 10На чертеже изображена схема устройства,Устройство содержит блоки 1 анализа, каждый из которых, кроме,первого и Ьоследнего, включает регистр 152, элемент И 3, группы.элементовИ 4 и 5, элемент ИЛИ б, схемусравнения и элемент И 8, Первыйблок 1 содержит регистр 2, элементИ 3, группу элементов И 5, схему 7 20сравнения и элемент И 8, а последний блок 1 - регистр 2, элементИ 3, группу элементов И 5,Кроме того, устройство содержиттриггер 9 коммутации и элемент 1025задержки, элемент ИЛИ-НЕ 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, Если в паре сравниваемых чисел большее иэ них оказалось в левом блоке то ана передается в правый блок 1, а число из этого блока переписывается в регистр левого блока 1, Таким образам, производится обмен числами между регистрами в каждой паре при соблюдении указанных условий сравни" ,мости, Па окончании первого этапа цикла триггер 9 устанавливается в единичное состояние. При этом сравниваются одновременно попарно числа четных и нечетных блоков 1 с аналогичным выполнением обменов как и впервом этапе.Затем циклы повторяются до техпар, пока все блоки 1 не сформируютсигналы о там, чта н соседнем справа блоке 1 находится большее число,Такой метод выявления больших чиселизвестен как метод пузырьков .Рабату устройства рассмотрим прип.=4, и в регистрах 2 размещен массивчисел: А=10, Ао=8, А=4, Аз=5.На входы схемы 7 сравнения блока1 подаются числа Ан Ад, на входысхемы 7 сравнения блока 1 - числа Аи АЭ, на входы схемы 7 сравнения блока 1 - числа Аэ и А, При этом навыходах "Больше" схемы 7 сравненияблока 1 формируется единичный сиг 11нал, так как А, ) А, на выходе Боль,ше" схемы 7 сравнения блока 1 а - также единичный сигнал, так как А) Аз,а на выходе "Больше" схемы 7 сравнения блока 1 э - нулевой сигнал, таккак АэАФ.Так как триггер 9 находится в нулевом состоянии, то единичным сигналом с его нулевого выхода открытыэлементы И 8 па вторым входам ва всехнечетных блоках 1, т,е. в блоках 1и 1, а также группы элементов И 3 поуправляющим входам в этих грут.пах.Кроме того, так как только схемы 7сравнения в блоках 1 и 1 Формируют1 евединичный сигнал на выходах Большето в блоке 1 открыт элемент И 8,единичным сигналом с выхода которогооткрыт элемент И 3 по первому входу,а в блоке 1 - элемент И 3, На входахэлемента ИЛИ-НЕ 11 устанавливаетсяпозиционный кад 110, определяющийнулевой сигнал на ега выходе,10 15 20 25 ЗО 35 40 45 50 55 5 . 1606Этим нулевым сигналом элемент И 13закрыт по первому входу. После поступления сигнала пуска по входу 18триггер 15 устанавливается в единичное состояние, открывая элемент И 12по второму входу.По первому импульсу генератора,проходящему через элемент И 2 и далее через элементы И 3 в блоках 1 ид на синхровходы регистров 2, производится передачачисла Ав регистр2 блока 1 через группу элементовИ 4, а числа А - регистр 2 блока 1через группу элементов И 5Затемимпульсом, задержанным элементом Озадержки, устанавливается в единичное состояние триггер 9, чем определяется второй этап первого цикла.Таким образом, после первого эта"па в регистрах 2 блоковиз последовательности чисел 1 О, 8, 4, 5 формиру ется последовательность 8, 1 О, 4, 5,При таком расположении чисел схема 7 сравнения блока 11 формирует навыходе Больше" нулевой сигнал(810), схема 7 сравнения блока 1 -единичный сигнал (О) 4) и схема 7сравнения блока 1 з - нулевой (45).Поэтому, поскольку триггер 9 находится в единичном состоянии, в блоке 1открыт элемент И 8, единичный сигналс выхода которого через элементыИЛИ 6 в блоках 1 и 3 открывает попервым входам элементы И 3. На выходе элемента ИЛИ-НЕ 11 поддерживаетсянулевой сигнал, т.е. на его входахустанавливается позиционный код 010,Вторым импульсом генератора 14,проходящим через элементы И 12 и И 3в блоках 1 ина синхровходы регистров 2, обеспечивается перезаписькодов чисел через группы элементовИ 5 и 4 соответственно. По окончаниипереходных процессов н регистрах 2блоков 1 и 1 э последовательностьчисел 8, 10, 4, 5 преобразуется в последовательность 8, 4, 10, 5,Через некоторое время импульсом,задержанным элементом О задержки,триггер 9 устанавливается в нулевоесостояние.Аналогично рассмотренному, но теперь уже по единичным сигналам с выходов "Больше" схем 7 сравнения вблоках 1 и 1 через открытые .элементы И 8 в этих блоках производитсяперезапись чисел в соседних блоках1 и 1 а,.з и 14, При этом последо 973 6 вательность чисел 8, 4, 10, 5 преобразуется в последовательность 4, 8, 5, 1 О.После установки триггера 9 в единичное состояние открывается элемент И 8 в блоке 1 д (8 T 5), и по окончании второго этапа последовательность 4, 8, 5, 10 четвертым импульсом преобразуется в упорядоченную последовательность 4, 5, 8, 1 О. При этом на входах "Больше" схем 7 сравнения всех блоков 1 устацавливаются нулевые сигналы, по которым на выходе элемента ИЛИ-НЕ 11 формируется единичный сигнал, открывающий элемент И 13.Пятым импульсом генератора 14 через элементы И 2, И 13 устанавливается триггер 1 в нулевое состояние. Единичный сигнал с нулевого выхода триггера 5, поступающий на выход 17, используется в качестве сигнала готовности устройства к считыванию упорядоченного массива и сортировки очередного массива чисел.При необходимости получения массива, упорядоченного по убыванию значений чисел, их следует подавать в регистры 2 в обратных кодах. Формула изобретения Устройство для сортировки чисел, содержащее триггер управления, триггер коммутации, элемент задержки, два элемента И и и блоков анализа, где и - количество сравниваемых чисел, причем каждый блок анализа содержит регистр, элемент И и группу элементов И, выходы которых соединены с информационными входами регистра, выходы разрядов которого являются информационными выходами блока анализа, каждый блок анализа, кроме п-го, содержит дополнительно второй элемент И и схему сравнения, входы первой группы которой соединены с выходами регистра, блоки анализа с второго по (и)-й содержат дополнительно элемент ИЛИ и вторую группу элементов И, выходы которых объединены с выходами соответствующих элементов И первой группы, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия при увеличении количества соответствующих чисел, в него введены элемент ИЛИ-НЕ и генератор импульсов, выход которого соединен с первым входом первого элемента И, выход которого7 1606973 8 Составитель Е,ИвановаТехред Л,Олнйньцс Корректор И.Куска Редактор Е,Копча Заказ 3550 Тираж 564 ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР113035, Москва, Ж"35 Раущская наб., д. 4/5 Производственно-издательский комбинат Патент , г,ужгород, ул. Гагарина,01зч е соединен с первым входом второго элемента И, первыми входами первых эле"ментов И всех блоков анализа и черезэлемент задержки подключен к счетному 5входу триггера коммутации, инверсныйвыход котопого подключен к управляющим входам элементов И первых группнечетных блоков анализа, кроме п-го,управляющим входам элементов И вторых 10групп четных блоков анализа, кромеп-го, и к управляющим входам элементов И и-го блока анализа, а прямойвыход - к управляющим входам элементов И первых групп четных блоков анализа и управляющим входам вторыхгрупп нечетных блоков анализа, вкаждом блоке анализа выход первогоэлемента И подключен к синхровходурегистра, в 1-м блоке анализа, где3.=1,2п, управляющие входы элементов И первой группы соединены спервым входом второго элемента И,второй вход которого подключен квыходу схемы сравнения, в первом блоке анализа выход второго элемента Исоединен с вторым входом первого элемента И, выход второго элемента И3-го блока анализа, где 3=1,2,г,соединен с первым входом элемента 30ИЛИ Ц+1)-го блока анализа, выходвторого элемента И (п)-го блокаанализа соединен с вторым входом первого элемента И п-го блока анализа,в каждом блоке анализа с второго по(и)-й выход второго элемента И дополнительно соединен с вторым входомэлемента ИЛИ, выход которого подключен к второму входу первого элементаИ, выходы разрядов регистра 3-го блока анализа соединены с информационными входами элементов И второй группы (3+1)-го блока анализа, выходыразрядов регистра (и)-го блока ана"лиза соединены с информационными вхо"дами элементов И и-го блока анализа,выходы разрядов регистра (д+1)-го блокаанализа соединены с информационнымивходами элементов И первой группыч-го блока анализа, выходы схем сравнения всех блоков анализа подключенык входам элемента ИЛИ-ИЕ, выход кото"рого соединен с вторым входом второго элемента И, выход которого соединен с входом установки в нулевое состояние триггера управления, вход установки в единичное состояние которого подключен к входу запуска устройства, прямой выход соединен с вторымвходом первого элемента И, а инверсный выход триггера управления является выходом готовности устройства,информационные выходы блоков анализаявляются выходами соответствующих от"сортированных чисел устройства.