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

ЗМІСТ 

ВСПУП                                                                                                                       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²) [читається як "Об велике від эн квадрат"].