Спосіб сортування чисел

Винахід відноситься до автоматики та обчислювальної техніки і може бути використаний при обробці статистичної інформації. Відомий спосіб сортування [Григорьев В. Р., На умов С. П. Нейросетевая реализация алгоритма сортировки на трехмерном оптическом нейрочипе, "Автометрия", 1993, №3, C.28-37], що базується на використанні одинично-позиційного коду, в якому результатом ряду перетворень є представления елементів вхідного невідсортованого масиву в единично позиційному коді, далі відбувається порозрядове(починаючи з першого розраду) зчитування елементів масиву, причому елемент, зчитаний розряд якого є одиницею, виводиться у вихідн у послідовність, починаючи з найменшого елемента. Недоліком тякого способу сортування є те, що для представлення елементів масиву в одиничнопозиційному коді виконується ряд нераціональних перетворень, що збільшує час сортування. Найбільш близьким за технічною суттю є спосіб сортування чисел за методом попарного обміну [Лорин Г. Сортировка и системы сортировки. М.: Мир, 1983, C.24-27], який базується на послідовності попарних переглядів, в яких елемент порівнюється зі своїм найближчим сусідом, а можливими переміщеннями є переміщення більшого за значенням елемента на одну позицію вниз і переміщення меншого за значенням на одну позицію вгору, причому при непарних переглядах кожен елемент непарної (2k-1)-ї позиції порівнюється зі своїм сусідом парної 2k-ї позиції і більший з них займає парну 2к-ту позицію, причому k=1,2,...,]m/2[, де ]а[ - ціла частина числа а, m - кількість елементів масиву, при парних переглядах кожен елемент парної 2к-ї позиції порівнюється із сусіднім елементом непарної (2k+1)-ї позиції і більший з них займає непарну (2k+1)-y позицію. Сортування закінчується тоді, коли під час двох послідовних переглядів не відбудеться обміну елементів ні в одній парі. Недоліком даного способу є значний час сортування, мінімальне значення якого дорівнює двом переглядам, а максимальне значення дорівнює (m+1) перегляду. В основу винаходу поставлена задача створення способу сортування чисел, в якому за рахунок введення додаткового нульового елементу масиву чисел та нових зв'язків між крайніми елементами масиву досягається можливість зменшення часу сортування. Поставлена задача вирішується тим, що в способі, який базується на послідовності циклів, в яких, виконуються паралельно попарю перегляди в К парах елементів(К = ] m/2 [, де m - кількість елементів масиву чисел), причому у непарних циклах в k-ій парі елемент непарної (2k-1)-oї позиції(k=1, 2,..., К) порівнюється із сусіднім елементом парної 2k-oї позиції і більший з них переміщується у парну 2k-y позицію, менший переміщується у непарну (2k-1)-у позицію, а у парних циклах в k-ій парі елемент парної 2k-oї позиції порівнюється із сусіднім елементом непарної (2k+1)-ої позиції і більший з них переміщується у непарну (2k+1)-y позицію, менший переміщується у парну 2k-y позицію, при непарній кількості елементів масиву вводиться додатковий нульовий елемент нульової позиції, який в подальшому розглядається як елемент (2k-2)-ої позиції, причому в цьому випадку у непарних циклах в k-ій парі елемент парної (2k-2)-ої позиції порівнюється із сусіднім елементом непарної (2k-1)-oї позиції і більший з них переміщується у непарну (2k-1)-у позицію, менший переміщується у парну (2k-2)-y позицію, а у парних циклах в k-ій парі елемент непарної (2k-1)-oї позиції порівнюється із сусіднім елементом парної 2k-oї позиції і більший з них переміщується у парну 2k-y позицію, менший переміщується у непарну (2k-1)-y позицію, крім того формується у кожному парному циклі додаткова пара елементів, яку утворюють елементи першої або нульової позиції і старшої m-ої позиції, в якій ці елементи порівнюються і більший з них переміщується у mту позицію, менший переміщується у першу або нульову позицію, а процес сортування закінчується, якщо у будь-якому циклі, крім першого, не переміщуються елементи у всі х К парах елементів. На фіг.1, 2 представлені відповідно топологія з'єднань елементів у сортувальній мережі типу "стрічка" і приклади сортування на цій мережі; на фіг.3, 4 представлені відповідно топологія з'єднань елементів у сортувальній мережі типу "кільце" і приклади сортування у цій мережі; на фіг.5 наведено приклади особливого випадку при сортуванні у мережі типу "кільце". Сортування масиву чисел відбувається таким чином. Алгоритм роботи сортувальної мережі типу "стрічка"(фіг.1) має такий вигляд. 1. Формується група(стрічка) пар із сусідніх елементів масиву чисел незалежно від кількості m елементів масиву за таким правилом: а) у всі х непарних циклах кожна пара елементів складається з (2к-1)-их і 2k-их елементів(k= 1, 2,..., К)(фіг.1а, б); б) у всі х парких циклах кожна пара елементів складається з 2k-иx і (2k+1)-их елементів(фіг.1а, б). 2. У кожній парі елементів за результатом порівняння виконуються такі дії: а) якщо елемент молодшої позиції менший за значенням, ніж елемент старшої позиції, то переміщення(транспозиції) елементів не відбувається; б) якщо елемент молодшої позиції більший за значенням, ніж елемент старшої позиції, то відбувається їх переміщення(транспозиція). 3. Перевіряється умова відсутності будь-якого переміщення елементів у всі х парах елементів. Якщо так, то виконується ще один контрольний цикл і перехід до п.4; якщо ні, то виконується перехід до п.1. 4. Процес сортування закінчується, якщо у двох послідовних циклах виконується умова п.3. Таким чином, для цього алгоритму мінімальна кількість циклів сортування дорівнює двом, а максимальна (m+2), де m - кількість елементів у масиві, тобто: Nmin=2, N max=m+2. (1) Приклади сортування масиву чисел на сортувальній мережі тилу "стрічка" з урахуванням розмірності m масиву показані на фіг.2: якщо m є парне число(фіг.2,а), якщо m є непарне число(фіг.2,6). Тут застосовано такі умовні позначення: ] - ознака пари елементів, що порівнюються; ]® - ознака переміщення(транспозиції) елементів у відповідній парі. Елементи масиву взято із діапазону цілих додатних чисел(0, 9). Алгоритм роботи сортувальної мережі типу "кільце"(фіг.3) має такий вигляд. 1. Формується кільце пар із сусідніх елементів масиву чисел з урахуванням розмірності m масиву за таким правилом: а) якщо m - парне число(фіг.3, а), то у всіх непарних циклах кожна пара елементів складається з (2k-1)их і 2k-их елементів, а у всіх парних циклах кожна пара елементів складається з 2k-их і (2k+1)-иx елементів, причому 1-ий і m-й елементи вважаються сусідніми і створюють К-у пару елементів; б) якщо m - непарне число(фіг.3, б), то вводиться нульовий елемент у нульову позицію і у всіх непарних циклах кожна пара елементів складається з (2k-2)-их і (2k-1)-их елементів(k=0, 1, 2,..., К), а у всі х парних циклах кожна пара елементів складається з (2k-1)-их і 2k-их елементів, причому нульовий і m-ий елементи вважаються сусідніми і створюють К-у пару елементів. 2. У кожній парі елементів за результатом порівняння виконуються такі дії: а) якщо m - парне число і елемент молодшої(або першої) позиції менший за значенням, ніж елемент старшої(або m-ої) позиції, то переміщення елементів не відбувається; але якщо цей елемент більший за значенням, то відбувається переміщення(транспозиція) елементів відповідної пари; б) якщо m - непарне число і елемент молодшої(або нульової) позиції менший за значенням, ніж елемент старшої(або m-ої) позиції, то переміщення елементів не відбувається; але якщо цей елемент більший за значенням, то відбувається переміщення(транспозиція) елементів відповідної пари. 3. Перевіряється умова відсутності будь-якого переміщення елементів у всі х парах елементів. Якщо так і це не перший цикл, то процес сортування закінчується, якщо це перший цикл, а також при невиконанні умови п.3 виконується перехід до п. 1. Отже, мінімальна і максимальна кількість циклів сортування для цього алгоритму дорівнює таким величинам: Nmin=2, N max=m+1. (2) Приклади сортування того самого масиву чисел у сортувальній мережі типу "кільце" з урахуванням розмірності m масиву показані на фіг.4: якщо m є парне число(фіг.4, а), якщо m є непарне число(фіг.4, б). Тут додатково застосовано такі умовні позначення: [ - ознака додаткової пари крайніх елементів, що порівнюються; [ ® - ознака переміщення(транспозиції) елементів у відповідній парі. ® Для наочності на фіг.5 наведено приклад особливого випадку сортування, а саме, коли масив чисел відсортований у зворотному порядку(за спаданням значень чисел). Тут збережено введені раніше умовні позначення. Приклад на фіг.5 підтверджує часові залежності(2). Доведемо можливість застосування одного контрольного циклу замість двох. Нехай n-ий цикл був останній, в якому виконувались переміщення елементів у парах. Але, якщо у (n+1)-му циклі не відбувається жодного переміщення елементів у парах, то можна стверджувати, що у (n+2)-му циклі також не буде переміщень, оскільки будуть порівнюватись елементи в парах, які вже впорядковані у n-му циклі. Ці міркування стосуються всіх циклів, окрім першого. При відсутності переміщень елементів у першому циклі необхідно виконати наступний цикл для контролю. Отже, саме спосіб сортування із замиканням сортувальної мережі у "кільце", а також можливість виконання тільки одного контрольного циклу дозволяють покращити часові характеристики процесу сортування. Запропонований спосіб дозволяє зменшити тривалість процесу сортування масиву чисел за рахунок введення додаткового нульового елемента при непарній розмірності вхідного масиву і формуванні додаткової пари елементів, яку утворюють перший(або введений нульовий) та старший елементи масиву у всіх парних циклах сортування. Це дозволяє підвищити швидкодію пристроїв сортування за рахунок зменшення кількості циклів як мінімум на один цикл.