Двохкомпонентні алгоритми сортування

Abstract

У роботі досліджувалися можливості покращення часових параметрів сортувань за допомогою попередньої обробки стохастичним сортуванням. Експериментально підтверджено гіпотезу про можливість суттєвого поліпшення часової ефективності двокомпонентного сортування стохастичне + класичне порівняно з таким же класичним однокомпонентним. За класичне прийняті сортування різної обчислювальної складності: шейкерне, з обчислювальною складністю O(n²), вставками O(n²), Шелла O(n•(log n)²) ... O(n³/²), а також швидке з оптимізацією кінцевих ділянок O(n•log n). Найбільший ефект досягається при виконанні порівнянь стохастичним сортуванням в обсязі 160 % від обсягу масиву. Введені показники ефективності обміну двох елементів та серії порівнянь з обмінами дозволили встановити найбільшу ефективність стохастичного сортування як першого компонента двокомпонентного сортування, коли один елемент для порівняння обирається з першої частини масиву, а інший – з другої. Покращення часової ефективності досягало 70–80 % для алгоритмів з обчислювальною складністю O(n²). Однак, для сортування Шелла та швидкого попереднє стохастичне сортування не має позитивного ефекту, а навпаки збільшує загальний час сортування, що, вочевидь, пояснюється початковою високою ефективністю даних методів сортування. Гіпотеза про підвищення часової ефективності сортування при трикомпонентному сортуванні швидке + стохастичне + вставками не підтвердилася. Однак, під час експерименту встановлено рекомендований розмір масиву, за якого в двокомпонентному сортуванні швидке + вставками необхідно переходити до другої компоненти – сортуванню вставками. Оптимальна довжина кінцевої ділянки лежить у діапазоні від 60 до 80 елементів. Враховуючи те, що часова ефективність алгоритмів залежить від архітектури комп’ютера, операційної системи, програмного середовища розробки та виконання програми, типів даних, обсягів даних та їхніх значень показники часової ефективності слід уточнювати у кожному конкретному випадку.

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(n²), insertions O(n²), Shell O(n•(log n)²) ... O(n³/²), 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(n²) 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.