Анализ методов сортировки одномерного массива

      Це - верхня оцінка, тобто кількість  операцій(а виходить, і час роботи) росте не швидше, ніж квадрат кількості  елементів. Щоб відчути, що це таке, подивитеся на таблицю, де приведені  числа, що ілюструють швидкість росту  для декількох різних функцій.

      Якщо  вважати, що числа в таблиці відповідають мікросекундам, то для задачі з n=1048576 елементами алгоритмові з часом роботи O(log n) буде потрібно 20 мікросекунд, алгоритмові згодом O(n) - 17 хвилин, а алгоритмові з часом роботи O( n2 ) - більш 12 днів... Тепер перевага алгоритму 2 з оцінкою O(n) перед алгоритмом 1 досить переконлива.

      Найкращою є оцінка O(1)... У цьому випадку  час узагалі не залежить від n, тобто  постійно при будь-якій кількості  елементів.

      Таким чином, O() - "урізана" оцінка часу роботи алгоритму, що найчастіше набагато простіше одержати, чим точну формулу для кількості операцій.

      Отже, сформулюємо два правила формування оцінки O().

      При оцінці за функцію береться кількість  операцій, що зростає швидше всього, тобто, якщо в програмі одна функція, наприклад, множення, виконується O(n) раз, а додавання - O(n²) раз, те загальна складність програми - O(n²), тому що зрештою при збільшенні n більш швидкі ( у визначене, константне число раз ) додавання стануть виконаються настільки часто, що будуть впливати на швидкодію куди більше, ніж повільні, але рідкі множення. Символ O() показує винятково асимптотику!

      При оцінці O() константи не враховуються. Нехай один алгоритм робить 2500n + 1000 операцій, а іншої - 2n+1. Обоє вони мають  оцінку O(n), тому що їхній час виконання  росте лінійно.

      Зокрема, якщо обидва алгоритми, наприклад, O( n*log n ), те це аж ніяк не виходить, що вони однаково ефективні. Перший може бути, скажемо, у 1000 разів ефективніше. O() значить  лише те, що їхній час зростає  приблизно як функція n*log n.

      Інший наслідок опускання константи - алгоритм згодом O(n²) може працювати значно швидше алгоритму O(n) при малих n... За рахунок того, що реальна кількість операцій першого алгоритму може бути n² + 10n + 6, а другого - 1000000n + 5. Утім, другий алгоритм рано або пізно обжене перший... n² росте куди швидше 1000000n.

      Основа  логарифма усередині символу O() не пишеться. Причина цього досить проста. Нехай у нас є O( log₂n). Але log₂n=log₃n/log₃2, а log₃2, як і будь-яку константу, асимптотика - символ О() не враховує. Таким чином, O( log₂n) = O( log₃n).

      До  будь-якої підстави ми можемо перейти  аналогічно, а відповідно і писати його не має сенсу.

      Математичне тлумачення символу O().

      Визначення: 
O(g) - безліч функцій f, для яких існують такі константи C і N, що |f(x)| <= C|g(x)| для всіх x>N. 
Запис f = O(g) дослівно позначає, що f належить безлічі O(g). При цьому зворотне вираження O(g) = f не має змісту.

      Зокрема, можна сказати, що f(n) = 50n належить O(n²). Тут ми маємо справу з неточною оцінкою. Зрозуміло, f(n) <= 50n² при n>1, однак більш сильним твердженням було б f(n) = O(n), тому що для C=50 і N=1 вірно f(n) <= Cn, n>N.

      Інші  види оцінок.

      Поряд з оцінкою O(n) використовується оцінка Ώ(n) [читається як "Омега більше від эн"]. Вона позначає нижню оцінку росту функції. Наприклад, нехай кількість операцій алгоритму описує функція f(n) = Ώ(n²). Це значить, що навіть у самому вдалому випадку буде зроблено не менш порядку n² дій.  
...У той час як оцінка f(n) = O(n³) гарантує, що в самому гіршому випадку дій буде порядку n³, не більше.

      Також використовується оцінка Θ(n) ["Тэта від эн"], що є гібридом O() і Ώ(). 
Та (n²) є і верхньою і нижньої асимптотической оцінкою одночасно - завжди буде виконуватися порядку n² операцій. Оцінка Θ() існує тільки тоді, коли O() і Ώ() збігаються і дорівнює їм.

      Як  правило, основна увага все-таки звертається на верхню оцінку O(), тому, незважаючи на "поліпшення", алгоритм 2 залишається переважніше.

      Отже, O() - асимптотическая оцінка алгоритму  на гірших вхідних даних, Ώ() - на кращих вхідних даних, Θ() - скорочений запис однакових O() і Ώ().

      1.3 Класифікація алгоритмів сортування

      Стабільність (stability) — стійке сортування не міняє  взаємного розташування рівних елементів.

      Природність поводження — ефективність методу при обробці вже упорядкованих, або частково упорядкованих даних. Алгоритм поводиться природно, якщо враховує цю характеристику вхідної послідовності і працює краще.

