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

• Дата: 2022
• Автори: Шинкаренко, В.І., Дорошенко, А.Ю., Яценко, О.А., Разносілін, В.В., Галанін, К.К.
• Формат: Стаття
• Мова: Ukrainian
• Опубліковано: Інститут програмних систем НАН України 2022
• Назва видання: Проблеми програмування
• Теми: Теоретичні і методологічні основи програмування
• Онлайн доступ: http://dspace.nbuv.gov.ua/handle/123456789/188626
• Назва журналу: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Цитувати: Двохкомпонентні алгоритми сортування / В.І. Шинкаренко, А.Ю. Дорошенко, О.А. Яценко, В.В. Разносілін, К.К. Галанін // Проблеми програмування. — 2022. — № 3-4. — С. 32-41. — Бібліогр.: 18 назв. — укр.

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