Курсовая работа: Порівняльний аналіз ефективності та складності швидких алгоритмів сортування масивів
a : array [1..N] of basetype.
Необмежуючи загальності, зупинимося на впорядкуванні його компонентів по зростанню.
Основна умова: обраний метод сортування масивів повинен економно використовувати доступну пам’ять. Це означає, що перестановки, які приводять елементи в порядок, повинні виконуватися "на тому ж місці". Тобто методи, в яких елементи масиву a передаються в результуючий масив b , не мають практичної цінності.
Алгоритми сортування окрім критерію економії пам’яті будуть класифікуватися по швидкості, тобто по часу їх роботи. Оскільки на різних типах ЕОМ одні і ті ж методи показуватимуть відмінні результати, то в якості міри ефективності алгоритму можуть бути прийняті числа: C - кількість необхідних порівнянь ключів; M - кількість перестановок елементів. Очевидно, що ці числа є функціями від кількості елементів в масиві N . Згідно із введеними критеріями швидкодії алгоритми сортування поділяють на два типи - прямі та швидкі.
Прямі методи зручні для пояснення і розбору основних рис більшості сортувань, легко програмуються і відлагоджуються, а самі програми - короткі, що теж важливо для економії пам’яті. В основі їх лежить повторення N етапів обробки масиву із зменшенням на кожному з них кількості порівнюваних елементів. Ефективність даних алгоритмів є величиною порядку O(N 2 ). Такі методи зручно використовувати на так званих "коротких" масивах.
Швидкі методи вимагають невеликої кількості етапів обробки, однак ці етапи досить складні. На кожному з них окрім переміщення чергового елемента на "своє" місце відбувається перегрупування решти відносно цього елемента. Звичайно виграш по ефективності для таких алгоритмів отримується на "довгих" масивах.
Методи сортування "на тому ж місці" у відповідності із визначаючими їх принципами розбиваються на три основні категорії :
- сортування включенням;
- сортування вибором;
- сортування обміном.
У курсовій роботі ми детально розглянемо швидкі алгоритми сортування елементів масиву, проведемо їх порівняльний аналіз. Крім цього, розглянемо і прямі методи сортування, їх позитиви і недоліки, що дасть змогу краще визначити ефективність і складність швидких алгоритмів сортування.
Розділ І. Прямі методи сортування масивів
1.1 Сортування прямим включенням
В основі розглядуваного методу лежить пошук для чергового елемента масиву відповідного місця у відсортованій частині із наступним включенням його в знайдену позицію. Таким чином елементи масиву умовно діляться на дві групи - вже "готову" послідовність a 1 , a 2 , ..., a i та вихідну послідовність. На кожному етапі, починаючи з i=2 та збільшуючи i кожен раз на 1 , із вихідної послідовності вибирається один елемент і вставляється в потрібне місце у вже впорядковану послідовність. Очевидно, що початкова ліва послідовність буде "готовою", оскільки одноелементний масив завжди впорядкований. Цей алгоритм можна записати у вигляді послідовності команд :
for i:=2 to N do
begin
x:=a[i];
включення x на потрібне місце серед a[1], ..., a[i]
end;
Процес просіювання (пошуку потрібного місця для включення елемента x ) може припинитися при виконанні однієї із двох умов :
1) знайдено елемент a j з ключем, меншим ніж ключ у x ;
2) досягнутий лівий кінець "готової" послідовності.
Таким чином програмна реалізація методу прямого включення матиме вигляд процедури :
Procedure Straight_Insertion;
Var
i, j : integer; x : basetype;
Begin
for i:=2 to N do
begin