Для значної  кількості алгоритмів середній і  найгірший час впорядкування n-елементного  масиву є  , це пов'язано з тим, що в них передбачені перестановки елементів, що стоять поряд (різниця між індексами елементів не перевищує деякого заданого числа). Такі алгоритми зазвичай є стабільними, хоча і не ефективними для великих масивів.

      Інший клас алгоритмів здійснює впорядкування  за час  . В цих алгоритмах використовується можливість обміну елементів, що знаходяться на будь-якій відстані один від одного.

      Ці  швидкі алгоритми використовуються в реальних задачах. Проте більшість  з них нестабільні. Стабільні  алгоритми, що працюють за час  , потребують додаткової пам'яті.

      Відомий стабільний алгоритм сортування, що не вимагає додаткової пам’яті, працює за час

      Ще  один клас алгоритмів використовує в  своїй роботі деяку додаткову  інформацію про елементи, що впорядковуються (наприклад, те що вони є різними числами в деякому діапазоні). Завдяки цьому, вони працюють за час .

      Ще  одною важливою властивістю алгоритму  є його сфера застосування. Тут  основних типів упорядкування два:

      Внутрішнє сортування оперує з масивами, що цілком поміщаються в оперативній пам'яті  з довільним доступом до будь-якого  осередку. Дані зазвичай упорядковуються на тому ж місці, без додаткових витрат.У сучасних архитектурах персональних комп'ютерів широко застосовується подкачка і кэширование пам'яті. Алгоритм сортування повинен добре поєднуватися із вживаними алгоритмами кешування і підкачування.

      Зовнішнє сортування оперує з пристроями великого об'єму, що запам'ятовують, але з доступом не довільним, а послідовним (впорядкування файлів), тобто в даний момент ми 'бачимо' тільки один елемент, а витрати на перемотування в порівнянні з пам'яттю невиправдано великі. Це накладає деякі додаткові обмеження на алгоритм і приводить до спеціальних методів упорядкування, що звичайно використовує додатковий дисковий простір. Крім того, доступ до даних на носієві проводиться набагато повільніше, ніж операції з оперативною пам'яттю.  Доступ до носія здійснюється послідовним образом: у кожен момент часу можна вважати або записати тільки елемент, що випливає за поточним. Обсяг даних не дозволяє їм розміститися в ОЗУ.

      Також алгоритми класифікуються по:

1. потреби в додатковій пам'яті або її відсутності
2. потреби в знаннях про структуру даних, що виходять за рамки операції порівняння, або відсутності таких

Відомі  алгоритми сортування:

За час 

• сортування вибором
• сортування включенням
• сортування обміном

За час 

• пірамідальне сортування
• швидке сортування
• сортування злиттям

За час  з використанням додаткової інформації про елементи

• сортування підрахунком
• сортування за розрядами
• сортування комірками

За час 

• сортування злиттям модифіковане
• сортування Шелла

 

      1.4 Постановка задачі сортування і методи її рішення. 

      Задачу  сортування даних можна сформулювати для інформаційної сукупності всілякої природи - для числової інформації, для слів і символів тексту. Для  цього, потрібно визначити поняття  порядку для елементів масиву, визначити поняття "більше" і "менше" для кожної пари елементів. Відсортувати послідовність чисел можна точно таким же способом, як і послідовність рядків тексту. Необхідно тільки визначити який з елементів пари "більше" іншого.

      Більш важливим для вибору алгоритму є  місце розташування даних - в оперативній пам'яті комп'ютера або на зовнішньому пристрої.

      Тут відіграє роль розходження в основних критеріях якості - для даних в  оперативній пам'яті основними  позитивними властивостями методу є швидкодія і потреби в  додатковій пам'яті. Для дискових файлів дуже важливим показником є кількість звертань до пристрою для виконання операцій уведення-висновку - воно повиннео бути мінімальним.

      Традиційно  розрізняють внутрішнє сортування, у якій передбачається, що дані знаходяться  в оперативній пам'яті, і важливо оптимизировать число дій програми (для методів, заснованих на порівнянні, число порівнянь, обмінів елементів і ін.), і зовнішню, у якій дані зберігаються на зовнішньому пристрої з повільним доступом (магнітні стрічка, барабан, диск, флешка) і насамперед треба знизити число звертань до цьому пристрою.

      У цій роботі розглянемо алгоритми  внутрішнього сортування масивів елементів, тому що вони більш важливі більшості  програмістів у повсякденній практиці.

      Варто помітити, що алгоритм сортування злиттям зручно застосовувати і при сортуванні зовнішніх даних. При цьому мова буде йти про злиття файлів.

      Сформулюємо постановку задачі сортування даних  для внутрішнього сортування одномірного  числового масиву по зростанню.

      Мається одномірний масив чисел, що складає з n елементів: X[n]. Переставити елементи масиву так, щоб їхні значення розташовувалися в порядку зростання. Іншими словами, для будь-якої пари елементів X[і] і X[і+1] виконується нерівність виду:

      X[і] <= X[і+1].

      У цій задачі однозначно визначається структура даних для внутрішнього сортування (одномірний масив) і порядок упорядкування елементів. Ключем для визначення порядку елементів є саме числове значення елемента масиву. Результатом рішення задачі повинна бути програма сортування масиву одним або декількома методами.

      При розробці програми можна скористатися різними алгоритмами. Найбільш відомими є наступні:

      - метод сортування обмінами ("бульбашкове"  сортування);

      - метод сортування включенням;

      - метод сортування вибором елемента;

      - метод поділу (алгоритм "швидкої" сортування метод Хоара);

      - метод Шелла;

      - метод злиття. 

      1.5 Сортування бульбашковим методом 

      Найбільш  відомим (і найбільше "безславним") є сортування бульбашковим методом. Його популярність пояснюється назвою, що запам'ятовується, і простотою алгоритму. Однак, це сортування є одним із самих гірших серед усіх коли-небудь, придуманих сортувань.

      Сортування  бульбашковим методом використовує метод обмінного сортування. Вон  заснован на виконанні в циклі  операцій порівняння і при необхідності обміну сусідніх елементів. Його назва відбувається через подобу процесові руху бульбашок у резервуарі з водою, коли кожна бульбашка знаходить свій власний рівень. Нижче показана найпростіша форма програми сортування бульбашковим методом:

      { сортування бульбашковим методом}