Study of the efficiency of some deterministic preprocessing methods for sorting algorithms
To verify the hypothesis about decrease in time of sorting by algorithms of different computational complexity experiments have been conducted. Several ideas on deterministic preprocessing of data arrays for sorting algorithms have been tested. The following algorithms are proposed: quick preprocess...
Збережено в:
| Дата: | 2023 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Інститут програмних систем НАН України
2023
|
| Теми: | |
| Онлайн доступ: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/589 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Problems in programming |
| Завантажити файл: |  |
Репозитарії
Problems in programming| id |
pp_isofts_kiev_ua-article-589 |
|---|---|
| record_format |
ojs |
| resource_txt_mv |
ppisoftskievua/fa/ff5936933354b7751376d74a9bd245fa.pdf |
| spelling |
pp_isofts_kiev_ua-article-5892024-04-26T21:18:20Z Study of the efficiency of some deterministic preprocessing methods for sorting algorithms Дослідження ефективності деяких детермінованих методів передобробки сортування даних Shynkarenko, V.I. Makarov, O.V. sorting algorithm; sorting; time efficiency; combined algorithm; preprocessing UDK 004.4 алгоритм сортування, сортування; часова ефективність; комбінований алгоритм; передобробка УДК 004.4 To verify the hypothesis about decrease in time of sorting by algorithms of different computational complexity experiments have been conducted. Several ideas on deterministic preprocessing of data arrays for sorting algorithms have been tested. The following algorithms are proposed: quick preprocessing – prediction of the index of an element in a sorted array and permutation, preprocessing with memory - prediction and permutation with memorization of previously set elements, preprocessing with reordering – reverting sequences of elements sorted in reverse order. Also proposed block variations of quick and preprocessing with memory, which are performed for parts of the array of a given length. It has been defined that the higher efficiency of preprocessing is achieved by using with sorting algorithms, which are significantly accelerated on sorted (or almost sorted) arrays of data. Block preprocessing methods can be performed faster due to the possibility of avoiding cache misses, but show a lower percentage of array sorting. Experiments were conducted to evaluate the effectiveness of various sorting algorithms after and together with the proposed preprocessing methods.Prombles in programming 2023; 4: 3-14 Для перевірки гіпотези щодо зменшення часу сортування алгоритмами різної обчислювальної складності здійснено експерименти. Опрацьовано декілька ідей із детермінованої передобробки масивів даних для алгоритмів сортування. Запропоновані відповідні алгоритми: швидка передобробка – передбачення індексу елемента у відсортованому масиві і перестановка, передобробка з пам’яттю – передбачення і перестановка із запам’ятовуванням раніше встановлених елементів, передобробка із розворотом – розвертання послідовностей елементів, відсортованих у зворотному порядку. Також запропоновані блочні варіації швидкої та передобробки з пам’яттю, які виконуються для частин масиву заданої довжини. Встановлено, що більшу ефективність передобробки вони показують разом із алгоритмами сортування, які значно прискорюються на відсортованих (або майже відсортованих) масивах даних. Блочні передобробки можуть виконуватися швидше через можливість уникнення промахів кешу (cache miss), однак показують нижчий відсоток впорядкованості масиву. Виконані експерименти з оцінки ефективності різних алгоритмів сортування після і разом із запропонованими передобробками.Prombles in programming 2023; 4: 3-14 Інститут програмних систем НАН України 2023-12-18 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/589 10.15407/pp2023.04.003 PROBLEMS IN PROGRAMMING; No 4 (2023); 3-14 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 4 (2023); 3-14 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 4 (2023); 3-14 1727-4907 10.15407/pp2023.04 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/589/646 Copyright (c) 2023 PROBLEMS IN PROGRAMMING |
| institution |
Problems in programming |
| baseUrl_str |
https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| datestamp_date |
2024-04-26T21:18:20Z |
| collection |
OJS |
| language |
Ukrainian |
| topic |
sorting algorithm sorting time efficiency combined algorithm preprocessing UDK 004.4 |
| spellingShingle |
sorting algorithm sorting time efficiency combined algorithm preprocessing UDK 004.4 Shynkarenko, V.I. Makarov, O.V. Study of the efficiency of some deterministic preprocessing methods for sorting algorithms |
| topic_facet |
sorting algorithm sorting time efficiency combined algorithm preprocessing UDK 004.4 алгоритм сортування сортування; часова ефективність; комбінований алгоритм; передобробка УДК 004.4 |
| format |
Article |
| author |
Shynkarenko, V.I. Makarov, O.V. |
| author_facet |
Shynkarenko, V.I. Makarov, O.V. |
| author_sort |
Shynkarenko, V.I. |
| title |
Study of the efficiency of some deterministic preprocessing methods for sorting algorithms |
| title_short |
Study of the efficiency of some deterministic preprocessing methods for sorting algorithms |
| title_full |
Study of the efficiency of some deterministic preprocessing methods for sorting algorithms |
| title_fullStr |
Study of the efficiency of some deterministic preprocessing methods for sorting algorithms |
| title_full_unstemmed |
Study of the efficiency of some deterministic preprocessing methods for sorting algorithms |
| title_sort |
study of the efficiency of some deterministic preprocessing methods for sorting algorithms |
| title_alt |
Дослідження ефективності деяких детермінованих методів передобробки сортування даних |
| description |
To verify the hypothesis about decrease in time of sorting by algorithms of different computational complexity experiments have been conducted. Several ideas on deterministic preprocessing of data arrays for sorting algorithms have been tested. The following algorithms are proposed: quick preprocessing – prediction of the index of an element in a sorted array and permutation, preprocessing with memory - prediction and permutation with memorization of previously set elements, preprocessing with reordering – reverting sequences of elements sorted in reverse order. Also proposed block variations of quick and preprocessing with memory, which are performed for parts of the array of a given length. It has been defined that the higher efficiency of preprocessing is achieved by using with sorting algorithms, which are significantly accelerated on sorted (or almost sorted) arrays of data. Block preprocessing methods can be performed faster due to the possibility of avoiding cache misses, but show a lower percentage of array sorting. Experiments were conducted to evaluate the effectiveness of various sorting algorithms after and together with the proposed preprocessing methods.Prombles in programming 2023; 4: 3-14 |
| publisher |
Інститут програмних систем НАН України |
| publishDate |
2023 |
| url |
https://pp.isofts.kiev.ua/index.php/ojs1/article/view/589 |
| work_keys_str_mv |
AT shynkarenkovi studyoftheefficiencyofsomedeterministicpreprocessingmethodsforsortingalgorithms AT makarovov studyoftheefficiencyofsomedeterministicpreprocessingmethodsforsortingalgorithms AT shynkarenkovi doslídžennâefektivnostídeâkihdetermínovanihmetodívperedobrobkisortuvannâdanih AT makarovov doslídžennâefektivnostídeâkihdetermínovanihmetodívperedobrobkisortuvannâdanih |
| first_indexed |
2024-09-16T04:08:07Z |
| last_indexed |
2024-09-16T04:08:07Z |
| _version_ |
1818528215651581952 |
| fulltext |
Експертні та інтелектуальні інформаційні системи
3
УДК 004.4 http://doi.org/10.15407/pp2023.04.003
В.І. Шинкаренко, О.В. Макаров
ДОСЛІДЖЕННЯ ЕФЕКТИВНОСТІ
ДЕЯКИХ ДЕТЕРМІНОВАНИХ МЕТОДІВ ПЕРЕДОБРОБКИ
СОРТУВАННЯ ДАНИХ
Для перевірки гіпотези щодо зменшення часу сортування алгоритмами різної обчислювальної складності
здійснено експерименти. Опрацьовано декілька ідей із детермінованої передобробки масивів даних для
алгоритмів сортування. Запропоновані відповідні алгоритми: швидка передобробка – передбачення ін-
дексу елемента у відсортованому масиві і перестановка, передобробка з пам’яттю – передбачення і пере-
становка із запам’ятовуванням раніше встановлених елементів, передобробка із розворотом –
розвертання послідовностей елементів, відсортованих у зворотному порядку. Також запропоновані бло-
чні варіації швидкої та передобробки з пам’яттю, які виконуються для частин масиву заданої довжини.
Встановлено, що більшу ефективність передобробки вони показують разом із алгоритмами сортування,
які значно прискорюються на відсортованих (або майже відсортованих) масивах даних. Блочні передоб-
робки можуть виконуватися швидше через можливість уникнення промахів кешу (cache miss), однак по-
казують нижчий відсоток впорядкованості масиву. Виконані експерименти з оцінки ефективності різних
алгоритмів сортування після і разом із запропонованими передобробками.
Ключові слова: алгоритм сортування, сортування, часова ефективність, комбінований алгоритм, передо-
бробка.
Вступ
Ера великих даних (Big Data) відкри-
ває нові можливості, але має й більше про-
блем для алгоритмів сортування. Класичні
алгоритми сортування не можуть пристосу-
ватися до вибухового зростання даних. Іс-
нує велика кількість алгоритмів сортування
за різноманіттям сценаріїв застосування,
пристроїв для зберігання даних і стратегій
удосконалення.
Алгоритми сортування класифіку-
ються за різними показниками часової ефе-
ктивності, стабільності і вимог до
виділення додаткової пам’яті. Прийнято
оцінювати алгоритми за показником асим-
птотичної обчислювальної складності
О [1]. Найбільш популярні алгоритми сор-
тування, такі як швидке сортування (Quick
sort) чи сортування злиттям (Merge sort),
мають обчислювальну складність у серед-
ньому 𝑂𝑂(𝑛𝑛 ∗ 𝑙𝑙𝑙𝑙𝑙𝑙(𝑛𝑛)). Однак на невеликих
наборах даних сортування вставками
(Insertion sort) з обчислювальною складні-
стю 𝑂𝑂(𝑛𝑛2) працює швидше.
Ефективні реалізації зазвичай вико-
ристовують гібридний алгоритм, що поєд-
нує асимптотично ефективний алгоритм
для загального сортування із сортуванням
вставками для невеликих масивів у нижній
частині рекурсії. Використовуються і скла-
дніші варіанти, такі як, Timsort [2] – попе-
редній аналіз даних та пошук
відсортованих послідовностей, розбиття
масиву на відсортовані ділянки за допомо-
гою сортування вставками і модифікований
алгоритм злиття в один відсортований ма-
сив. Або Introsort [3], що починає із швид-
кого сортування, потім переходить на
Heapsort, коли глибина рекурсії перевищує
заданий рівень, і закінчує сортуванням не-
великих послідовностей за допомогою сор-
тування вставками.
Досліджувалися можливі модифіка-
ції існуючих алгоритмів для покращення їх-
ньої часової ефективності. Наприклад, у [4]
використовувалось сортування вставками
із розбиттям масиву на дві відсортовані ча-
стини і одну невідсортовану, з якої вибира-
лись елементи. У [5] досліджувалось
швидке сортування з різною кількістю pivot
елементів.
Попередню обробку можна предста-
вити як аналіз і деяку перестановку елеме-
нтів масиву. Залежно від основного
алгоритму сортування попередня обробка
може робити перестановки, які зменшують
час сортування. Або запобігають виник-
© В.І. Шинкаренко, О.В. Макаров, 2023
ISSN 1727-4907. Проблеми програмування. 2023. №4
Експертні та інтелектуальні інформаційні системи
4
ненню найгірших ситуацій, що призводять
до погіршання часової ефективності алго-
ритму. В даній праці запропоновано декі-
лька алгоритмів попередньої обробки
масивів сортованих даних.
У [6] досліджувалися методи стоха-
стичної передобробки. Випадкові елеме-
нти, вибрані з усього масиву або із його
половин, певну кількість разів (кратну роз-
міру масиву) порівнюються і, якщо вони
йдуть у зворотньому порядку, міняються
місцями.
У [7] розглядається метод стохасти-
чної передобробки, в якому випадкові еле-
менти міняються місцями спочатку в межах
половин вхідного масиву, а потім ще раз у
межах цілого масиву. Також представлений
детермінований метод передобробки, в
якому порівнюються елементи з кінця та
початку масиву і, якщо вони стоять у зво-
ротному порядку, виконується перестано-
вка, а індекси порівнюваних елементів
зміщуються до середини масиву. Процес
повторюється для усіх елементів масиву, а
потім рекурсивно для підмасивів.
Показники ефективності
передобробки
У цьому дослідженні ефективність
передобробки оцінювалась за декількома
показниками.
Поліпшення впорядкованості ма-
сиву визначається за показником невпоряд-
кованості масиву [6] після закінчення
одинарних або серійних перестановок:
𝑈𝑈 = 1
𝑁𝑁 (∑ |𝑗𝑗 − 𝑖𝑖|
𝑚𝑚𝑚𝑚𝑚𝑚( 𝑖𝑖, 𝑁𝑁 − 𝑖𝑖)
𝑁𝑁
𝑖𝑖=0
) ∗ 100%, (1)
де 𝑗𝑗 – індекс елемента у відсортованому
масиві, 𝑖𝑖 – індекс того ж елемента у нев-
порядкованому масиві, 𝑁𝑁 – загальна кіль-
кість елементів масиву. Тут і далі
індексація масивів починається з нуля.
Якщо у масиві є декілька однакових еле-
ментів під індексами i1 та i2, для них бу-
дуть використані відповідні індекси у
відсортованому масиві j1 та j2. Зазначимо,
що у разі i1 < i2, тоді j1 < j2, як за умови
стабільного сортування.
Для визначення найбільш ефектив-
ного алгоритму попередньої обробки ма-
сиву використовується формула:
𝐸𝐸𝐸𝐸 = (
𝑈𝑈0 − 𝑈𝑈𝑝𝑝
𝑈𝑈0
) ∗ 100% (2)
де 𝑈𝑈0 – показник невпорядкованості вхід-
ного масиву, 𝑈𝑈𝑝𝑝 – показник невпорядкова-
ності масиву після виконання передобробки.
Часова ефективність алгоритмів
оцінюється за S показником [8]. Якщо 𝑉𝑉∗ –
множина можливих значень обсягу даних,
𝑇𝑇∗ – множина можливих типів даних, 𝑋𝑋∗ –
множина можливих значень даних, Ψ∗ –
множина можливих програмних середо-
вищ, ℜ∗ – множина архітектур ЕОМ, на
яких можлива реалізація алгоритмів, тоді
для порівняння часової ефективності альте-
рнативних обчислювальних алгоритмів ви-
значається ступінь переваги одного (i-го)
алгоритму над іншим (j-им) на обмежених
множинах, що є підмножинами зазначених
вище множин �̅�𝑉 ⊆ 𝑉𝑉∗, �̅�𝑇 ⊆ 𝑇𝑇∗, �̅�𝑋 ⊆ 𝑋𝑋∗,
Ψ̅ ⊆ Ψ∗, ℜ̅ ⊆ ℜ∗:
𝑆𝑆𝑈𝑈𝑆𝑆𝑖𝑖𝑖𝑖|�̅�𝑉, �̅�𝑇, �̅�𝑋, Ψ̅, ℜ̅ = (3)
= 1
𝑁𝑁 ∑ ∑ ∑ ∑ ∑ 𝑔𝑔𝑖𝑖𝑖𝑖(𝑣𝑣, 𝑡𝑡, 𝑚𝑚, 𝜓𝜓, 𝑟𝑟),
∀𝑟𝑟∈ℜ̅∀𝜓𝜓∈Ψ̅∀𝑥𝑥∈�̅�𝑋∀𝑡𝑡∈�̅�𝑇∀𝑣𝑣∈�̅�𝑉
де 𝑁𝑁 – загальна кількість виконань, 𝑔𝑔𝑖𝑖𝑖𝑖 –
ступінь переваги i-го алгоритму над j-им в
точці, визначається як:
𝑔𝑔𝑖𝑖𝑖𝑖(𝑣𝑣, 𝑡𝑡, 𝑚𝑚, 𝜓𝜓, 𝑟𝑟)
=
𝜏𝜏𝑖𝑖(𝑣𝑣, 𝑡𝑡, 𝑚𝑚, 𝜓𝜓, 𝑟𝑟) − 𝜏𝜏𝑖𝑖(𝑣𝑣, 𝑡𝑡, 𝑚𝑚, 𝜓𝜓, 𝑟𝑟)
max (𝜏𝜏𝑖𝑖(𝑣𝑣, 𝑡𝑡, 𝑚𝑚, 𝜓𝜓, 𝑟𝑟), 𝜏𝜏𝑖𝑖(𝑣𝑣, 𝑡𝑡, 𝑚𝑚, 𝜓𝜓, 𝑟𝑟)), (4)
де 𝜏𝜏𝑖𝑖(𝑣𝑣, 𝑡𝑡, 𝑚𝑚, 𝜓𝜓, 𝑟𝑟) – час виконання j-го алго-
ритму, 𝜏𝜏𝑖𝑖(𝑣𝑣, 𝑡𝑡, 𝑚𝑚, 𝜓𝜓, 𝑟𝑟) – час виконання i-го
алгоритму.
В експериментах змінюються роз-
міри масивів даних (�̅�𝑉 ⊆ 𝑉𝑉∗) і значення
елементів (�̅�𝑋 ⊆ 𝑋𝑋∗). Тип даних, програмна
середа та архітектура ЕОМ залишаються
постійними і можуть бути видалені з рів-
няння. Кінцева формула для визначення
ступеня переваги алгоритму має вигляд:
𝑔𝑔𝑖𝑖𝑖𝑖(𝑣𝑣, 𝑡𝑡) =
𝜏𝜏𝑖𝑖(𝑣𝑣, 𝑚𝑚) − 𝜏𝜏𝑖𝑖(𝑣𝑣, 𝑚𝑚)
max (𝜏𝜏𝑖𝑖(𝑣𝑣, 𝑚𝑚), 𝜏𝜏𝑖𝑖(𝑣𝑣, 𝑚𝑚)), (5)
Експертні та інтелектуальні інформаційні системи
5
Експериментально статистична оці-
нка S показника, як обґрунтовано у [8], об-
числюється так:
𝑆𝑆𝑖𝑖𝑖𝑖 =
1
𝑁𝑁∑𝑔𝑔𝑖𝑖𝑖𝑖(𝑣𝑣, 𝑥𝑥𝑘𝑘)
𝑁𝑁
𝑘𝑘=1
(6)
де N – кількість експериментальних випро-
бувань алгоритму, 𝑣𝑣 – фіксований у конкре-
тному експерименті розмір масиву, 𝑥𝑥𝑘𝑘 –
випадковим чином сформований масив у 𝑘𝑘-
тому випробуванні. В експериментах вико-
ристовується N рівне 51.
Детерміновані методи
передобробки
Розглянемо запропоновані авторами
методи передобробок, що використову-
ються для покращення часової ефективно-
сті алгоритмів сортування.
Швидка передобробка (QP). Осно-
вна ідея швидкої передобробки полягає у
спробі «передбачити» позицію елемента в
масиві. Знаходиться мінімальне та макси-
мальне значення елементів масиву. Для ко-
жного елемента розраховується
передбачуване місце (індекс) у відсортова-
ному масиві
𝑖𝑖 =
(𝑥𝑥𝑖𝑖 − min
𝑖𝑖
𝑥𝑥𝑖𝑖)
(max
𝑖𝑖
𝑥𝑥𝑖𝑖 − min
𝑖𝑖
𝑥𝑥𝑖𝑖)
∗ (𝑁𝑁 − 1), (7)
де 𝑥𝑥𝑖𝑖– поточний елемент масиву, 𝑁𝑁 – кіль-
кість елементів у масиві. Виконується пере-
становка поточного елемента з елементом
за передбаченим індексом. Операція повто-
рюється аж доки для поточного елемента не
буде передбачений його ж індекс, тобто,
коли елемент уже стоїть на передбаченому
місці, або елемент за передбаченим індек-
сом дорівнює поточному. Кількість перед-
бачень для поточного місця елемента не
може перевищувати наперед заданого M
(це дозволяє уникнути зациклювання).
Після передобробки деяка кількість
елементів опиниться на місцях, відповід-
них їхнім місцям у відсортованому масиві.
Таким чином зменшується кількість перес-
тановок елементів, що буде виконана без-
посередньо алгоритмом сортування.
Покажемо на масиві випадкових ці-
лих чисел у діапазоні від 0 до 9 роботу пе-
редобробки. Визначаємо мінімальний і ма-
ксимальний елементи масиву. Вони дорів-
нюють відповідно 0 і 9. Максимальний
індекс дорівнює N-1 = 9. Починаємо пере-
добробку з першого елемента масиву. Жи-
рним шрифтом виділено поточний елемент.
Затіненням жовтого кольору показано пе-
редбачене місце для поточного елемента.
Праворуч від масиву на кожному кроці на-
ведені значення показника невпорядкова-
ності масиву (Ui).
6 0 4 4 1 3 8 9 2 5 U0=39.5
8 0 4 4 1 3 6 9 2 5 U1=38.8
2 0 4 4 1 3 6 9 8 5 U2=25.3
4 0 2 4 1 3 6 9 8 5 U3=24.8
1 0 2 4 4 3 6 9 8 5 U4=17.1
0 1 2 4 4 3 6 9 8 5 U5=14.9
0 1 2 4 4 3 6 9 8 5 U6=14.9
0 1 2 4 4 3 6 9 8 5 U7=14.9
0 1 2 4 4 3 6 9 8 5 U8=14.9
0 1 2 4 4 3 6 9 8 5 U9=14.9
0 1 2 4 4 3 6 9 8 5 U10=14.9
0 1 2 3 4 4 6 9 8 5 U11=7.9
0 1 2 3 4 4 6 9 8 5 U12=7.9
0 1 2 3 4 4 6 9 8 5 U13=7.9
0 1 2 3 4 4 6 5 8 9 U14=3.1
0 1 2 3 4 5 6 4 8 9 U15=6.5
0 1 2 3 4 5 6 4 8 9 U16=6.5
0 1 2 3 4 5 6 4 8 9 U17=6.5
Рис.1. Приклад швидкої передобробки
(QP)
Передобробка з пам’яттю (PM).
Відмінність від швидкої передобробки по-
лягає у запам’ятовуванні передбачених ін-
дексів, у яких була виконана перестановка.
Алгоритм не намагається передбачати ін-
Експертні та інтелектуальні інформаційні системи
6
декс для того ж самого елемента декілька
разів і для поточного елемента буде знай-
дено наступний ще непередбачений індекс.
У передобробці з пам’яттю додат-
ково використовується окремий масив бу-
левих змінних. Після того, як у
передбачений індекс p встановлюється еле-
мент масиву, булевий флаг за індексом p
встановлюється в значення true. Булеві зна-
чення, що відповідають кожному елементу
масиву, відобразимо під кожним елемен-
том. Напочатку усі булеві флаги дорівню-
ють false, що відображається знаком “-“.
Після встановлення елемента булеве зна-
чення зміниться на true (“+”). Жирним виді-
лимо поточний елемент, затіненням
жовтого кольору – елемент під передбаче-
ним індексом, зеленого – елемент переста-
влений за передбаченим на попередньому
кроці індексом. Праворуч від масиву на ко-
жному кроці записані значення невпоряд-
кованості масиву (Ui).
6 0 4 4 1 3 8 9 2 5 U0=39.49
- - - - - - - - - -
8 0 4 4 1 3 6 9 2 5 U1=38.82
- - - - - - + - - -
2 0 4 4 1 3 6 9 8 5 U2=25.32
- - - - - - + - + -
4 0 2 4 1 3 6 9 8 5 U3=24.82
- - + - - - + - + -
1 0 2 4 4 3 6 9 8 5 U4=17.06
- - + - + - + - + -
0 1 2 4 4 3 6 9 8 5 U5=14.9
5
- + + - + - + - + -
0 1 2 4 4 3 6 9 8 5 U6=14.9
5
+ + + - + - + - + -
0 1 2 3 4 4 6 9 8 5 U7=7.85
+ + + - + + + - + -
0 1 2 3 4 4 6 9 8 5 U8=7.85
+ + + + + + + - + -
0 1 2 3 4 4 6 5 8 9 U9=3.09
+ + + + + + + - + +
0 1 2 3 4 4 6 5 8 9 U10=3.1
+ + + + + + + + + +
Рис. 2. Приклад передобробки з пам’яттю
Потребує пояснення вибір місця і
перестановка на сьомому кроці, тому що
для елемента «4» передбачене місце під ін-
дексом 4, де стоїть елемент «4», але у ма-
сиві флагів стоїть «+». Тому вибирається
наступне після передбаченого місце, в
якому флаг дорівнює «-». Таке місце знахо-
диться під індексом «5», за яким стоїть еле-
мент «3».
Блочна локальна передобробка.
Ідея блочної локальної передобробки поля-
гає в розбитті масиву на блоки певної дов-
жини і застосуванні алгоритмів, описаних
раніше на кожному підмасиві. Маємо дві
комбінації алгоритмів: блочна локальна
швидка передобробка (BLQP) і блочна ло-
кальна передобробка з пам’яттю (BLPM). У
результаті початковий масив буде мати N
частково (або повністю) відсортованих під-
масивів. Масив після локальної передобро-
бки матиме «форму пилки». За умови
правильного вибору довжини блоку, мен-
шої за довжину кешу процесора, поділеної
на розмір елементів у сортованому масиві,
можна значно зменшити кількість (або вза-
галі уникнути) промахів кешу (cache miss).
У разі, якщо розмір блока буде дуже вели-
ким, отримаємо багато промахів кешу і зме-
ншення часової ефективності роботи
алгоритму.
Блочна глобальна передобробка.
Глобальна передобробка також включає ро-
збиття масиву на блоки певної довжини і
застосування швидкої (BGQP) та передоб-
робки з пам’яттю (BGPM) до підмасивів.
Відмінність від локального алгоритму по-
лягає у тому, що для кожного елемента ма-
сиву передбачається глобальний індекс,
тобто приблизне місце, на якому стояв би
даний елемент у відсортованому масиві. Пі-
сля передбачення елемент може бути пере-
ставлений, тільки якщо передбачений
індекс не виходить за межі поточного
блока. Такий підхід також дозволяє уник-
Експертні та інтелектуальні інформаційні системи
7
нути промахів кешу (cache miss). Але приб-
лизна вірогідність того, що елемент буде
переставлений, дорівнює 1 𝐾𝐾⁄ (де К – кіль-
кість блоків), для масиву рівномірно розпо-
ділених випадкових чисел.
Попередня обробка із розворо-
том (SR). В останньому варіанті попере-
дньої обробки виконується прохід
масивом, й усі послідовності, відсорто-
вані у зворотному напрямку, розверта-
ються. Тож максимальна довжина
послідовностей, відсортованих у зворот-
ному напрямку, буде дорівнювати 2 (кі-
нець попередньої і початок наступної
відсортованої послідовностей). Найбіль-
ший вплив даний вид попередньої обро-
бки буде мати для швидкого сортування
(Quick sort), для якого вхідний масив,
відсортований у зворотному порядку, є
спеціальним випадком, де обчислюва-
льна складність зростає до 𝑂𝑂(𝑛𝑛2).
Наведемо приклад роботи поперед-
ньої обробки із розворотом на масиві випа-
дкових цілих чисел від 0 до 9.
Послідовності, відсортовані у зворотному
порядку, перед розворотом виділені заті-
ненням жовтого кольору, після – зеленого
кольору.
6 0 4 4 1 3 8 9 2 5 U0=39.49
0 6 4 4 1 3 8 9 2 5 U1=38.05
6 0 1 4 4 3 8 9 2 5 U2=32.04
0 6 1 4 4 3 8 2 9 5 U3=30.07
Рис.3. Приклад передобробки
із розворотом
Отож, досліджено сім детермінованих ал-
горитмів передобробки:
– швидка передобробка (QP);
– передобробка з пам’яттю (PM);
– передобробка із розворотом (SR);
– блочна локальна швидка передобробка
(BLQP);
– блочна локальна передобробка з
пам’яттю (BLPM);
– блочна глобальна швидка передобробка
(BGQP);
– блочна глобальна передобробка з
пам’яттю (BGPM).
Організація експериментів
із дослідження ефективності
передобробки
Структури даних. Дослідження ві-
дбувалося на масивах цілих 4-байтових чи-
сел. Пам’ять під масиви виділялася
безпосередньо засобами C++, створенням
std::vector<int> та викликом
std::vector<int>::reserve. Сортований масив
заповнювався рівномірно розподіленими
псевдовипадковими числами від 0 до N-1,
де N – кількість елементів масиву 𝑥𝑥𝑖𝑖. Псев-
довипадкові числа були отримані генерато-
ром псевдовипадкових величин
std::mt19937 з початковим станом, заданим
генератором std::random_device. Згенеро-
вані числа приведені до значення із зада-
ного інтервалу за допомогою
std::uniform_int_distribution.
Особливості вимірювання часу
виконання алгоритму. У зв’язку з неста-
більністю роботи потоків операційної сис-
теми Windows та технічних засобів, час
сортування одного й того ж масиву буде ви-
падковим із деякою дисперсією.
Час сортування визначався як меді-
анний час із M-кратним виконанням сорту-
вання одного й того ж масиву даних (дані
копіювалися з оригінального невідсортова-
ного масиву перед кожним вимірюванням).
Перед виконанням окремого сорту-
вання (паралельного вимірювання) викону-
валося очищення кешу. Для цього
застосовувався такий спосіб: створювався
масив розміром 𝑁𝑁 = 8 ∗ 220 4-байтових
псевдовипадкових чисел, 2 випадкових еле-
менти масиву мінялись місцями за допомо-
гою std::swap N разів.
Технічні засоби. Експерименти ви-
конані на ноутбуці з технічними характери-
стиками, наведеними у табл. 1.
Таблиця 1
Характеристики технічних засобів
Характеристики центрального
процесору
Поле Значення
Тип Intel Core i7-6700HQ, 2600
МГц
Експертні та інтелектуальні інформаційні системи
8
Кількість
ядер
4
Кеш L1 256 KB per core
Кеш L2 1 MB per core (On-Die, ECC,
Full-Speed)
Кеш L3 6 MB (On-Die, ECC, Full-
Speed)
Набір ін-
струкцій
64-Bit, Intel® SSE4.1, Intel®
SSE4.2, Intel® AVX2, Intel
AES
Характеристики оперативної пам’яті
Поле Значення
Формфак-
тор
FB-DIMM
Розмір
модулю
8 ГБ
Кількість
модулів
2 х 8 ГБ
Результати експериментів
Ефективність передобробки будемо
оцінювати за показниками (1)-(3). Для дос-
лідження обирались загальновідомі алгори-
тми сортування, які зазвичай
використовують для вирішення задач із рі-
зними вимогами. Швидке сортування [9]
(Quick sort) є одним із найшвидших універ-
сальних алгоритмів сортування. Викорис-
товується для великих списків, коли
важлива ефективність. Сортування встав-
ками [10] (Insertion sort) ефективне для ма-
лих або частково відсортованих списків.
Може використовуватись як базовий варі-
ант для інших алгоритмів. Шейкерне сорту-
вання [11] (Cocktail sort) подібне до
сортування бульбашкою [12], але викону-
ється в обидва напрямки. Може бути ефек-
тивно використане для невеликих або
майже відсортованих масивів.
Дослідження невпорядкованості
масиву до та після передобробок. Для ви-
значення найбільш ефективного алгоритму
попередньої обробки було проведено екс-
перимент, де для масиву випадкових цілих
чисел у діапазоні [0, N-1] (де N – розмір ма-
сива) вираховувався показник ефективно-
сті за формулою (2). Максимально можливе
значення ефективності 100% означало б,
що результатом передобробки є повністю
відсортований масив. На рисунку .4 видно,
що найбільшу ефективність має передобро-
бка з пам’яттю. Далі із значенням близько
62% йде швидка передобробка. Передобро-
бка з розворотом показала значення ефек-
тивності близьке до 0% для усіх масивів
даних з експерименту.
Рис.4. Ефективність передобробок
Дослідження часової ефективності
швидкого сортування з використанням
різних типів передобробок.
Рис.5. S оцінка швидкого сортування після
швидкої, з пам’яттю і передобробки
з розворотом
Найбільше зростання часової ефек-
тивності швидкого сортування дає попере-
дня обробка з пам’яттю. Значення S оцінки
стартує з 0.35 на 1000 елементів і стрімко
зростає у разі збільшення розміру масиву.
На 50 – 60 тисячах елементів S оцінка дося-
гає 0.5 і лишається на тому ж рівні за пода-
льшого збільшення кількості елементів.
Швидка передобробка має стабільні
показники S оцінки у межах 0.18 – 0.25 для
усіх розмірів масиву. Передобробка із роз-
воротом має показник близький до 0, плюс
мінус 0.05.
Експертні та інтелектуальні інформаційні системи
9
Рис.6. S оцінка швидкого сортування
разом із швидкою, з пам’яттю
і передобробкою з розворотом
Однак усі досліджені типи передоб-
робок разом зі швидким сортуванням у по-
рівнянні із чистим сортуванням мають
негативні значення S оцінки. Для передоб-
робки із розворотом ці значення знахо-
дяться у діапазоні від - 0.02 до - 0.12.
Швидка показує значення у діапазоні
- 0.1..- 0.2. А для передобробки з пам’яттю
S оцінка різко знижується від -0.32, для ма-
сиву 1000 елементів, до -0.5 – на 30 тисячах.
Далі зі збільшенням розміру масиву продо-
вжується падіння показника до -0.7 на 200
тисячах елементів.
Дослідження впливу блочних пе-
редобробок. Блочні локальні передобробки
мають позитивний вплив на часову ефекти-
вність швидкого сортування. S оцінка сор-
тування після локальних передобробок
знаходиться на рівні 0.1 на малих розмірах
масиву. На масивах близько ста тисяч і бі-
льше елементів показник коливається у ме-
жах 0.1 – 0.2.
Рис.7. S оцінка швидкого сортування після
блочної локальної швидкої
та передобробки з пам’яттю
Локальні передобробки разом із шви-
дким сортуванням мають негативні значення
S оцінки. Блочна локальна швидка показує
значення близько -0.4 – -0.5 на дуже малих
розмірах масиву, а після десяти тисяч елеме-
нтів і до кінці експерименту показує зна-
чення у діапазоні -0.3..-0.4. Блочна локальна
з пам’яттю починає зі значення близько -0.39
і рівномірно погіршується впродовж усього
експерименту, досягаючи значення -0.6.
Блочні глобальні передобробки та-
кож мають позитивний вплив на швидке со-
ртування, але дещо менший, ніж локальні.
Значення S оцінки швидкої передобробки
коливається у межах -0.02 – 0.1 впродовж
усього експерименту. Передобробка з
пам’яттю показує значення від -0.03 до 0.17.
Рис.8. S оцінка швидкого сортування після
блочної глобальної швидкої та
передобробки з пам’яттю
Значення S оцінки для блочних гло-
бальних передобробок разом із сортуван-
ням є негативним. Швидка передобробка
має значення у діапазоні -0.22..-0.07. А з
пам’яттю починає з -0.6, сягає -0.9 на де-
сяти тисячах елементів, а після сімдесяти
тисяч лишається близьким до -1.
Підсумки. Швидке сортування має
складність O(n*log(n)) у кращому випадку, і
відсортованість даних у масиві перед почат-
ком сортування майже не впливає на час ви-
конання. Усі запропоновані типи перед-
обробок разом зі швидким сортуванням по-
казали довший час виконання, ніж окреме со-
ртування. Однак деякі передобробки
показали позитивний вплив на часову ефек-
тивність сортування. Передобробка з
пам’яттю досягла показника S оцінки 0.5, а
швидка передобробка – 0.25. Найкращий по-
казник серед блочних передобробок показала
глобальна передобробка з пам’яттю – до 0.17.
Решта показала значення на рівні 0.1 – 0.2.
Експертні та інтелектуальні інформаційні системи
10
Дослідження часової ефективності
сортування вставками з використанням
різних типів передобробок. Значення S оці-
нки для сортування вставками після швидкої
передобробки має позитивне значення на ма-
лих розмірах масиву. Для масиву довжиною
100 елементів оцінка дорівнює 0.3. Далі зна-
чення швидко зростає до 0.5 для масиву дов-
жиною 1000. Зі збільшенням довжини
масиву до 100000 елементів, значення S оці-
нки лишається на рівні 0.55.
Рис.9. S оцінка сортування вставками після
швидкої, з пам’яттю і передобробки
з розворотом
Сортування після передобробки з
пам’яттю має вищі показники S оцінки. Для
масива довжиною 100 елементів оцінка до-
рівнює 0.55 і стрімко зростає. На 2000 еле-
ментів значення S оцінки сягає 0.92, на
10000 – 0.97 й із подальшим збільшенням
кількості елементів наближається до 1.
Передобробка із розворотом має по-
казник S оцінки дещо вище 0 на малих роз-
мірах масиву, досягає 0 після 1000 і
залишається таким протягом усього експе-
рименту.
Рис.10. S оцінка сортування вставками
зі швидкою, з пам’яттю і передобробкою
з розворотом
Швидка передобробка показує нега-
тивне значення S оцінки на малих розмірах
масиву. Для розміру масиву в діапазоні
200..300 елементів значення близьке до 0.
Далі значення рівномірно зростає до 0.53
для масиву довжиною 10000. Подальше збі-
льшення довжини масиву не змінює зна-
чення S оцінки.
Передобробка з пам’яттю також має
негативне значення S оцінки на малих роз-
мірах масивів. Оцінка для масиву з 300 еле-
ментів досягає 0 і продовжує стрімко
зростати. На 2000 елементів значення S оці-
нки сягає 0.8, на 6000 – 0.9 і, за подальшого
збільшення кількості елементів, наближа-
ється до 1.
Передобробка із розворотом має по-
казник S оцінки дещо нижче 0 на малих ро-
змірах масиву, досягає 0 після 1000 і
залишається таким протягом усього експе-
рименту.
Дослідження впливу блочних пе-
редобробок. Сортування вставками після
обох блочних глобальних передобробок
має показник S оцінки у діапазоні від -0.04
до 0.1 на малих розмірах масивів. Із збіль-
шенням довжини масиву діапазон звужу-
ється до значень -0.009..0.03. Водночас
швидка передобробка має незначну пере-
вагу над передобробкою з пам’яттю.
Рис.11. S оцінка сортування вставками
після блочних передобробок
Блочні локальні передобробки ма-
ють більшу ефективність порівняно з гло-
бальними. Сортування після швидкої
передобробки має показник S оцінки
0.029..0.17. Із збільшенням довжини масиву
діапазон значень звужується до величин
0.127..0.145.
Експертні та інтелектуальні інформаційні системи
11
Блочна локальна передобробка з
пам’яттю на малих розмірах масиву пока-
зує більший діапазон значень S оцінки
0.128..0.285. За умови збільшення довжини
масиву діапазон звужується до значень
0.224..0.271.
Найгірші показники S оцінки пока-
зує сортування вставками після блочної
глобальної передобробки з пам’яттю. На
малих розмірах масивів значення колива-
ються у діапазоні -0.31..-0.24, для масивів
понад 50000 елементів і до кінця експери-
менту – - 0.29..- 0.28.
Блочна глобальна швидка передоб-
робка дає негативні значення S оцінки на
масивах малої довжини. Досягає 0 на маси-
вах довжиною 5000 елементів і лишається
на тому ж рівні до кінця експерименту.
Рис.12. S оцінка сортування вставками
разом із блочними передобробками
Блочні локальні передобробки пока-
зують вищий рівень значень S оцінки ніж
глобальні. Швидка передобробка має нега-
тивне значення на малих розмірах масивів.
Для масивів довжиною 15000 і до кінця екс-
перименту S оцінка лишається на рівні
0.11..0.13.
Передобробка з пам’яттю також має
негативні значення S оцінки на малих роз-
мірах масиву. На масивах довжиною понад
15000 показує значення у діапазоні
0.2..0.26.
Підсумки. Сортування вставками
має складність O(n) у кращому випадку – на
повністю відсортованому масиві. Тому пе-
редобробки разом із сортуванням мають пе-
реважно позитивні значення S оцінки. А
через те, що час передобробки дуже малий
порівняно із часом сортування, результати
S-оцінок для алгоритму сортування після і
разом з передобробкою відрізняються на
0.01 – 0.02. Передобробка з розворотом має
показники на рівні 0, швидка передобробка
– 0.53, передобробка з пам’яттю – наближа-
ється до 1 зі збільшенням розміру масиву.
Серед блочних найбільші показники у ло-
кальної передобробки з пам’яттю – 0.26, ло-
кальна швидка має – 0.13, глобальна
швидка – 0. Найнижчі показники у глобаль-
ної передобробки з пам’яттю – -0.
Дослідження часової ефективності
шейкерного сортування з використан-
ням різних типів передобробок. Шейке-
рне сортування після швидкої
передобробки має позитивне значення S
оцінки на всіх довжинах масивів з експери-
менту. На малому розмірі масиву S оцінка
дорівнює 0.54 і швидко зростає зі збільшен-
ням розміру масиву. На масивах близько
1000 елементів сягає 0.58, а вже після 7000
елементів виходить на свій постійний рі-
вень – 0.7.
Рис.13. S оцінка шейкерного сортування
після швидкої, з пам’яттю і передобробки
з розворотом
Передобробка з пам’яттю має до-
сить велике значення (0.7) S оцінки на ма-
лих розмірах масиву. Масив з 1000
елементів досягає 0.87, а після 10000 – 0.98.
Далі на всіх довжинах масивів, використа-
них в експерименті, значення S оцінки ся-
гає і перевищує 0.99.
Шейкерне сортування після передо-
бробки з розворотом на масивах довжиною
до 1000 показує значення S оцінки у діапа-
зоні -0.02..0.06. На довших масивах діапа-
зон значень звужується і лишається рівним
0.0..0.02.
Експертні та інтелектуальні інформаційні системи
12
Рис.14. S оцінка шейкерного сортування
разом із швидкою, з пам’яттю
і передобробкою з розворотом
Усі вищезгадані типи передобробок
займають мало часу порівняно з шейкер-
ним сортуванням. Тому відмінність у пока-
зниках S оцінки можна побачити на малих
розмірах масивів. Початкове значення для
швидкої передобробки для масиву довжи-
ною 100 дорівнює 0.3, а вже для 1000 дося-
гає 0.54, після 7000 елементів і до кінця
експерименту – 0.7.
Передобробка з пам’яттю має досить
мале значення 0.15 для масиву зі 100 елемен-
тів. А при довжині рівній 1000 – 0.81. На вели-
ких розмірах сягає 0.99 і наближається до 1.
Значення для передобробки з розво-
ротом знаходяться у діапазоні -0.034..0.008
для масивів довжиною до 1000 елементів.
Далі усі значення S оцінок сортування з пе-
редобробками співпадають із результатами
сортування після передобробок.
Дослідження впливу блочних пе-
редобробок. Найкращі показники S оцінки
на великих розмірах масивів показує бло-
чна локальна передобробка з пам’яттю. На
масивах до 1000 елементів значення збіль-
шуються від 0.16 до 0.29. На 10000 дорів-
нює 0.54, а на 20000 досягає 0.6 і лишається
на тому ж рівні до кінця експерименту.
Рис.15. S оцінка шейкерного сортування
після блочних передобробок
Блочна локальна швидка передобро-
бка має показники S оцінки у діапазоні
0.12..0.26 на масивах довжиною до 1000
елементів. Для масивів 1000–10000 елемен-
тів діапазон розширюється і має значення
0.26..0.34. Для більших масивів показник
лишається на рівні 0.3 протягом усього екс-
перименту.
Блочні глобальні передобробки по-
казують значно нижні результати S оці-
нки порівняно з локальними. Швидка
передобробка має значення у діапазоні
0.01..0.13 на масивах довжиною до 10000.
На довших масивах показники варію-
ються від 0.07 до 0.08.
Блочна глобальна передобробка з
пам’яттю має найнижчі показники S оці-
нки. На масивах до 10000 елементів – -
0.04..0.06, на довших масивах – -0.06..0.04.
Зі збільшенням довжини масиву наближа-
ється до нуля.
Рис.16. S оцінка шейкерного сортування
разом із блочними передобробками
Шейкерне сортування разом із блоч-
ними локальними передобробками має ни-
жчі показники S оцінок, порівняно із
сортуванням після передобробок, на малих
розмірах масивів. Для швидкої передобро-
бки на масивах довжиною менше 10000
елементів значення оцінки стрімко зроста-
ють від -0.26 до 0.19. А для передобробки з
пам’яттю – від -0.29 до 0.24. Далі протягом
усього експерименту значення S оцінок
співпадають із результатами сортування пі-
сля блочних локальних передобробок.
Блочна глобальна швидка передоб-
робка на масивах довжиною до 10000 еле-
ментів має показник S оцінки, що зростає з
-0.07 до 0.06. Для довших масивів значення
знаходяться у діапазоні 0.065..0.076.
Експертні та інтелектуальні інформаційні системи
13
Блочна глобальна передобробка з
пам’яттю має негативні показники S-
оцінки протягом усього експерименту. На
масивах довжиною до 10000 елементів зна-
чення лежать у діапазоні -0.29..-0.05, а бі-
льше 10000 – -0.06..-0.01.
Підсумки. Шейкерне сортування,
як і сортування вставками, має складність
O(n) у кращому випадку, що підтверджу-
ють високі експериментально отримані
показники S оцінки для сортування разом
із передобробками. Для швидкої передоб-
робки – 0.7, передобробки з пам’яттю –
0.99. Ефективність передобробки із розво-
ротом близька до 0. Серед блочних алго-
ритмів найбільш ефективна локальна з
пам’яттю – 0.6, локальна швидка – 0.3,
глобальна швидка – 0.08, глобальна з
пам’яттю – близька до 0.
Висновки
Встановлено, що із розмежуванням
процесів обробки та сортування можливо
отримати значне скорочення часу вико-
нання алгоритмів сортування. Більш ефек-
тивна передобробка для алгоритмів
сортування, що прискорюються з майже
відсортованими даними.
Передобробка з пам’яттю дозволяє
отримати краще впорядковані масиви да-
них, але потребує більше часу та пам’яті
порівняно зі швидкою передобробкою.
Передобробка із розворотом не погі-
ршує, але і не поліпшує в межах похибки
час сортування для усіх досліджених алго-
ритмів.
Для великих обсягів даних, більших,
ніж довжина кешу, ефективнішим може
стати використання блочних локальних або
глобальних передобробок. Через їхню осо-
бливість – не виконувати перестановки,
якщо передбачений елемент знаходиться за
межами блоку, - можна мінімізувати або зо-
всім уникнути промахів кешу (cache miss).
У випадках, коли сумарний час пе-
редобробки і сортування перевищує час
сортування, використання передобробки
видається недоцільним. Однак залежно
від архітектури і вимог до даних у про-
грамі передобробка може викликатись
один або багато разів протягом роботи
програми, за умови надходження певної
кількості нових даних. Таким чином дані
можна тримати частково відсортованими.
А за потреби у повністю відсортованих да-
них, викликати безпосередньо алгоритм
сортування, який виконається швидше че-
рез те, що дані знаходяться у «передобро-
бленому» стані.
Найбільший ефект застосування за-
пропонованих алгоритмів передобробки
виявлено під час застосування передобро-
бки з пам’яттю разом із сортуванням вста-
вками і шейкерним сортуванням. Значення
S оцінки у цих випадках наближається до
1. Також досить високу ефективність пока-
зує швидка передобробка для вищезгада-
них алгоритмів сортування. Серед
блочних передобробок локальні передоб-
робки показали більшу ефективність, ніж
глобальні.
Жодний тип передобробки не мав
позитивного впливу у використанні разом
зі швидким сортуванням. Час виконання
передобробки перевищував виграш від ско-
рочення часу сортування передоброблених
даних.
Література
1. Knuth, Donald. The Art Of Computer
Programming, vol. 3: Sorting And Searching. :
Addison-Wesley, 1973.
2. Timsort [Online] – Available from:
https://svn.python.org/projects/python/trunk/
Objects/listsort.txt, last accessed 2023/08/07.
3. Musser, David R. (1997). "Introspective
Sorting and Selection Algorithms". Software:
Practice and Experience. 27 (8): 983–993.
4. Adnan Saher Mohammed, Şahin Emrah
Amrahov, Fatih V. Çelebi. Bidirectional Con-
ditional Insertion Sort algorithm; An efficient
progress on the classical insertion sort. Future
Generation Computer Systems, Volume 71,
June 2017, 102-112.
5. Shrinu Kushagra, Alejandro López-Ortiz, Au-
rick Qiao, J. Ian Munro. Multi-Pivot Quick-
sort: Theory and Experiments. 2014
Proceedings of the Meeting on Algorithm En-
gineering and Experiments (ALENEX), 47-60
6. Шинкаренко В.І., Дорошенко А.Ю., Яце-
нко О.А., Разносілін В.В., Галанін К.К.
Двокомпонентні алгоритми сортування
Проблеми програмування. – 2022. – № 3-4.
– С. 32-41. – Бібліогр.: 18 назв. – укр.
Експертні та інтелектуальні інформаційні системи
14
7. Abbas Mubarak, Sajid Iqbal, Qaisar Rasool,
Nabeel Asghar, Neetu Faujdar, & Abdul Rauf.
(2022). Preprocessing: A method For
Reducing Time Complexity. Journal of
Computing & Biomedical Informatics, 4(01),
104–117.
8. Шинкаренко В.І Сравнительный анализ
временной эффективности функционально
эквивалентных алгоритмов / В. И. Шинка-
ренко // Проблемы программирования. –
2001. – № 3-4. – С. 31-39
9. Hoare, C. A. R. (1962). "Quicksort". Comput.
J. 5 (1): 10–16.
10. Insertion sort [Online] – Available from:
https://en.wikipedia.org/wiki/Insertion_sort,
last accessed 2023/08/07.
11. Knuth, Donald E. (1973). "Sorting by
Exchanging". Art of Computer Programming.
Vol. 3. Sorting and Searching (1st ed.).
Addison-Wesley. pp. 110–111.
12. Bubble sort [Online] – Available from:
https://en.wikipedia.org/wiki/Bubble_sort, last
accessed 2023/08/07.
Одержано: 18.10.2023
Про авторів:
Шинкаренко Віктор Іванович,
доктор технічних наук, професор,
Кількість публікацій в українських
виданнях – більше 200
Кількість зарубіжних публікацій –
більше 30
індекс Хірша – 6
https://orcid.org/0000-0001-8738-7225
E-mail: shinkarenko_vi@ua.fm
Макаров Олексій Вікторович,
аспірант,
Кількість публікацій в українських
виданнях – 1
https://orcid.org/0009-0003-0921-155X
E-mail: makarovov@hotmail.com
Місце роботи авторів:
Український державний університет
науки і технологій,
49010, Україна, Дніпро,
вул. академіка Лазаряна, 2.
E-mail: office@ust.edu.ua
|