Двохкомпонентні алгоритми сортування
Loading...
Date
2022
Journal Title
Journal ISSN
Volume Title
Publisher
Інститут програмних систем НАН України
Abstract
UKR: У роботі досліджувалися можливості покращення часових параметрів сортувань за допомогою попередньої обробки стохастичним сортуванням. Експериментально підтверджено гіпотезу про можливість суттєвого поліпшення часової ефективності двокомпонентного сортування стохастичне + класичне порівняно з таким же класичним однокомпонентним. У якості класичного прийняті сортування різної обчислювальної складності: шейкерне, з обчислювальною складністю O(n2), вставками O(n2), Шелла O(n·(log n)2) ... O(n3/2), швидке з оптимізацією кінцевих ділянок O(n·log n). Найбільший ефект досягається при виконанні порівнянь стохастичним сортуванням у обсязі 160 % від обсягу масиву. Введені показники ефективності обміну двох елементів та серії порівнянь з обмінами дозволили встановити найбільшу ефективність стохастичного сортування у якості першого компонента двокомпонентного сортування коли один елемент для порівняння обирається з першої частини масиву, а інший – з другої. Покращення часової ефективності досягало 70–80 % для алгоритмів з обчислювальною складністю O(n2). Однак, для сортування Шелла та швидкого попереднє стохастичне сортування не має позитивного ефекту, а навпаки збільшує загальний час сортування, що, вочевидь, пояснюється початковою високою ефективністю даних методів сортування. Гіпотеза про підвищення часової ефективності сортування при трикомпонентному сортуванні швидке + стохастичне + вставками не підтвердилася. Однак, в ході експерименту встановлено рекомендований розмір масиву, при якому в двокомпонентному сортуванні швидке + вставками необхідно переходити до другої компоненти – сортуванню вставками. Оптимальна довжина кінцевої ділянки лежить у діапазоні від 60 до 80 елементів. Враховуючи те, що часова ефективність алгоритмів залежить від архітектури комп’ютера, операційної системи, програмного середовища розробки та виконання програми, типів даних, обсягів даних та їх значень показники часової ефективності слід уточнювати у кожному конкретному випадку.
ENG: The possibilities of improving sorting time parameters through preprocessing by stochastic sorting were investigated. The hypothesis that two-component stochastic + classical sorting outperforms classic one-component sorting in terms of time efficiency was experimentally confirmed. Sorting with different computational complexity is accepted as classical sorting algorithms: shaker sorting with computational complexity O(n2), insertions O(n2), Shell O(n·(log n)2) ... O(n3/2), fast with optimization of ending sequences O(n·log n). The greatest effect is obtained when performing comparisons using stochastic sorting in the amount of 160 percent of the array’s size. Indicators of the efficiency of the exchange of two elements, as well as series of exchanges, are introduced. This allowed to determine the highest efficiency of stochastic sorting (as the first component of two-component sorting), when one element for comparison is chosen from the first part of the array and the other from the second. For algorithms with a computational complexity of O(n2) the improvement in time efficiency reached 70–80 percent. However, for Shell sort and quick sort, the stochastic presort has no positive effect, but instead increases the total sorting time, which is apparently due to the initial high efficiency of these sorting methods. The hypothesis that three-component sorting fast + stochastic + insertions would increase sorting time efficiency was not confirmed. However, during the experiment, the recommended size of the array was determined, at which point the two-component quick + insertion sort must be switched to the second component – insertion sorting. The optimal length of the ending sequences is between 60 and 80 elements. Given that algorithm time efficiency is affected by computer architecture, operating system, software development and execution environment, data types, data sizes, and their values, time efficiency indicators should be specified in each specific case.
ENG: The possibilities of improving sorting time parameters through preprocessing by stochastic sorting were investigated. The hypothesis that two-component stochastic + classical sorting outperforms classic one-component sorting in terms of time efficiency was experimentally confirmed. Sorting with different computational complexity is accepted as classical sorting algorithms: shaker sorting with computational complexity O(n2), insertions O(n2), Shell O(n·(log n)2) ... O(n3/2), fast with optimization of ending sequences O(n·log n). The greatest effect is obtained when performing comparisons using stochastic sorting in the amount of 160 percent of the array’s size. Indicators of the efficiency of the exchange of two elements, as well as series of exchanges, are introduced. This allowed to determine the highest efficiency of stochastic sorting (as the first component of two-component sorting), when one element for comparison is chosen from the first part of the array and the other from the second. For algorithms with a computational complexity of O(n2) the improvement in time efficiency reached 70–80 percent. However, for Shell sort and quick sort, the stochastic presort has no positive effect, but instead increases the total sorting time, which is apparently due to the initial high efficiency of these sorting methods. The hypothesis that three-component sorting fast + stochastic + insertions would increase sorting time efficiency was not confirmed. However, during the experiment, the recommended size of the array was determined, at which point the two-component quick + insertion sort must be switched to the second component – insertion sorting. The optimal length of the ending sequences is between 60 and 80 elements. Given that algorithm time efficiency is affected by computer architecture, operating system, software development and execution environment, data types, data sizes, and their values, time efficiency indicators should be specified in each specific case.
Description
В. Шинкаренко: ORCID 0000-0001-8738-7225;
А. Дорошенко: ORCID 0000-0002-8435-1451;
О. Яценко: ORCID 0000-0002-4700-6704;
В. Разносілін: ORCID 0000-0002-4463-4588;
К. Галанін: ORCID 0000-0001-9296-4808
Keywords
сортування, стохастичне сортування, алгоритм, часова ефективність, експеримент, sorting, stochastic sorting, algorithm, time efficiency, experiment, КІТ
Citation
Шинкаренко В. І., Дорошенко А. Ю., Яценко О. А., Разносілін В. В., Галанін К. К. Двохкомпонентні алгоритми сортування. Проблеми програмування. 2022. № 3–4. С. 32–41. DOI: 10.15407/pp2022.03-04.032.