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

ЗМІСТ 

ВСПУП                                                                                                                       2

1. ТЕОРЕТИКО-МЕТОДОЛОГИЧЕСКИЕ  АСПЕКТЫ ПРОБЛЕМЫ  МЕТОДОВ СОРТИРОВКИ  ДАННЫХ В ЯЗЫКЕ  PASCAL

1.1 Поняття сортування

1.2 Критерії оцінки алгоритмів сортування

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

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

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

1.6 Сортування вибором  елемента

1.7 Сортування включенням

1.8 Сортування злиттям

1.9 Удосконалені алгоритми сортування. Сортування Шелла

1.10 Метод поділу (алгоритм "швидкого" сортування, метод  Хоара)

1.11 Порівняльний аналіз  методів сортування 

ВИСНОВОК

СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ 
ВСТУП 

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

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

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

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

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

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

     Задача  сортування в програмуванні не вирішена повністю. Адже, хоча й існує велика кількість алгоритмів сортування, все  ж таки метою програмування є  не лише розробка алгоритмів сортування елементів, але й розробка саме ефективних алгоритмів сортування. Ми знаємо, що одну й ту саму задачу можна вирішити за допомогою різних алгоритмів і кожен раз зміна алгоритму приводить до нових, більш або менш ефективних розв’язків задачі. Основними вимогами до ефективності алгоритмів сортування є перш за все ефективність за часом та економне використання пам’яті.

        У даній  роботі  мова буде  йти  про ефективність різних  методів сортування даних   у мові Pascal.

      Об'єкт  і предмет дослідження – методи сортування даних, використовувані  в мові Pascal.

      Метою даного дослідження є аналіз  ефективності різних методів сортування даних у мові Pascal.

      Взагалі , методи сортування поділяються на три типи:

1. методи сортування, що сортують без використання додаткової пам'яті, за винятком, можливо, невеликого стека і/або масиву;
2. методи, що використовують для сортування зв'язані списки і тому використовують N додаткових покажчиків збережених у пам'яті;
3. і методи, що мають потребу в додатковій пам'яті для збереження копії сортуемого файлу.

      Мною  були розглянуті переваги і недоліки таких методів сортування, як метод  обміну, включення, вибору, злиття, методи Шелла і Хоара.

      Основними критеріями ефективності алгоритмів сортування мною був обраний час його роботи й ощадливе використання пам'яті.

      І перші три алгоритми, що ми розглянемо, для сортування N елементів мають  час роботи пропорційний N², у той час як більш складні алгоритми використовують час пропорційне N log N.

      Крім  часу й обсягу пам'яті, критерії ефективності розглянутих у роботі алгоритмів можуть включати наступні параметри:

1. кількість кроків алгоритму, необхідних для упорядкування;
2. кількість порівнянь елементів;
3. кількість перестановок, виконуваних при сортуванні.

      Зрозуміло, що, чим вище показник, тим «гірше» алгоритм сортування.

      РОЗДІЛ 1. ТЕОРЕТИКО-МЕТОДОЛОГІЧНІ АСПЕКТИ ПРОБЛЕМИ методів сортування даних у мові Pascal 

      1.1 Поняття сортування

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

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

      Сортування - це процес упорядкування деякої безлічі елементів, на якому визначені відносини порядку >, <, ³ , £ . Коли говорять про сортування, мають на увазі упорядкування безлічі елементів по зростанню або убуванню. Розглянемо різні алгоритми сортування і з'ясуємо, чому виникла необхідність появи такого великого числа алгоритмів рішення однієї і тієї ж задачі.

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

      Сортування  даних використовується для ефективного  рішення інших задач при програмуванні. Для упорядкованої сукупності даних швидко і легко вирішується задача, як пошук і добір інформації з заданої умови.

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

      1.2 Критерії оцінки алгоритмів сортування 

      Для кожного методу сортування мається  багато алгоритмів. Кожен алгоритм має свої переваги, але в цілому оцінка алгоритму сортування залежить від відповідей, що будуть отримані на наступні питання:

      1) з якою середньою швидкістю  цей алгоритм сортує інформацію?;

      2) яка швидкість для кращого  випадку і для гіршого випадку?;

      3) поводження алгоритму є природним  або є не природним?;

      4) чи виконується перестановка елементів для однакових ключів?

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

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

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

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

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

      Далі  будуть представлені характерні для  кожної групи алгоритми сортування з аналізом ефективності. Після них будуть продемонстровані більш досконаліші методи сортування.

        Оцінки часу виконання. Символ O().

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

      Розглянемо  алгоритм обчислення значення багаточлена  ступеня n у заданій крапці x. 
Pn(x) = anxn + an-1xn-1 + ... + aixi + ... + a1x1 + a0

      Алгоритм 1 - для кожного доданка, крім a0 звести x у заданий ступінь послідовним множенням і потім домножить на коефіцієнт. Потім доданки скласти.

      Обчислення i-го доданка(i=1..n) вимагає і множень.  Отже, усього 1 + 2 + 3 + ... + n = n(n+1)/2 множень. Крім того, потрібно n+1 додаваннь. Усього n(n+1)/2 + n + 1= n2/2 + 3n/2 + 1 операцій.

      Алгоритм 2 - винесемо x-и за дужки і перепишемо багаточлен у вигляді 
Pn(x) = a0 + x(a1 + x(a2 + ... ( ai + .. x(an-1 + anx))).

      Наприклад, 
P3(x) = a3x3 + a2x2 + a1x1 + a0 = a0 + x(a1 + x(a2 + a3x))

      Будемо  обчислювати вираз зсередини. Сама внутрішня дужка вимагає 1 множення і 1 додавання. Її значення використовується для наступної дужки... І так, 1 множення і 1 додавання на кожну дужку, яких.. n-1 штука. І ще після обчислення самої зовнішньої дужки помножити на x і додати a0. Усього n множень + n додавань = 2n операцій.

      Найчастіше  така докладна оцінка не потрібно. Замість  неї приводять лише асимптотичну швидкість зростання кількості  операцій при збільшенні n.

      Функція f(n) = n²/2 + 3n/2 + 1 зростає приблизно як n²/2 (відкидаємо порівняно повільно зростаючий доданок 3n/2+1). Константний множник 1/2 також забираємо й одержуємо асимптотическую оцінку для алгоритму 1, що позначається спеціальним символом O(n²) [читається як "Об велике від эн квадрат"].

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

      Якщо  вважати, що числа в таблиці відповідають мікросекундам, то для задачі з 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 Сортування бульбашковим методом 

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

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

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