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

Пристрій для сортування чисел, який містить групи елементів порівняння, який відрізняється тим, що містить групу m елементів пам'яті, де m кількість елементів у масиві чисел, гр упу m входів пристрою і (N-1) груп m виходів пристрою, причому кількість груп К елементів порівняння дорівнює N, де К=[m/2] - ціла частина числа m/2, N - кількість етапів сортування, (N-1) елементів АБО-HI, крім того, інформаційний вхід і-го елемента пам'яті з'єднаний з і-м входом пристрою, де i=1,..,m, a інформаційні виходи 2k-го і (2k+1)-го елементів пам'яті з'єднані відповідно з (2k-1)-м і 2k-м входами k-го елемента порівняння першої групи елементів порівняння, крім першого і останнього елементів пам'яті, виходи яких з'єднані з входами К-го елемента порівняння, де k=1,...,К, у k-му елементі порівняння у парній 2р-ій групі елементів порівняння, де p=1,..., [N/2], (2k-1)-й і 2k-й входи з'єднані відповідно з (2k-2)-м і (2k-1)-м виходами попередньої непарної (2р-1)-ої групи елементів порівняння, крім U 2 34857 1 3 34857 аналізу містить елемент АБО, схему порівняння, другий елемент І та елемент І першої групи, керуючі входи перших гр уп елементів І непарних блоків аналізу, перші входи други х елементів І непарних блоків аналізу і керуючі входи други х гр уп елементів І парних блоків аналізу з'єднані з інверсним виходом тригера комутації, керуючі входи др угої групи елементів І непарних блоків аналізу, керуючі входи перших гр уп елементів І парних блоків аналізу і перші входи други х елементів І парних блоків аналізу з'єднані з прямим виходом тригера комутації, в кожному блоці аналізу вихід першого елемента І підключений до синхровходу регістра, а до інформаційних входів регістра підключені виходи елементів І першої і другої гр уп, ви хід елемента АБО блока аналізу з'єднаний з другим входом першого елемента І блока аналізу, в і-му блоці аналізу, де і=1,2,...,(n-1), ви хід другого елемента І і-го блока аналізу з'єднаний з другим входом елемента АБО і-го блока, з першим входом елемента АБО (і+1)-го блока аналізу, вихід другого елемента І n-го блока аналізу підключений до другого входу елемента АБО n-го блока аналізу і до першого входу елемента АБО першого блока аналізу, ви хід регістра j-гo блока аналізу, де j=2,3,...,(n-1), з'єднаний з другим входом схеми порівняння (j-1)-гo блока аналізу, др угим входом елемента І першої групи (j-1) гo блока, з першим входом схеми порівняння j-гo блока аналізу, з першим входом елемента І другої гр упи (j+1)-гo блока аналізу, ви хід регістра n-го блока аналізу з'єднаний з другим входом схеми порівняння (n-1)-го блока аналізу, з другим входом елемента І першої групи (n-1)-го блока аналізу, з першим входом схеми порівняння n-го блока і з першим входом елемента І другої групи елементів першого блока аналізу, вихід регістра першого блока аналізу з'єднаний з першим входом схеми порівняння першого блока аналізу, з першим входом елемента І другої гр упи другого блока аналізу, з другим входом схеми порівняння n-го блока аналізу і другим входом елемента І першої групи n-го блока, вихід схем порівняння всіх блоків аналізу підключений до других входів другого елемента І відповідного блока аналізу і до входів елемента АБО-HI, вихід якого підключений до першого входу др угого елемента І, вихід якого з'єднаний з входом встановлення в нульовий стан тригера керування, вхід встановлення в одиничний стан якого підключений до входу запуску пристрою, прямий вихід підключений до першого входу першого елемента І, а інверсний вихід тригера керування є виходом готовності пристрою, до другого входу першого елемента І пристрою підключений генератор імпульсів, вихід першого елемента І підключений до перших входів перших елементів І всіх блоків аналізу, до другого входу другого елемента І та через елемент затримки підключений до тригера комутації, інформаційні виходи блоків аналізу є виходами відповідних відсортованих чисел пристрою. Недоліком даного пристрою для сортування є недостатня швидкодія через те, що у пристрої відбувається перезапис чисел у парах за необхідністю, що збільшує час циклів попарного аналізу масиву чисел. 4 Найбільш близьким за технічною суттю є пристрій для визначення екстремальних чисел [А.с. СРСР №1277090, кл. G06F7/04, 1986р., Бюл. №46], який містить (n-1) груп елементів порівняння по і елементів у кожній групі, де i=1,2,...,(n-1), n кількість чисел, які аналізують, n лічильниківдешифраторів і n груп по n блоків по m елементів І в кожному, l-і входи, де l=1,2,...,m, m - розрядність чисел, що порівнюють, першої групи входів елементів порівняння і-ої групи об'єднані та підключені до входу l-го розряду і-го числа пристрою, l-і входи др угої гр упи j-x елементів порівняння і-ої групи, де j=1,2,...,(i-1), об'єднані та підключені до входу l-го розряду j-гo числа пристрою, причому вихід „Більше" k-го елемента порівняння і-ої групи, де k=1,2,...,і, з'єднаний з і-м входом k-го лічильника-дешифратора, вихід „Менше" k-го елемента порівняння і-ої групи з'єднаний з k-м входом (k+1)го лічильника-дешифратора, р-й вихід q-гo лічильника-дешифратора, де p=1,2,...,n, q=1,2,...,n, з'єднаний з першими входами елементів І q-гo блока р-ої групи, вхід l-го розряду р-го числа пристрою з'єднаний з другими входами елементів І всіх блоків р-ої групи, ви ходи l-х елементів І всі х блоків р-ої групи об'єднані і є виходом І-го розряду р-го відсортованого числа пристрою. Недоліком даного пристрою є значний час оброблення через те, що у пристрої виконується попарне порівняння чисел кожного з кожним. В основу корисної моделі поставлено задачу створення пристрою для сортування чисел, в якому за рахунок введення додаткового максимального елемента при непарній розмірності масиву чисел, нових зв'язків між крайніми елементами масиву, а також зменшення кількості контрольних етапів на один етап досягається можливість зменшення часу сортування. Поставлена задача вирішується тим, що у пристрій для сортування чисел, який містить групи елементів порівняння, введено групу m елементів пам'яті, де m - кількість елементів у масиві чисел, груп у m входів пристрою і (N-1) груп m виходів пристрою, причому кількість груп К елементів порівняння дорівнює N, де К=]m/2[ - ціла частина числа m/2, N - кількість етапів сортування, (N-1) елементів АБО-HI, крім того, інформаційний вхід і-го елемента пам'яті з'єднаний з і-м входом пристрою, де i=1,...,m, a інформаційні виходи 2k-го і (2k+1)-го елементів пам'яті з'єднані відповідно з (2k-1)-м і 2k-м входами k-го елемента порівняння першої групи елементів порівняння, крім першого і останнього елементів пам'яті, виходи яких з'єднані з входами К-го елемента порівняння, де k=1,...,К, у k-му елементі порівняння у парній 2р-й групі елементів порівняння, де p=1,...,]N/2[, (2k-1)-й і 2k-й входи з'єднані відповідно з (2k-2)-м і (2k-1)-м виходами попередньої непарної (2р-1)-ої групи елементів порівняння, крім першого входу першого елемента порівняння і другого входу останнього елемента порівняння, які з'єднані відповідно з першим і другим виходами останнього елемента порівняння з попередньої непарної (2р-1)-ої групи елементів порівняння, у k-му елементі порівняння у непарній (2р+1)-й групі елементів порівняння (2k1)-й і 2k-й входи з'єднані відповідно з 2k-м і (2k+1) 5 34857 м виходами попередньої парної 2р-ої групи елементів порівняння, крім першого і другого входів останнього елемента порівняння, які з'єднані відповідно з першим виходом першого елемента порівняння і другим виходом останнього елемента порівняння попередньої парної 2р-ої групи елементів порівняння, (m-2) виходів непарних (2р+1)-х груп елементів порівняння з'єднані відповідно з непарними (2р+1)-ми групами (m-2) виходів пристрою, починаючи з другого виходу пристрою, причому перший і другий виходи останнього елемента порівняння у непарних (2р+1)-х групах елементів порівняння з'єднані відповідно з першим і m-м виходами непарних (2р+1)-х груп ви ходів пристрою, m виходів парних 2р-х гр уп елементів порівняння з'єднані відповідно з парними 2р-ми групами m виходів пристрою, К виходів ознаки j-ої групи елементів порівняння, j=2,...,N, крім першої групи елементів порівняння, з'єднані з К входами j-гo елемента АБО-HI, ви хід якого є j-м виходом ознаки закінчення сортування у пристрої, а останній m-й елемент пам'яті має вихід ознаки нуля. На Фіг.1 показано структурн у схему пристрою для сортування чисел; на Фіг.2, 3 представлено відповідно топологію з'єднань елементів масиву чисел типу „кільце" для парної і непарної розмірності масиву чисел. Пристрій для сортування чисел (Фіг. 1) містить груп у елементів 11,K,1m (де m - кількість елементів у масиві чисел), N груп елементів порівняння j j 21,K 2K (де j=1,...,N, K=]m/2[ - ціла частина числа m/2), групу входів 31, K,3m і (N-1) груп ви ходів j j 41, K,4m , починаючи з j=2. Крім того, інформаційний вхід елемента пам'яті 1i з'єднаний зі входом 3i пристрою (де i=1,...,m), a інформаційні виходи елементів пам'яті 12k і 12k+1 з'єднані з входами 51 k -1 і 51 k елементів порівняння 21 , де k=1,...,К, 2 2 k крім виходів першого і останнього елементів пам'яті 11 і 1m , ви ходи яких з'єднані з входами 51 -1 і m 51 елемента порівняння 21 . У кожній парній 2р-й m K групі елементів порівняння 2 21 p , K,22p , K де р=1,...,]N/2[, входи 52p -1 і 52p елемента порівнян2k 2k ня 22p k з'єднані відповідно з виходами 62p -1 2k -2 і 62p - 1, попередньої непарної (2р-1)-ої групи еле2k - 1 2 2 2 ментів порівняння 21 p -1, K,2Kp-1 , крім входу 51 p 2 елемента порівняння 21 p і входу 52p елемента m порівняння 22p , які з'єднані відповідно з виходами K 62p--1 і 62p -1 попередньої непарної (2р-1)-ої групи m m 1 2 2 елементів порівняння 21 p -1, K,2Kp-1 . У кожній непарній (2р+1)-й групі елементів порівняння 2 2 1 21 p +1, K,2Kp+1 входи 52p +1 і 52p +1 елемента порів2k 2k 6 няння 22p +1 з'єднані відповідно з виходами 62p і k 2k 62p +1 , попередньої парної 2р-ої групи елементів 2k 2 порівняння 21 p , K,22p , крім входів 52p-+1 і 52p +1 m K m 1 елемента порівняння 22p +1 , які з'єднані відповідно K з виходами 62p і 62p попередньої парної 2р-ої m 1 2 групи елементів порівняння 21 p , K,22p . K 2 Виходи 61 p +1, K ,62p-+1 непарних (2р+1)-х гр уп m 2 2 2 елементів порівняння 21 p +1, K,2Kp+1 з'єднані від повідно з виходами 42 p+1, K,42p-+1 2 m 1 непарних (2р+1)-х груп виходів пристрою, крім виходів 62p-+1 m 1 і 62p +1 , які з'єднані відповідно з виходами 42p +1 і m 1 42p +1 непарних (2р+1)-х груп виходів пристрою. m Виходи 62p , K ,62p парних 2р-х груп елементів поm 1 2 рівняння 21 p , K,22p з'єднані відповідно з виходами K 42p , K ,42 p парних 2р-х гр уп ви ходів пристрою. m 1 j j Виходи 71, K,7K ознаки всіх гр уп елементів порівj j няння 21, K,2K , крім першої групи елементів порі вняння 21, K,21 , з'єднані з входами відповідних 1 K елементів АБО-HI 8 j , починаючи з j=2, вихід 9 j яких є відповідним j-м виходом ознаки закінчення сортування у пристрої, j=2,...,N, а елемент пам'яті 1m має вихід 10 ознаки нуля. Сортування масиву чисел у пристрої (Фіг.1) відбувається таким чином. Числа початкового масиву записують по входа х 31, K,3m пристрою в елементи пам'яті 11, K ,1m відповідно. Якщо кількість елементів масиву чисел є непарною (m-1), тобто при наявності одиничного сигналу на виході 10 ознаки нуля старшого елемента пам'яті 1m , то в нього записують максимальне за значенням число. На першому непарному етапі сортування пари сусідніх елементів складають елементи масиву чисел 2k-х і (2k+1)-х позицій, де k=1,...,К, які подають відповідно на перший і другий входи 51 k -1 і 2 51 k елемента порівняння 21 першої групи еле2 k ментів порівняння 21, K,21 , крім елемента порів1 K няння 21 , на перший і другий входи якого подаK ють перший і m-й елементи масиву чисел, тобто формують додаткову пару крайніх елементів масиву. На другому і всі х наступних парних етапах сортування пари сусідніх елементів складають елементи масиву чисел (2k-1)-х і 2k-х позицій, де k=1,...,К, які з виходів 62p -1 і 62p -1 попередньої 2k -2 2k -1 непарної (2р-1)-ої групи елементів порівняння 7 34857 8 2 2 21 p -1, K,2Kp-1 подають відповідно на перший і дру j елемента порівняння 2k з'явиться менше число, а гий входи 52p -1 і 52p елемента порівняння 22p 2k 2k k парної 2р-ої групи елементів порівняння j на виході 62k - більше число з двох чисел, що порівнюють. Якщо за результатом порівняння в 2 2 21 p , K,22p , крім елемента порівняння 21 p , на пеK j елементі порівняння 2k j-ої групи елементів порі 2 рший вхід 51 p якого з виходу 62p--1 попередньої m 1 непарної (2р-1)-ої групи елементів порівняння j j вняння 21, K,2K , де j=2,...,N, k=1,...,K, відбуде ться переміщення (транспозиція) чисел з першого вхо 2 2 21 p -1, K,2Kp-1 подають елемент масиву чисел першої позиції, а також крім елемента порівняння j j j ду 52k -1 на другий вихід 62k і з другого входу 52k 22p K 52p m 62p -1 m , на другий вхід якого з виходу попередньої непарної (2р-1)-ої групи елементів порі2 2 вняння 21 p -1, K,2Kp-1 подають елемент масиву чисел m-ої позиції. На третьому і всі х наступних непарних етапах сортування пари сусідніх елементів складають елементи масиву чисел 2k-х і (2k+1)-х позицій, які з виходів 62p і 62p +1 попередньої парної 2р-ої 2k 2k 2 групи елементів порівняння 21 p , K,22p , де K p=1,...,]N/2[, подають відповідно на перший і дру гий входи 1 52p +1 і 52p +1 елемента порівняння 2k 2k 22p +1 непарної (2р+1)-ої групи елементів порівk 2 2 няння 21 p +1, K,2Kp+1 , крім елемента порівняння 22p +1 , на перший і другий входи 52p-+1 і 52p +1 якоm K m 1 го подають з виходів 62p і 62p попередньої парm 1 2 ної 2р-ої групи елементів порівняння 21 p , K,22p K відповідно елементи масиву чисел першої і m-ої позицій. Таким чином у пристрої на непарних етапах реалізується спосіб сортування з топологією з'єднань елементів масиву типу „кільце" для парної розмірності (Фіг.2) і непарної розмірності (Фіг.3) масиву чисел. За результатом попарного порівняння в N груj j j пах елементів порівняння 21, K,2K на виході 62k -1 j j на перший вихід 62k -1 , то на його виході 7k ознаки з'явиться одиничний сигнал, що призведе до появи нульового сигналу на виході 9 j елемента АБО-HI 8 j , який свідчить про продовження процесу сортування. При появі на виході 9 j елемента АБО-HI 8 j , а отже, на j-му виході ознаки закінчення сортування пристрою одиничного сигналу процес сортування припиняється і з відповідних ви хоj j дів 41, K,4m j-ої групи виходів пристрою зчитується відсортований масив чисел, j=2,...,N. У табл.1 наведено приклади сортування масиву чисел (за зростанням їх значень) з урахуванням розмірності m масиву відповідно за класичним способом (лінійним) та запропонованим способом (кільцевим). Тут застосовано такі умовні позначення: [ - ознака пари елементів масиву чисел, що порівнюються; ] - ознака додаткової пари крайніх елементів масиву чисел, що порівнюють; (9) - введений максимальний додатковий елемент масиву чисел. Елементи масиву взято з діапазону цілих додатних чисел (0,K ,9) . У табл.1 розглянуто сортування масиву чисел, розмірність якого або парна (шість чисел) або непарна (п'ять чисел). Для наочності у табл.1 наведено приклади особливого випадку сортування, а саме, коли елементи початкового масиву чисел розташовані у зворотному порядку (за спаданням значень чисел). 9 34857 10 Tаблиця 1 Спосіб сортування 1 é6 ê5 ë Класичний спосіб: парна розмірність масиву é4 ê ë3 é2 ê1 ë Класичний спосіб: непарна розмірність масиву é5 ê ë4 é3 ê ë2 1 Запропонований спосіб: парна розмірність масиву Запропонований спосіб: непарна розмірність масиву 2 5 é6 ê ë3 é4 ê ë1 2 4 é5 ê ë2 é3 ê1 ë 6 ù ú é5 ú ê4ú ë ú é3 ú ê2ú ë ú 1 ú û é1 ê4 ë 5 ù ú é4 ú ê3 ú ë ú é2 ú ê1 ú ë ú (9)ú û é5 ê3 ë é5 ê ë2 é3 ê6 ë é4 ê ë1 é2 ê(9) ë 3 é5 ê3 ë é6 ê ë1 é4 ê2 ë é4 ê ë2 é5 ê ë1 3 1 ù ú é4ú ê2ú ë ú é5 ú ê3 ú ë ú 6 ú û 3 ù ú é5 ú ê1 ú ë ú é4 ú ê2 ú ë ú (9)ú û Для класичного способу сортування методом попарного обміну характерним є застосування двох контрольних етапів (парного та непарного) для визначення моменту закінчення процесу сортування (табл.1) за відсутності переміщень елементів масиву у парах на цих етапах. Доведемо можливість застосування одного контрольного етапу. Нехай n-й етап був останній, в якому виконувались переміщення елементів масиву у парах. Але, якщо на (n+1)-му етапі не відбувається жодного переміщення елементів масиву у парах , то можна стверджувати, що на (n+2)-му етапі також не буде переміщень, оскільки будуть порівнювати елементи масиву у парах, які вже впорядковані на n-му етапі. Ці міркування стосуються всіх етапів, окрім першого. При відсутності переміщень елементів масиву на першому етапі необхідно виконати наступний етап для контролю. Отже, мінімальна і максимальна кількість етапів N сортування для запропонованого способу сортування дорівнює таким величинам: Етапи сортування 4 5 3 é3 ê1 é5 ë ê 1 ë é5 ê é6 ë2 ê 2 ë é6 ê4 4 ë 2 é2 ê é4 ë1 ê 1 ë é4 ê é5 ë3 ê3 5 ë é1 ê2 ë é4 ê ë3 é5 ê6 ë é3 ê1 ë é5 ê ë2 é4 ê(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 ù ú é3 ú ê2 ú ë ú é5 ú ê4 ú ë ú (9)ú û é1 ê2 ë é3 ê ë4 é5 ê(9) ë Nmin = 2, Nmax = m + 1 . (1) Приклади у табл.1 підтверджують часові залежності (1). Для класичного способу сортування методом попарного обміну максимальна кількість етапів дорівнює Nmax = m + 2 . Отже, саме виконання сортування із „замиканням" масиву чисел у „кільце", а також можливість виконання тільки одного контрольного етапу дозволяють покращити часові характеристики процесу сортування. Запропонований пристрій дозволяє зменшити тривалість процесу сортування масиву чисел за рахунок введення додаткового максимального елемента при непарній розмірності вхідного масиву чисел і формування додаткової пари елементів, яку утворюють перший та старший (або введений максимальний) елементи масиву на всі х непарних етапах сортування, а також за рахунок зменшення кількості контрольних етапів на один етап. Це дозволяє підвищити швидкодію сортування чисел за рахунок зменшення кількості етапів як мінімум на один етап. 11 34857 12 13 Комп’ютерна в ерстка Л.Литв иненко 34857 Підписне 14 Тираж 28 прим. Міністерство осв іт и і науки України Держав ний департамент інтелектуальної в ласності, вул. Урицького, 45, м. Київ , МСП, 03680, Україна ДП “Український інститут промислов ої в ласності”, вул. Глазунова, 1, м. Київ – 42, 01601