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

Пристрій для сортування чисел, який містить групи елементів порівняння, який відрізняється тим, що він містить групу m елементів пам’яті, де m - кількість елементів у масиві чисел, груп у m входів пристрою і (N-1) груп m виходів пристрою, причому кількість груп К елементів порівняння дорівнює N, де К=]m/2[ - ціла частина числа m/2, N кількість етапів сортування, (N-1) елементів АБОНІ, крім того, інформаційний вхід і-го елемента пам’яті з’єднаний з і-им входом пристрою, де і = 1, ... , m, а (2k-1)-ий і 2k-ий інформаційні виходи відповідних (2k-1)-го і 2k-го елементів пам’яті з’єднані відповідно з першим і другим входами k-го елемента порівняння першої групи елементів порівняння, де k = 1, 2, ..., К, у k-му елементі порівняння у непарній (2р+1)-ій групі елементів порівняння, де p = l, 2, ..., ]N/2[, крім першої групи елементів порівняння, (2k-1)-й і 2k-й входи з’єднані відповідно з (2k-2)-им і (2k-1)-им виходами попередньої парної 2р-ої групи елементів порівняння, крім першого U 2 25483 1 3 25483 входи др угої групи елементів І непарних блоків аналізу, керуючі входи перших гр уп елементів І парних блоків аналізу і перші входи други х елементів І парних блоків аналізу з’єднані з прямим виходом тригера комутації, в кожному блоці аналізу вихід першого елемента І підключений до синхровходу регістра, а до інформаційних входів регістра підключені виходи елементів І першої і другої гр уп, вихід елемента АБО блока аналізу з’єднаний з другим входом першого елемента І блока аналізу, в і-му блоці аналізу, де і=1,2,...,n-1, ви хід другого елемента І і-го блока аналізу з’єднаний з другим входом елемента АБО і-го блока, з першим входом елемента АБО (і+1)-го блока аналізу, ви хід другого елемента І n-го блока аналізу підключений до другого входу елемента АБО n-го блока аналізу і до першого входу елемента АБО першого блока аналізу, ви хід регістра j-го блока аналізу, де j=2,3,...,(n-1), з’єднаний з другим входом схеми порівняння (j-1)-гo блока аналізу, др угим входом елемента І першої групи (j-1)-гo блока, з першим входом схеми порівняння j-гo блока аналізу, з першим входом елемента І другої гр упи (j+1)-гo блока аналізу, ви хід регістра n-го блока аналізу з’єднаний з другим входом схеми порівняння (n-1)го блока аналізу, з другим входом елемента І першої гр упи (n-1)-го блока аналізу, з першим входом схеми порівняння n-го блока і з першим входом елемента І другої групи елементів першого блока аналізу, вихід регістра першого блока аналізу з’єднаний з першим входом схеми порівняння першого блока аналізу, з першим входом елемента І другої групи другого блока аналізу, з другим входом схеми порівняння n-го блока аналізу і другим входом елемента І першої групи n-го блока, вихід схем порівняння всіх блоків аналізу підключений до других входів другого елемента І відповідного блока аналізу і до входів елемента АБО-НI, вихід якого підключений до першого входу другого елемента І, вихід якого з’єднаний з входом встановлення в нульовий стан тригера керування, вхід встановлення в одиничний стан якого підключений до входу запуску пристрою, прямий вихід підключений до першого входу першого елемента І, а інверсний вихід тригера керування є виходом готовності пристрою, до другого входу першого елемента І пристрою підключений генератор імпульсів, вихід першого елемента І підключений до перших входів перших елементів І всіх блоків аналізу, до другого входу др угого елемента І та через елемент затримки підключений до тригера комутації, інформаційні виходи блоків аналізу є виходами відповідних відсортованих чисел пристрою. Недоліком даного пристрою для сортування є те, що у пристрої відбувається перезапис чисел у парах за необхідністю, що збільшує час циклів попарного аналізу масиву чисел. Відомий пристрій для вибору екстремального числа з множини NM-розрядних чисел [А.с. СРСР №1348818, кл. G06F 7/02, 1987, Бюл. №40], який містить К груп схем порівняння, де K = 1, N - 1 , пo N-K схем порівняння в кожній групі, К груп елементів НІ по (N-K) елементів НІ в кожній групі, входи Кго числа пристрою з’єднані з першою групою входів схем порівняння К-ої групи, друга група входів 4 схем порівняння К-ої групи з’єднана з входами чисел з (К+1)-го по N-й пристрою відповідно, виходи нерівності схем порівняння з’єднані з входами відповідних елементів НІ гр уп, пристрій також містить К гр уп елементів АБО по N-K елементів АБО в кожній групі, N елементів І, причому вихід нерівності (N-К)-ої схеми порівняння К-ої групи з’єднаний з першим входом (N-K)-гo елемента АБО К-ої гр упи, другий вхід якого з’єднаний з виходом рівності (N-K)-oї схеми порівняння К-ої групи, а вихід з’єднаний з К-им входом і-го елемента І, де i=2,...,N, ви хід j-гo елемента І, де j=l,...,N, є j-м виходом екстремального числа пристрою, виходи елементів НІ К-их гр уп з’єднані з входами К-их елементів І відповідно. Недоліком даного пристрою є його обмежені функціональні можливості через те, що пристрій шляхом попарного пошуку визначає екстремальні числа масиву, але не сортує масив чисел. Найбільш близьким за технічною суттю є пристрій для визначення екстремальних чисел [А.с. СРСР №1277090, кл. G06F 7/04, 1986, Бюл. №46], який містить n-1 груп елементів порівняння по і елементів у кожній групі, де і=1,2,...,(n-1), n - кількість чисел, які аналізують, l-і входи, де l=1,2,...,m, m - розрядність чисел, що порівнюють, першої групи входів елементів порівняння і-ої групи об’єднані та підключені до входу l-го розряду і-го числа пристрою, l-і входи другої групи j-x елементів порівняння і-ої групи, де j=1,2,...,(i-1), об’єднані та підключені до входу l-го розряду j-гo числа пристрою, n лічильників-дешифраторів і n груп по n блоків по m елементів І в кожному, причому вихід "Більше" k-го елемента порівняння і-ої групи, де k=1,2,...,і, з’єднаний з і-им входом k-го лічильникадешифратора, вихід "Менше" k-го елемента порівняння і-ої групи з’єднаний з k-им входом (к+1)-го лічильника-дешифратора, р-ий вихід q-гo лічильника-дешифратора, де p=1,2,...,n, q=1,2,...,n, з’єднаний з першими входами елементів І q-ro блока р-ої групи, вхід l-го розряду р-го числа пристрою з’єднаний з другими входами елементів І всіх блоків р-ої групи, виходи l-их елементів І всіх блоків р-ої групи об’єднані і є виходом l-го розряду р-го відсортованого числа пристрою. Недоліком даного пристрою є фіксований максимальний час оброблення через те, що у пристрої виконується попарне порівняння чисел кожного з кожним. В основу пристрою поставлена задача створення пристрою для сортування чисел, в якому за рахунок введення додаткового максимального елемента при непарній розмірності масиву чисел, нових зв’язків між крайніми елементами масиву, а також зменшення кількості контрольних етапів на один етап досягається можливість зменшення часу сортування. Поставлена задача вирішується тим, що у пристрій для сортування чисел, який містить групи елементів порівняння, введено групу m елементів пам’яті, де m – кількість елементів у масиві чисел, груп у m входів пристрою і (N-1) груп m виходів пристрою, причому кількість груп К елементів порівняння дорівнює N, де К=]m/2[ - ціла частина числа m/2, N - кількість етапів сортування, (N-1) еле 5 25483 ментів АБО-НI, крім того, інформаційний вхід і-го елемента пам’яті з’єднаний з і-им входом пристрою, де і=1,...,m, а (2k-1)-ий і 2к-ий інформаційні виходи відповідних (2k-1)-го і 2k-го елементів пам’яті з’єднані відповідно з першим і другим входами k-го елемента порівняння першої групи елементів порівняння, де k=1,2,...,К, у k-го елемента порівняння у непарній (2р+1)-ій групі елементів порівняння, де p=1,2,...,]N/2[, крім першої групи елементів порівняння, (2k-1)-й і 2k-й входи з’єднані відповідно з (2k-2)-им і (2k-1)-им виходами попередньої парної 2р-ої групи елементів порівняння, крім першого входу першого елемента порівняння і другого входу останнього елемента порівняння, які з’єднані з першим і другим виходами останнього елемента порівняння попередньої парної 2р-ої групи елементів порівняння відповідно, у k-го елемента порівняння у парній 2р-ій групі елементів порівняння (2k-1)-й і 2k-й входи з’єднані відповідно з 2k-им і (2k+1)-им виходами попередньої непарної (2р-1)-ої групи елементів порівняння, крім першого і другого входів останнього елемента порівняння, які з’єднані з першим виходом першого елемента порівняння і другим виходом останнього елемента порівняння попередньої непарної (2р-1)-ої групи елементів порівняння відповідно, m виходів непарних (2р+1)-их груп елементів порівняння, крім першої групи елементів порівняння, з’єднані відповідно з непарними (2р+1)-ми групами m виходів пристрою, m виходів парних 2р-их груп елементів порівняння з’єднані відповідно з парними 2р-ми групами m виходів пристрою, причому перший і другий ви ходи останнього елемента порівняння у парних 2р-х гр упах елементів порівняння з’єднані відповідно з першим і m-им виходами парних 2р-х груп m виходів пристрою, K виходів ознаки j-ої групи елементів порівняння, j=2,...,N, крім першої групи елементів порівняння, з’єднані з К входами j-гo елемента АБО-НІ, вихід якого є j-им виходом ознаки закінчення сортування у пристрої, а останній mий елемент пам’яті має вихід ознаки нуля. На Фіг.1 показано структурн у схему пристрою для сортування чисел, на Фіг.2, 3 представлено відповідно топологію з’єднань елементів типу „кільце" для парної і непарної розмірності масиву чисел. Пристрій для сортування чисел (Фіг.1) містить груп у елементів пам’яті 11, ..., 1m, де m - кількість елементів у масиві чисел, N груп К елементів поріj вняння 2Ij ,..., 2K , де j=1, ..., N, K=]m/2[, груп у вхоj дів 3і, ..., 3 m пристрою і (N-1) груп виходів 4l , ..., j 4m пристрою, починаючи з j=2. Крім того, інформаційний вхід елемента пам’яті li з’єднаний зі входом 3i пристрою, де і=1,2, ..., m, а інформаційні виходи елементів пам’яті 12k-1 і 12k з’єднані з вхо дами 51 k -1 і 51 k елемента порівняння 21 , де 2 2 k k=1,2, ..., К. У кожній непарній (2р+1)-ій групі еле2p +1 2 ментів порівняння 21 p +1 , ..., 2K , де p=1, ..., ]N/2[, крім першої групи елементів порівняння 21 , 1 1 ..., 21 , входи 52p +1 , і 52p +1 елемента порівняння K 2k 2k 6 22p +1 з’єднані відповідно з виходами 62p -2 k 2k 62p -1 , 2k і попередньої парної 2р-ої групи елементів 2 2 порівняння 21 p , ..., 22p , крім входа 51 p +1 , елемеK 52p +1 m 2 нта порівняння 21 p +1 , і входа елемента по рівняння 22p +1 , які з’єднані відповідно з виходами K 62p 1 , і 62p попередньої парної 2р-ої групи елемеm m2 нтів порівняння 21 p , ..., 22p . У кожній парній 2р-ій K 2 групі елементів порівняння 21 p , ..., 22p входи K 52p-1 , і 52p елемента порівняння 2k 2k відповідно з виходами 62p -1 2k 22p k з’єднані і 62p -1 , попередньої 2k +1 непарної (2р-1)-ої групи елементів порівняння 2 2 2 21 p-1 , ..., 2Kp-1 входів 5mp 1 , і 52p елемента порівm няння 22p , які з’єднані відповідно з виходами k 2 61 p -1 і 62p -1 m попередньої непарної (2р-1)-ої групи 2 2 елементів порівняння 21 p-1 , ..., 2Kp-1 . Виходи 62p +1 і 62p +1 непарних (2р+1)-их груп 1 m 2 2 елементів порівняння 21 p-1 , ..., 2Kp-1 , крім першої групи елементів порівняння 21 , ..., 21 , з’єднані 1 K відповідно з виходами 2 41 p+ 1 і 42p +1 непарних m (2р+1)-их груп виходів пристрою. Виходи 62p і 1 62 p-2 m 2 парних 2р-их груп схем порівняння 21 p , ..., 22p з’єднані відповідно з виходами 42p , ..., 42p-1 K 2 m парних 2р-их гр уп виходів пристрою, крім виходів 2 62p 1 і 62p , які з’єднані відповідно з виходами 41 p m m 2 і 4mp парних 2р-их гр уп виходів пристрою. Виходи j 7lj , ..., 7K ознаки всіх гр уп елементів порівняння j 2lj , ..., 2K , крім першої групи елементів порівнян ня 21 , ..., 21 , з’єднані з входами відповідних еле1 K ментів АБО-НІ 8j, починаючи з j=2, вихід 9j, яких є відповідним j-им виходом ознаки закінчення сортування у пристрої, j=2, ..., N, а елемент пам’яті lm має вихід 10 ознаки нуля. Сортування масиву чисел у пристрої (Фіг.1) відбувається таким чином. Числа початкового масиву записують по входах 31, ..., 3m пристрою в елементи пам’яті l1, ..., l m. Якщо кількість елементів масиву чисел є непарною (m-1), тобто при наявності одиничного сигналу на виході 10 ознаки нуля старшого елемента пам’яті lm, то в нього записують максимальне за значенням число. На першому непарному етапі сортування пари сусідніх елементів складають елементи масиву чисел (2к-1)-их 7 25483 і 2к-их позицій, де k=1, ..., К, які подають відповідно на перший і другий входи 51 k-1 , 2 і 51 k 2 елемента порівняння 21 першої групи елементів порівняння k 21 , ..., 21 . 1 K На другому і всі х наступних парних етапах сортування пари сусідніх елементів складають елементи масиву чисел 2k-их і (2k+1)-их позицій, які з виходів 62p -1 і 62p -1 попередньої непарної (2р-1)2k 2k +1 2 ої групи елементів порівняння 21 p-1 , ..., 22p -1 , де K p=1, ..., ]N/2[, подають відповідно на перший і другий входи 52p-1 , і 52p елемента порівняння 22p 2k 2k k 2 парної 2р-ої групи елементів порівняння 21 p , ..., 22p K , крім елемента порівняння 2 другий входи 5mp 1 , і 2 61 p -1 і 2 6mp -1 2 5mp 22p K , на перший і якого подають з виходів попередньої непарної (2р-1)-ої групи 2 елементів порівняння 21 p-1 , ..., 22p -1 відповідно K елементи масиву чисел першої і m-ої позицій. На третьому і всі х наступних непарних етапах сортування пари сусідніх елементів складають елементи масиву чисел (2k-1)-их і 2k-их позицій, які з виходів 62p -2 і 62p -1 , попередньої парної 2р2k 2k 2 ої групи елементів порівняння 21 p , ..., 22p подаK 1 ють відповідно на перший і другий входи 52p +1 , і 2k 52p +1 елемента порівняння 22p +1 непарної (2р+1)2k k 2p + 1 2 оі групи елементів порівняння 21 p +1 , .., 2k , крім 2 2 елемента порівняння 21 p +1 , на перший вхід 51 p +1 якого з виходу 62p 1 попередньої парної 2р-ої груm2 пи елементів порівняння 21 p , ..., 22p подають K елемент масиву чисел першої позиції, а також крім елемента порівняння 22p +1 , на другий вхід 52p +1 m K якого з виходу 62p попередньої парної 2р-ої групи m 2 елементів 21 p , ..., 22p подають елемент масиву K чисел m-ої позиції. Таким чином у пристрої реалізується спосіб сортування з топологією з’єднань елементів типу «кільце» для парної розмірності (Фіг. 2) і непарної розмірності (Фіг. 3) масиву чисел. За результатом попарного порівняння в N груj пах елементів порівняння 2lj , ..., 2K , на їх виході 6 j2k- 1 j з’явиться менше число, а на виході 6 2k 8 більше число з двох чисел, що порівнюють. Якщо за результатом порівняння в елементі порівняння j j 2k j-ої групи елементів порівняння 2lj , ..., 2K , де j=2, ..., N, k = 1, ..., K, відбудеться переміщення j (транспозиція) чисел з першого входу 52k-1 , на j j другий ви хід 62k і з другого входу 52k на перший j j вихід 62k -1 , то на його виході 7k ознаки з’явиться одиничний сигнал, що призведе до появи нульового сигналу на ви ході 9j елемента АБО-НІ 8j, який свідчить про продовження процесу сортування. При появі на виході 9j елемента АБО-НІ 8j, а отже, на j-му виході ознаки закінчення сортування пристрою одиничного сигналу процес сортування j j припиняється і з відповідних ви ходів 41 , …, 4m jої групи ви ходів пристрою зчитується відсортований масив чисел. У табл. наведено приклади сортування масиву чисел (за зростанням їх значень) з урахуванням розмірності m масиву відповідно за класичним способом (лінійним) та запропонованим способом (кільцевим). Тут застосовано такі умовні позначення: [ - ознака пари елементів масиву чисел, що порівнюють; ] - ознака додаткової пари крайніх елементів масиву чисел, що порівнюють; (...) введений максимальний додатковий елемент масиву чисел. Елементи масиву взято із діапазону цілих додатних чисел (0,...,9). Розглянемо сортування масиву чисел, розмірність якого або парна (шість чисел) або непарна (п’ять чисел) (табл.). Для наочності у табл. наведено приклади особливого випадку сортування, а саме, коли елементи початкового масиву чисел розташовані у зворотному порядку (за спаданням значень чисел). Для класичного способу сортування методом попарного обміну характерним є застосування двох контрольних етапів (парного та непарного) для визначення моменту закінчення процесу сортування (табл.1) за відсутністю переміщень елементів масиву у парах на цих етапах. Доведемо можливість застосування одного контрольного етапу. Нехай n-й етап був останній, в якому виконувались переміщення елементів масиву у парах. Але, якщо на (n+1)-му етапі не відбувається жодного переміщення елементів масиву у парах, то можна стверджувати, що на (n+2)-му етапі також не буде переміщень, оскільки будуть порівнювати елементи масиву у парах, які вже впорядковані на n-му етапі. Ці міркування стосуються всіх етапів, окрім першого. При відсутності переміщень елементів масиву на першому етапі необхідно виконати наступний етап для контролю. 9 25483 10 Таблиця Спосіб сортування 1 é6 ê5 ë Класичний спосіб: парна розмірність масиву é4 ê ë3 é2 ê1 ë Класичний спосіб: непарна розмірність масиву é5 ê ë4 é3 ê ë2 1 Запропонований спосіб: парна розмірність масиву é6 ê5 ë é4 ê ë3 é2 ê1 ë Запропонований спосіб: непарна розмірність масиву é5 ê4 ë é3 ê ë2 é1 ê(9) ë 2 5 é6 ê ë3 é4 ê ë1 2 4 é5 ê ë2 é3 ê ë1 3 é5 ê3 ë é6 ê ë1 é4 ê2 ë é4 ê ë2 é5 ê ë1 3 5ù ú é6ú ê3 ú ë ú é4ú ê1 ú ë ú 2ú û é2 ê3 ë 4 ù ú é5 ú ê2 ú ë ú é3 ú ê1 ú ë ú (9 )ú û é4 ê2 ë é5 ê ë1 é6 ê ë1 é4 ê5 ë é3 ê(9) ë Отже, мінімальна і максимальна кількість етапів N сортування для запропонованого способу сортування дорівнює таким величинам: Nmin=2, N max=m+1. (1) Приклади у табл. підтверджують часові залежності (1). Для класичного способу сортування методом попарного обміну максимальна кількість етапів дорівнює Nmax=m+2. Отже, саме проведення сортування із «замиканням» масиву чисел у «кільце», а також можливість виконання тільки одного контрольного етапу дозволяють покращити часові характеристики процесу сортування. Етапи сортування 4 5 3 é3 ê1 é5 ë ê é5 ë1 ê é6 ë2 ê ë2 é6 ê4 4 ë 2 é2 ê é4 ë1 ê 1 ë é4 ê é5 ë3 ê 3 5 ë 2ù ú é3 ú ê1 ú ë ú é6ú ê4ú ë ú 5ú û 2 ù ú é4 ú ê1 ú ë ú é5 ú ê3 ú ë ú (9 )ú û é2 ê1 ë é3 ê ë4 é6 ê5 ë é2 ê1 ë é4 ê ë3 é5 ê(9) ë 6 1 é3 ê ë2 é5 ê ë4 6 1 é2 ê ë3 é4 ê ë5 7 é1 ê2 ë é3 ê ë4 é5 ê6 ë 8 1 é2 ê ë3 é4 ê ë5 6 é1 ê ë2 é3 ê ë4 5 1ù ú é2ú ê3 ú ë ú é4ú ê5 ú ë ú 6ú û 1 ù ú é2 ú ê3 ú ë ú é4 ú ê5 ú ë ú (9 )ú û Запропонований пристрій дозволяє зменшити тривалість процесу сортування масиву чисел за рахунок введення додаткового максимального елемента при непарній розмірності вхідного масиву чисел і формування додаткової пари елементів, яку утворюють перший та старший (або введений максимальний) елементи масиву на всіх парних етапах сортування, а також за рахунок зменшення кількості контрольних етапів на один етап. Це дозволяє підвищити швидкодію сортування чисел за рахунок зменшення кількості етапів як мінімум на один етап. 11 25483 12 13 Комп’ютерна в ерстка А. Крулевський 25483 Підписне 14 Тираж 26 прим. Міністерство осв іт и і науки України Держав ний департамент інтелектуальної в ласності, вул. Урицького, 45, м. Київ , МСП, 03680, Україна ДП “Український інститут промислов ої в ласності”, вул. Глазунова, 1, м. Київ – 42, 01601