На головну

Методи сортування даних

  1. Data Information / General (Інформація про дані).
  2. I. Неекспериментальні методи
  3. II. Арени. Методи отримання.
  4. II. Основні методи збору соціологічної інформації, їх коротка характеристика.
  5. II. Перепишіть з даних пропозицій ті, дія яких відбувалася в минулому, і переведіть їх.
  6. II. експериментальні методи
  7. II. Метод ДЕРЖАВНОГО УПРАВЛІННЯ.

Існує традиційний поділ алгоритмів на чисельні і нечисельні. Чисельні алгоритми призначені для математичних розрахунків: обчислення за формулами, рішення рівнянь, статистичної обробки даних і т. П. У таких алгоритмах основним видом оброблюваних даних є числа. Нечіcленние алгоритми мають справу з найрізноманітнішими видами даних: символьної, графічної, мультимедійної інформацією. До цієї категорії відносяться багато алгоритми системного програмування (транслятори, операційні системи), систем управління базами даних, мережевого програмного забезпечення і т. Д.

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

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

Як правило, сортовані дані розташовуються в масивах. У найпростішому випадку це числові масиви. Однак для нечисельних алгоритмів більш характерна ситуація, коли сортується масив записів (в термінології Паскаля) або масив структур (в термінології Сі). Поле, за значенням якого виробляється сортування, називається ключем сортування. Зазвичай воно має числовий тип. Наприклад, масив сортируемих записів містить два поля: найменування товару та кількість товару на складі. У програмі на Паскалі він описаний так:

Сортування проводиться або по зростанню, або по спадаючій значення ключа A [i] .key.

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

Алгоритм сортування «методом бульбашки» розглядався в розділі 3.17. Тут ми обговоримо два алгоритму: сортування простим включенням і швидку сортування.

Сортування простим включенням. Припустимо, що на деякому етапі роботи алгоритму ліва частина масиву з 1-го по (i - 1) -й елемент включно

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

Процес починається з лівої частини, що складається з одного елемента А [1], а закінчується, коли права частина стає порожній.

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

Оцінимо величину мінімальної тимчасової складності алгоритму. Якщо масив вже відсортований, то тіло циклу while не виконуватиметься жодного разу. Виконання процедури зведеться до роботи наступного циклу:

Оскільки тіло циклу for виповнюється n - 1 раз, то число пересилань елементів масиву

Мmin = 2 (п - 1),

а число порівнянь ключів одно

Сmin = n - 1.

Складність алгоритму буде максимальною, якщо вихідний масив впорядкований по спадаючій. Тоді кожен елемент А [i] буде «проганяти» до початку масиву, т. Е. Встановлюватися в першу позицію. Цикл while виконається 1 раз при i = 2, 2 рази при i = 3 і т. Д., П - 1 раз при i = п. Таким чином, загальне число пересилань записів одно:

Більш підходящої для реальної ситуації є середня оцінка складності. Для її обчислення треба припустити, що всі елементи вихідного масиву - випадкові числа і їх значення ніяк не пов'язані з їх номерами. В такому випадку результат чергової перевірки умови x. key

Розумно припустити, що середня кількість виконань циклу While для кожного конкретного значення i одно i / 2, т. Е. В середньому кожен раз доводиться переглядати половину послідовності до тих пір, поки не знайдеться підходяще місце для чергового елемента

Тоді формула для середнього числа пересилань (середня оцінка складності) буде наступною:

Як максимальна, так і середня оцінка складності алгоритму квадратична (є поліномом другого ступеня) по параметру п - розміром сортованого масиву.

Алгоритм швидкого сортування. Цей алгоритм був розроблений Е. Хоаром. В алгоритмі швидкого сортування використовуються три ідеї:

- Поділ сортованого масиву на 2 частини, ліву і праву;

- Взаємне упорядкування двох частин (подмассивов) так, щоб всі елементи лівої частини не перевищували елементів правій частині;

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

Для поділу масиву на дві частини потрібно вибрати якийсь «бар'єрне» значення ключа. Це значення має задовольняти єдиному умові: лежати в діапазоні значень для даного масиву (т. Е. Між мінімальною і максимальною величиною). За «бар'єр» можна вибрати значення ключа будь-якого елементу масиву, наприклад першого, або останнього, або знаходиться в середині.

Далі потрібно зробити так, щоб в лівому підмасиві виявилися всі елементи з ключем, меншим бар'єру, а в правому - з великим: Потім, переглядаючи масив зліва направо, необхідно знайти позицію першого елемента з ключем, великим бар'єру, а переглядаючи справа наліво - знайти перший елемент з ключем, меншим бар'єру. Слід змінити ці значення, потім продовжити зустрічний рух до наступної пари елементів, призначених для обміну. Необхідно повторювати цю процедуру, поки індекси лівого і правого переглядів не співпадуть. Місце збіги стане кордоном між двома взаємно впорядкованими подмассіви. Далі алгоритм рекурсивно застосовується до кожного з подмассивов (лівому і правому). В кінцевому рахунку приходимо до сукупності з п взаємно упорядкованих одноелементні масивів, які ділити далі неможливо. Ця сукупність утворює один повністю упорядкований масив. Сортування завершена!

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

т (п) = 0 (n 1n (n)).

Тут використано прийняте в математиці позначення: O (х) позначає величину порядку х. Отже, тимчасова складність алгоритму швидкого сортування є величина порядку п 1n (n). Ця величина для цілих позитивних п менше, ніж п2 (згадаємо, що алгоритм сортування простим включенням має складність порядку n2). І чим більше значення п, тим ця різниця істотніше. наприклад:


 



складність алгоритмів | Додаток 2. Турбо Паскаль. модуль GRAPH

ОСНОВИ ПРОГРАМУВАННЯ | Вступ | Алгоритми і величини | Основою програмістської грамотності є розвинене алгоритмічне мислення. | Лінійні обчислювальні алгоритми | Розгалуження і цикли в обчислювальних алгоритмах | Допоміжні алгоритми і процедури | Історія і класифікація мов програмування | Структура і способи опису мов програмування високого рівня | Перше знайомство з Паскалем |

© um.co.ua - учбові матеріали та реферати