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

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