Висновки
Отже, ми розглянули як працюють швидкі алгоритми сортування і спробували визначити їх складність.
Застосування того чи іншого алгоритму сортування для вирішення конкретної задачі є досить складною проблемою, вирішення якої потребує не лише досконалого володіння саме цим алгоритмом, але й всебічного розглядання того чи іншого алгоритму, тобто визначення усіх його переваг і недоліків.
Звичайно, необхідність застосування саме швидких алгоритмів сортування очевидна. Адже прості алгоритми сортування не дають бажаної ефективності в роботі програми. Але завжди треба пам’ятати й про те, що кожний швидкий алгоритм сортування поряд із своїми перевагами може містити і деякі недоліки.
Так, алгоритм сортування деревом, хоча й працює однаково на всіх входах (так, що його складність в гіршому випадку співпадає зі складністю в середньому), але цей алгоритм має і досить суттєвий недолік: для нього потрібна додаткова пам’ять розміром 2n-1.
Розглядаючи такий швидкий алгоритм сортування, як пірамідальне сортування, можна зазначити, що цей алгоритм ефективніший ніж попередній, адже він сортує “на місці” , тобто він не потребує додаткових масивів. Крім того, цей алгоритм (“ з точністю до мультиплікативної константи” (4, 74)) оптимальний: його складність співпадає з нижньою оцінкою задачі, тобто за критеріями C(n) та M(n) він має складність O(n log2 n), але містить складний елемент в умові. Тобто, в умові A[left] має бути строго менше ніж x , а A[right] - строго більше за x. Якщо ж замість “строго більше” та “строго менше” поставити знаки, що позначають “більше, або дорівнює” та “менше, або дорівнює”, то індекси left і right пробіжать увесь масив і побіжать далі. Вийти з цієї ситуації можна було б шляхом ускладнення умов продовження перегляду, але це б погіршило ефективність програми.
В нашій роботі ми розглянули деякі швидкі алгоритми сортування та їх реалізацію мовою Pascal, дослідили не лише переваги таких алгоритмів, ефективність їх використання, але й визначили деякі недоліки окремих алгоритмів, що заважають вживати їх для вирішення першої ліпшої задачі сортування.
Отже, головною задачею, яку має вирішити людина, яка повинна розв’язати задачу сортування – це визначення як позитивних, так і усіх негативних характеристик різних алгоритмів сортування, передбачення кінцевого результату. До того ж , треба враховувати головне – чи , можливо, цю задачу задовольнить один з класичних простих алгоритмів сортування.

стор.24