Quicksort: статистичне порівняння часу роботи методів обчислення опорного елементу
Ключові слова:
QuickSort, опорний елемент, рандомізований вибір, детермінований вибір, сортування, аналіз алгоритмів, статистичне порівнянняАнотація
Досліджено алгоритм сортування QuickSort, який є одним із найефективніших методів сортування. У роботі зосереджено увагу на статистичному порівнянні часу роботи алгоритму в різних сценаріях вибору опорного елементу. Розглянуто найгірший, середній та найкращий випадки, а також використання рандомізованого та детермінованого підходів під час вибору опорного елементу. Виконано практичний експеримент, де порівняні реалізації алгоритму з використанням рандомізованого та детермінованого алгоритмів вибору опорного елементу.
Посилання
Roughgarden T. Algorithms Illuminated. Part 1: The Basics. Soundlikeyourself Publishing, 2017. Р. 226.
Introduction to Algorithms 3rd Edition / T. H. Cormen, C. E. Leiserson, R L. Rivest, C. Stein. MIT PRESS, 2009. 1292 p.
Hoare C. A. R. Quicksort. The Computer Journal. 1962. Vol. 5. № 1. P. 10–16. 0 100 000 200 000 300 000 400 000 500 000 600 000 700 000 800 000 900 000 1 000 000 0 150000 300000 450000 600000 750000 900000 DQS RQS
Sedgewick R. Algorithms In C: Fundamentals, Data Structures, Sorting, Searching, Parts 1–4. Addison-Wesley Professional, 1997. 752 p.
Programming Languages – C++. Standart (ISO/IEC JTC1 SC22 WG21 N4860). URL: https://isocpp.org/files/ papers/N4860.pdf (дата звернення: 20.02.2024).
Офісійний сайт Github. URL: https://github.com/shevmee/algorithms (дата звернення: 24.02.2024).
Денисюк В. О., Потапова Н. А., Зелінська О. В., Тарасюк М. Б. Програмна реалізація та дослідження алгоритмів паралельного швидкого сортування. Вісник Хмельницького національного університету. Технічні науки. 2023. № 4. С. 95–105. URL: http://journals.khnu.km.ua/vestnik/wp-content/uploads/2023/09/323-95-105.pdf (дата звернення: 01.03.2024).
