Пристрій для ранжування чисел

Пристрій для ранжування чисел, що містить n регістрів, схеми порівняння, n лічильників, де n кількість сортованих чисел, виходи розрядів i-го лічильника є виходами рангу і-го числа пристрою, де і=1, ..., n, який відрізняється тим, що в нього введено селектор кодів, комутатор і елемент АБОНІ, причому перша і друга групи n входів пристрою є відповідно входами елементів вхідного масиву чисел та їхніх початкових рангів, перша гр упа n 3 34516 4 Найбільш близьким за технічною суттю є припопарно з'єднані з входами К схем порівняння, де стрій для ранжування чисел [а.с. СРСР №1363184, К = ]n/2[- ціла частина числа n/2, інформаційні кл. G06F7/06, 1987р., Бюл. №48], який містить розвходи комутатора з'єднані з виходами ознаки відподілювач імпульсів, n регістрів, n схем порівнянповідних К схем порівняння, а інформаційні виходи ня, де n- кількість сортованих чисел, гр упи елемез'єднані з входами інкременту/декременту відповінтів І перезапису чисел, вузол підрахунку кількості дних n лічильників, інформаційні входи яких підодиниць, проміжний регістр, n тригерів, n елеменключені до другої гр упи n входів пристрою, а інфотів І аналізу першої групи, причому виходи розрярмаційні виходи є групою n виходів пристрою, крім дів і-го регістра, де і=1,..., n, з'єднані з входами того інформаційні виходи n лічильників з'єднані з першої групи і-ої схеми порівняння, входи другої відповідними входами керування селектора кодів і групи якої з'єднані з виходами розрядів проміжного комутатора, вхід керування пристрою з'єднаний з регістра, перший вихід підключений до першого входом керування циклічністю роботи селектора входу і-го елемента І аналізу першої групи, другий кодів, а виходи ознаки К схем порівняння з'єднані з вхід якого з'єднаний з прямим виходом і-го тригевідповідними входами елемента АБО-НІ, ви хід ра, вхід встановлення в одиничний стан якого якого є виходом сигналу "Кінець" пристрою. з'єднаний з і-м виходом розподілювача імпульсів і На Фіг.1 представлено блок-схему пристрою входами керування елементів І перезапису чисел для ранжування чисел, на Фіг.2 і 3 представлено і-ої групи, тактовий вхід розподілювача імпульсів топологію з'єднань елементів масиву чисел, яку підключений до тактового входу пристрою, крім реалізує селектор кодів, відповідно для парної і того пристрій містить n елементів І аналізу другої непарної розмірності масиву n чисел. групи, n груп елементів І перезапису рангу і n лічиПристрій для ранжування чисел (Фіг.1) містить льників, причому інформаційні входи пристрою n регістрів 11..,1n , де n- кількість сортованих чисел з'єднані з інформаційними входами відповідних (елементів у масиві чисел), К схем порівняння елементів І перезапису чисел (n+1)-ої групи, входи 21,...,2К, де К=]n/2[ - ціла частина числа n/2, n лічикерування яких підключені до тактового входу прильників 31, ...,3n, селектор кодів 4 і комутатор 5. строю, а ви ходи з'єднані з інформаційними входаКрім того, пристрій містить входи 61,..., 6n та 71,..., ми проміжного регістра, виходи розрядів якого 7n пристрою, які є відповідно входами елементів з'єднані додатково з відповідними інформаційними вхідного масиву чисел та їхніх початкових рангів, входами елементів І перезапису чисел і-х гр уп, виходи 81; ...,8n рангів пристрою. Входи 61...,6n привиходи елементів І перезапису чисел і-ої гр упи строю з'єднані з інформаційними входами регістрів з'єднані з інформаційними входами і-го регістра, 11...,1 n, інформаційні виходи яких підключені до другий ви хід і-ої схеми порівняння підключений до інформаційних входів селектора кодів 4, інформапершого входу і-го елемента І аналізу другої гр упи, ційні виходи якого попарно з'єднані з входами другий вхід якого з'єднаний з прямим виходом і-го схем порівняння 21... ,2K. Інформаційні входи комутригера, а вихід з'єднаний з входом лічби і-го лічитатора 5 з'єднані з виходами ознаки відповідних льника, виходи розрядів якого є виходами рангу ісхем порівняння 21,..., 2К, а інформаційні виходи го числа пристрою, а інформаційні входи з'єднані з з'єднані з входами інкременту/декременту відповівиходами відповідних елементів І перезапису рандних лічильників 31;..., 3n, ін формаційні входи яких гу і-ої гр упи, входи керування яких підключені до іпідключені до входів 71,..., 7n пристрою, а інфорго виходу розподілювача імпульсів, виходи елемемаційні виходи є виходами 81,...,8n рангів принтів І аналізу першої групи з'єднані з входами вузстрою. Крім того, інформаційні виходи лічильників ла підрахунку кількості одиниць, виходи якого з'єд31,...,3n з'єднані з відповідними входами керування нані з інформаційними входами відповіднихселектора кодів 4 і комутатора 5, вхід 9 керування елементів І перезапису рангу всіх гр уп. пристрою з'єднаний з входом керування циклічнісНедоліком цього пристрою є недостатня тю роботи селектора кодів 4, а виходи ознаки схем швидкодія, оскільки він сортує числа з ранжуванпорівняння 21,..., 2K з'єднані з відповідними входаням в процесі їхнього послідовного подання у прими елемента АБО-НІ 10, ви хід якого є виходом 11 стрій. сигналу "Кінець" пристрою. В основу корисної моделі поставлено задачу Сортування масиву чисел шляхом попарного створення пристрою для ранжування чисел, в обміну без використання рангів виконуються в таякому за рахунок введення нових вузлів та зв'язків кий спосіб. У першому і всіх непарних циклах поміж ними досягається зменшення часу сортування парно порівнюють сусідні елементи масиву у (2kмасиву чисел. 1)-х і 2k-х позиціях і більший з них за значенням Поставлена задача вирішується тим, що у переміщують або залишають у 2k-й позиції, а пристрій для ранжування чисел, який містить n менший переміщують або залишають у (2к-1 )-й регістрів, схеми порівняння, n лічильників, де nпозиції, де k = 1,.. .,K. кількість сортованих чисел, виходи розрядів і-го У другому і всі х парних циклах попарно порівлічильника є виходами рангу і-го числа пристрою, нюють сусідні елементи масиву у 2k-х і (2k+1)-х де і=1,...,n, введено селектор кодів, комутатор і позиціях і більший з них за значенням переміщуелемент АБО-НІ, причому перша і друга групи n ють або залишають у (2k+1)-й позиції, а менший входів пристрою є відповідно входами елементів переміщують або залишають у 2k-й позиції. вхідного масиву чисел та їхніх початкових рангів, Сортування шляхом попарного обміну з ввеперша група n входів пристрою з'єднана з відповіденням рангів елементів масиву має такий вигляд. дними інформаційними входами n регістрів, інфо1. Перед сортуванням усім елементам масиву рмаційні виходи яких підключені до інформаційних присвоюють ранги, які відповідають номерам їхніх входів селектора кодів, інформаційні виходи якого позицій у масиві. 5 34516 6 2. Формують групу пар із сусідніх елементів дів 4 і комутатора 5 перед початком наступного масиву чисел незалежно від кількості n елементів циклу сортування. масиву за таким правилом: а) у всіх непарних цикОдночасно перевіряють виконання умови лах кожна пара елементів складається з (2k-1)-х і (п.4), тобто наявність одиничного сигналу на вихо2k-х елементів (k = 1,..., K); б) у всіх парних циклах ді 11 елемента АБО-НІ 10, що можливо при відсукожна пара елементів складається з 2k-х і (2k+1)-х тності одиничних сигналів на виходах ознаки всіх елементів. схем порівняння 21,..., 23. Оскільки для першого 3. У кожній парі елементів за результатом поциклу це не суттєво , тому змінюють сигнал на вхорівняння виконують такі дії: а) якщо елемент моді 9 керування пристрою на протилежний, який лодшої позиції менший за значенням, ніж елемент подають на вхід керування циклічністю роботи старшої позиції, то ранги елементів не змінюють; селектора кодів 4, в результаті чого починають б) якщо елемент молодшої позиції більший за знавиконання другого (парного) циклу сортування. Він ченням ніж елемент старшої позиції, то ранги зміскладається з формування відповідних пар сусіднюють таким чином: ранг елемента молодшої поніх елементів масиву чисел (п.2б) селектором козиції збільшують на одиницю, ранг елемента дів 4, попарного порівняння у схемах порівняння більшої позиції зменшують на одиницю. 21;..., 23, комутації сигналів ознаки з виходів ознаки 4. Перевіряють умову відсутності будь-якої схем порівняння 21, ..., 23 комутатором 5, формузміни рангів у всіх парах елементів. Якщо ця умова вання рангів чисел масиву у лічильниках 31,..., 36 в виконується і це не перший цикл, то виконують процесі збільшення/зменшення їхнього стану. Зміперехід до п.5; якщо ця умова не виконується, а нені значення рангів з виходів лічильників 31; ...,36 також якщо це перший цикл, то виконують перехід знову подають на входи керування селектора кодо п.2. дів 4 і комутатора 5 перед початком наступного 5. Процес сортування закінчується. циклу сортування. Приклади сортування масиву чисел без ранПроцес сортування з ранжуванням елементів жування і з введенням рангів елементів масиву масиву по циклах представлено у табл.2. Після показано у табл. 1,2 відповідно. Тут застосовано кожного циклу сортування перевіряють умову (п.4) такі умовні позначення: ] - ознака пари елементів, у вигляді наявності чи відсутності одиничного сигналу на виході 11 елемента АБО-НІ 10. Якщо одищо порівнюють; - ознака переміщення (транспоничний сигнал на виході 11 елемента АБО-НІ 10 зиції) елементів у відповідній парі, ↱↲ - ознака відсутній, то змінюють сигнал на вході 9 пристрою зменшення/збільшення відповідних рангів елеменна протилежний і починають виконання наступного тів. Елементи масиву взято з діапазону цілих допарного/непарного циклу сортування. Так продовдатних чисел (0, 9). Масив рангів елементів склажується процес сортування з ранжуванням. Він дається з діапазону цілих чисел від 1 до 6. закінчується з появою одиничного сигналу на виНаприкінці сортування виконують один контрольході 11 сигналу „Кінець" пристрою. Отже, у лічильний цикл. никах 31; ...,36 сформовано відповідні ранги елемеРозглянемо сортування масиву чисел, який нтів відсортованого масиву чисел, а саме, складається, наприклад, з шести чисел найбільшому за значенням елементу масиву чи{7,9,1,5,4,2} (табл.2). Ці числа записують по входах сел відповідає максимальний ранг, а найменшому 61;...,66 пристрою у відповідні регістри 11 ...,16. Од- мінімальний (одиничний) ранг. Сформовані ранги ночасно по входах 71;...,76 пристрою у лічильники в подальшому використовують для зчитування 31,...,36 записують масив початкових рангів елемечисел з регістрів 11;..., 16 або за збільшенням, або нтів у вигляді послідовності номерів позицій відпоза зменшенням їхніх значень, тобто формують відних елементів у масиві, а саме {1,2,3,4,5,6}. відсортований масив чисел за зростанПісля цього з подачею зі входу 9 керування приням/спаданням. строю відповідного сигналу (наприклад, нульовоТаким чином, для наведеного сортування чиго) на вхід керування циклічністю роботи селектосел мінімальна кількість циклів сортування дорівра кодів 4 виконують перший (непарний) цикл нює двом, а максимальна (n+1), де n - кількість сортування, який починають з формування відпоелементів у масиві, тобто: відних пар сусідніх елементів масиву чисел (п.2а) Nmin = 2,N man =n+1. селектором кодів 4. Ці пари чисел подають на поПри відсутності зміни рангів у першому циклі парні входи відповідних схем порівняння 21,...,23, необхідно виконати ще один парний цикл для конпричому принцип формування пар елементів у тролю. непарних і парних циклах, а також з урахуванням У запропонованому пристрої зменшення трипарної/непарної розмірності масиву чисел графічвалості сортування масиву чисел досягається за но подано на Фіг.2,3 відповідно. рахунок їх ранжування, що приводить в процесі За результатом попарного порівняння на випопарного перегляду елементів масиву до зміни ходах ознаки схем порівняння 21;..., 23 одиниця значень рангів на одиницю замість переміщення формується у тих випадках, коли не виконується (транспозиції) елементів у парах, яке виконують як умова (п.3а), а виконується умова (п.3б). Ці одинимінімум за три такти. В якості значень рангів елечні сигнали, проходячи через комутатор 5, форментів може використовуватися не тільки послідомують одиничні сигнали на входах інкременвність чисел від 1 до n, де n - кількість елементів у ту/декременту відповідних лічильників 31, ...,36, масиві чисел, але й послідовність адреси цих елетобто збільшують/зменшують на одиницю їхній ментів при їхньому записі у пам'ять. стан. Ці значення рангів з виходів лічильників 31, ...,36 фіксують на входах керування селектора ко 7 34516 8 9 34516 10 11 34516 12 13 Комп’ютерна в ерстка М. Мацело 34516 Підписне 14 Тираж 28 прим. Міністерство осв іт и і науки України Держав ний департамент інтелектуальної в ласності, вул. Урицького, 45, м. Київ , МСП, 03680, Україна ДП “Український інститут промислов ої в ласності”, вул. Глазунова, 1, м. Київ – 42, 01601