Data Stochastic Preprocessing for Sorting Algorithms
Loading...
Date
2022
Journal Title
Journal ISSN
Volume Title
Publisher
CEUR Workshop Proceedings
Abstract
ENG: The possibilities of improving sorting time parameters through preprocessing by stochastic sorting were investigated. The hypothesis that preprocessing by stochastic sorting can significantly improve the time efficiency of classical sorting algorithms has been 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 exchange efficiency of two elements and a series of comparisons with exchanges are proposed, which made it possible to establish the greatest efficiency of data preprocessing by stochastic sorting when one element for comparison is selected 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 about increasing the time efficiency of quick sorting combined with sorting by insertions on the final sections due to the use of preliminary stochastic processing of such sections has not been confirmed. However, according to the experiment, the recommended size of the array was established, at which it is necessary to switch to insert sorting in the modified quick sort. 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.
UKR: У роботі досліджувалися можливості покращення часових параметрів сортувань за допомогою попередньої обробки стохастичним сортуванням. Експериментально підтверджено гіпотезу про можливість суттєвого поліпшення часової ефективності двокомпонентного сортування стохастичне + класичне порівняно з таким же класичним однокомпонентним. У якості класичного прийняті сортування різної обчислювальної складності: шейкерне, з обчислювальною складністю O(n2), вставками O(n2), Шелла O(n·(log n)2) ... O(n3/2), швидке з оптимізацією кінцевих ділянок O(n·log n). Найбільший ефект досягається при виконанні порівнянь стохастичним сортуванням у обсязі 160 % від обсягу масиву. Введені показники ефективності обміну двох елементів та серії порівнянь з обмінами дозволили встановити найбільшу ефективність стохастичного сортування у якості першого компонента двокомпонентного сортування коли один елемент для порівняння обирається з першої частини масиву, а інший – з другої. Покращення часової ефективності досягало 70–80 % для алгоритмів з обчислювальною складністю O(n2). Однак, для сортування Шелла та швидкого попереднє стохастичне сортування не має позитивного ефекту, а навпаки збільшує загальний час сортування, що, вочевидь, пояснюється початковою високою ефективністю даних методів сортування. Гіпотеза про підвищення часової ефективності сортування при трикомпонентному сортуванні швидке + стохастичне + вставками не підтвердилася. Однак, в ході експерименту встановлено рекомендований розмір масиву, при якому в двокомпонентному сортуванні швидке + вставками необхідно переходити до другої компоненти – сортуванню вставками. Оптимальна довжина кінцевої ділянки лежить у діапазоні від 60 до 80 елементів. Враховуючи те, що часова ефективність алгоритмів залежить від архітектури комп’ютера, операційної системи, програмного середовища розробки та виконання програми, типів даних, обсягів даних та їх значень показники часової ефективності слід уточнювати у кожному конкретному випадку.
UKR: У роботі досліджувалися можливості покращення часових параметрів сортувань за допомогою попередньої обробки стохастичним сортуванням. Експериментально підтверджено гіпотезу про можливість суттєвого поліпшення часової ефективності двокомпонентного сортування стохастичне + класичне порівняно з таким же класичним однокомпонентним. У якості класичного прийняті сортування різної обчислювальної складності: шейкерне, з обчислювальною складністю O(n2), вставками O(n2), Шелла O(n·(log n)2) ... O(n3/2), швидке з оптимізацією кінцевих ділянок O(n·log n). Найбільший ефект досягається при виконанні порівнянь стохастичним сортуванням у обсязі 160 % від обсягу масиву. Введені показники ефективності обміну двох елементів та серії порівнянь з обмінами дозволили встановити найбільшу ефективність стохастичного сортування у якості першого компонента двокомпонентного сортування коли один елемент для порівняння обирається з першої частини масиву, а інший – з другої. Покращення часової ефективності досягало 70–80 % для алгоритмів з обчислювальною складністю O(n2). Однак, для сортування Шелла та швидкого попереднє стохастичне сортування не має позитивного ефекту, а навпаки збільшує загальний час сортування, що, вочевидь, пояснюється початковою високою ефективністю даних методів сортування. Гіпотеза про підвищення часової ефективності сортування при трикомпонентному сортуванні швидке + стохастичне + вставками не підтвердилася. Однак, в ході експерименту встановлено рекомендований розмір масиву, при якому в двокомпонентному сортуванні швидке + вставками необхідно переходити до другої компоненти – сортуванню вставками. Оптимальна довжина кінцевої ділянки лежить у діапазоні від 60 до 80 елементів. Враховуючи те, що часова ефективність алгоритмів залежить від архітектури комп’ютера, операційної системи, програмного середовища розробки та виконання програми, типів даних, обсягів даних та їх значень показники часової ефективності слід уточнювати у кожному конкретному випадку.
Description
V. Shynkarenko: ORCID 0000-0001-8738-7225;
A. Doroshenko: ORCID 0000-0002-8435-1451;
O. Yatsenko ORCID 0000-0002-4700-6704;
V. Raznosilin ORCID 0000-0002-4463-4588;
K. Halanin ORCID 0000-0001-9296-4808
Keywords
sorting, stochastic sorting, algorithm, time efficiency, experiment, сортування, стохастичне сортування, алгоритм, часова ефективність, експеримент, КІТ
Citation
Shynkarenko V. I., Doroshenko A. Y., Yatsenko O. A., Raznosilin V. V., Halanin K. K. Data Stochastic Preprocessing for Sorting Algorithms. CEUR Workshop Proceedings. 2022. Vol. 3501 : 13th International Scientific and Practical Programming Conference, UkrPROG 2022, Kyiv, 11–12 October 2022. – P. 29–38.