Теорія алгоритмів і структури даних. Лабораторна робота з Алгоритмізація і програмування. Робота № 518366

Перехід до торгівельного партнера Binance

Теорія алгоритмів і структури даних

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

ІКНІ

Факультет:

КН

Кафедра:

Кафедра САПР

Інформація про роботу

Рік:

2010

Тип роботи:

Лабораторна робота

Предмет:

Алгоритмізація і програмування

Варіант:

Завантажити

Частина тексту файла (без зображень, графіків і формул):

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ Національний університет “Львівська політехніка” Кафедра САПР / Звіт до лабораторної роботи № 10 на тему: Теорія алгоритмів і структури даних ЛЬВІВ – 2010 1. МЕТА РОБОТИ Метою роботи є вивчення алгоритмів сортування. 2. КОРОТКІ ТЕОРЕТИЧНI ВIДОМОСТI Сортуванням називають впорядковування по ключах (тобто за якою-небудь ознакою) елементів деякої структури даних на якій визначено відношення порядку. У залежності від того, чи знаходяться елементи структур даних у внутрішній (оперативній) пам’яті або у зовнішній пам’яті (на зовнішніх пристроях), розрізняють внутрішнє та зовнішнє сортування. Нехай існують послідовність a0, a1... an і функція порівняння, яка на будь-яких двох елементах послідовності приймає одне з трьох значень: менше, більше або дорівнює. Задача сортування полягає у перестановці елементів послідовності так,щоб виконувалася умова: ai <= ai+1, для всіх i від 0 до n. Можлива ситуація, коли елементи складаються з декількох полів (рис.4): struct element { field x; field y; } Якщо значення функції порівняння залежить тільки від поля x, то x називають ключем, по якому проводиться сортування. На практиці, в якості x часто виступає число, а поле у зберігає будь-які дані, жодним чином не впливаючи на роботу алгоритму. Мабуть, жодна інша проблема не породила такої кількості найрізноманітніших рішень, як задача сортування. Чи існує певний "універсальний, найкращий алгоритм"? Маючи приблизні характеристики вхідних даних, можна підібрати метод, який працює оптимальним чином. Для того, щоб обґрунтовано зробити такий вибір, розглянемо параметри, по яких проводититься оцінка алгоритмів. 1. Час сортування - основний параметр, що характеризує швидкодію алгоритму. 2. Пам’ять - ряд алгоритмів вимагає виділення додаткової пам’яті під тимчасове зберігання даних. При оцінці пам’яті, що використовується, не враховується місце, яке займає початковий масив і незалежні від вхідної послідовності витрати, наприклад, на зберігання коду програми. 3. Стійкість - стійке сортування не міняє взаємного розташування рівних елементів. Така властивість може бути дуже корисною, якщо вони складаються з декількох полів, як на рис. 5, а сортування відбувається по одному з них, наприклад, по x. Рис.5 Приклад стійкого і нестійкого сортування Взаємне розташування рівних елементів з ключем 1 і додатковими полями "a", "b", "c" залишилося початковим: елемент з полем "a", потім - з "b", потім - з "c". Взаємне розташування рівних елементів з ключем 1 і додатковими полями "a", "b", "c" змінилося. 4. Природність поведінки - ефективність методу при обробці вже відсортованих, або частково відсортованих даних. Алгоритм поводиться природно, якщо враховує цю характеристику вхідної послідовності і працює краще. Швидке сортування Алгоритм "швидкого сортування" був розроблений більше 40 років тому, і є найбільш широко вживаним і одним з найефективніших алгоритмів сортування. Метод заснований на підході "поділяй-і-владарюй". Загальна схема алгоритму наступна: 1. з масиву вибирається деякий опорний елемент а[i]; 2. запускається процедура розділення масиву, яка переміщає всі ключі, які менше-рівні а[i], ліворуч від нього, а всі ключі, більші, або дорівнюють а[i] – вправо; 3. тепер масив складається з двох підмножин, причому ліва менша, або дорівнює правій; 4. для обох підмасивів: якщо у підмасиві більше двох елементів, рекурсивно запускаємо для нього ту саму процедуру. У кінці роботи отримуємо повністю відсортовану послідовність. Розглянемо алгоритм детальніше. 1.7.1. Розділення масиву На вході масив а[0]...а[N] і опорний елемент p, по якому проводитиметься розділення. 1. Введемо два покажчики: i і j. На початку алгоритму вони вказують, відповідно, на лівий і правий кінець послідовності. 2. Рухатимемо покажчик i з кроком в 1 елемент у напрямку до кінця масиву, поки не буде знайдений елемент а[i]>= p. Потім аналогічним чином почнемо рухати покажчик j від кінця масиву до початку, поки не буде знайдений а[j]<= p. 3. Далі, якщо i <= j, міняємо а[i] і а[j] місцями і продовжуємо рухати i,j за тими ж правилами. 4. Повторюємо крок 3, поки i <= j. Розглянемо роботу процедури для масиву а[0]...а[6] і опорного елемента p = а[3]. Рис.16 Приклад роботи алгоритму швидкого сортування Тепер масив розділений на дві частини: всі елементи лівої менше або рівні p, всі елементи правої - більше, або рівні p. Розділення завершено. 1.7.2. Загальний алгоритм Наведемо псевдокод алгоритму. ШвидкеСортування ( масив а, верхня межа N ) { Вибрати опорний елемент p - середину масиву Розділити масив по цьому елементу Якщо підмасив зліва від p містить більше одного елемента викликати для нього ШвидкеСортування. Якщо підмасив праворуч від p містить більше одного елемента викликати для нього ШвидкеСортування. } Кожне розділення вимагає, очевидно, Theta(n) операцій. Кількість кроків розподілу (глибина рекурсії) складає приблизно log n, якщо масив ділиться на більш-менш рівні частини. Таким чином, загальна швидкодія: О(n log n), що і має місце на практиці. Проте, можливий випадок таких вхідних даних, на яких алгоритм працюватиме за O(n2) операцій. Таке відбувається, якщо кожного разу у ролі центрального елемент вибиратиметься максимум або мінімум вхідної послідовності. Якщо дані взяті випадково, ймовірність цього дорівнює 2/n. Ця ймовірність повинна реалізовуватися на кожному кроці. Метод є нестійким. Поведінка досить природна, якщо врахувати, що при частковій впорядкованості підвищуються шанси розділення масиву на рівніші частини. Сортування використовує додаткову пам’ять, оскільки приблизна глибина рекурсії складає О(log n), а дані про рекурсивні підвиклики кожного разу додаються у стек. 4. Варіант індивідуального завдання Програмно реалізувати алгоритм сортування Текст програми на мові С. #include <iostream> using namespace std; int a[100]; void quickSort(int l, int r) { int x = a[l + (r - l) / 2];//запись эквивалентна (l+r)/2, int i = l; int j = r; //код в while обычно выносят в процедуру particle while(i <= j) { while(a[i] < x) i++; while(a[j] > x) j--; if(i <= j) { swap(a[i], a[j]); i++; j--; } } if (i<r) quickSort(i, r); if (l<j) quickSort(l, j); } int main() { int n;//количество элементов в массиве cin >> n; for(int i = 0; i < n; i++) { cin>>a[i]; } quickSort(0, n-1); for(int i = 0; i < n; i++) { cout<<a[i]<<" "; } system("pause"); return 0; } Результати / Висновок. На цій лабораторній роботі я вивчив алгоритми сортування.Закріпив набуті знання на практиці:слав программу яка реалізує мій варіант сортування.

Лабораторна робота Алгоритмізація і програмування

Kaljan333

05.01.2013 15:01-

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись