МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” Кафедра ЕОМ / Розробка та дослідження ефективності методів сортування ЗВІТ до лабораторної роботи № 3 з дисципліни " AЛГОРИТМИ ТА МЕТОДИ ОБЧИСЛЕНЬ" МЕТА РОБОТИ Вивчення, реалізація та дослідження ефективності методів сортування даних. 2. ТЕОРЕТИЧНІ ВІДОМОСТІ 2.1. Задача сортування Задача сортування в програмуванні не вирішенаповністю. Адже, хоча й існує велика кількістьалгоритмівсортування, все ж таки метою програмування є не лишерозробкаалгоритмівсортуванняелементів, але й розробкасамеефективнихалгоритмівсортування. Ми знаємо, що одну й ту саму задачу можнавирішити за допомогоюрізнихалгоритмів і кожен раз зміна алгоритму приводить до нових, більшабоменшефективнихрозв'язківзадачі. Основнимивимогами до ефективностіалгоритмівсортування є перш за все часова ефективність та економневикористанняпам'яті. Згідноцихвимог, простіалгоритмисортування (такі, як сортуваннявибором і сортуваннявставкою) не є дужеефективними. Алгоритм сортуванняобміном, хоча і завершує свою роботу (оскількивінвикористовуєлише цикли з параметром і в тіліциклівпараметрипримусово не змінюються) і не використовуєдопоміжноїпам'яті, але займаєбагато часу. Навіть, якщовнутрішній цикл не міститьжодної перестановки, то діїбудутьповторюватись до тих пір, поки не завершиться зовнішній цикл. Алгоритм сортуваннявиборомефективнішесортуванняобміном за критерієм М(n), тобто за кількістюперестановок, але також є не дужеефективним. З цих причин булорозробленодеякіновіалгоритмисортування, щоотрималиназвушвидкихалгоритмівсортування. Цетакіалгоритми, як сортування деревом, пірамідальнесортування, швидкесортування Хоара та метод цифрового сортування. Метою роботи є ознайомлення з алгоритмами сортування, спробапроаналізуватиїх і написатипрограму, яка б виконуваласортуваннядеякоїпослідовності за допомогоюрізнихалгоритмівсортування. Необхідністьвідсортуватиякі-небудьвеличинивиникає в програмуваннідуже часто. Існуютьситуації, коли попереднєсортуванняданихдозволяєскоротитизмістовнучастину алгоритму в декількаразів, а час йогороботи - у десятки разів. Однаксправедливе й зворотне. Яким би гарним і ефективним не бувобраний алгоритм, але якщо в якості підзадачівінвикористовує "поганє" сортування, то вся робота з йогооптимізаціївиявляєтьсямарною. Невдалореалізованесортуваннявхіднихданихздатнепомітнознизитиефективність алгоритму в цілому. ЗАВДАННЯ НА ЛАБОРАТОРНУ РОБОТУ Задати послідовність цілих чисел довільної довжини і представити її у пам’яті комп’ютера у вигляді масиву або лінійного зв’язаного списку. Програмно реалізувати один із вказаних нижче методів сортування згідно з варіантом. Під час виконання програми обов’язково виводити на екран монітора всі проміжні кроки процесу сортування. Провести дослідження побудованого методу за такою схемою: 1). Обґрунтувати вибір структури даних, в якій має зберігатись інформація (масив чи список; якщо список, то однозв’язаний чи двозв’язаний). 2). Намалювати схему алгоритму на прикладі послідовності з десяти (або більше при необхідності) цілих чисел, показуючи всі проміжні кроки процесу сортування. 3). Дослідити метод cортуванняна стійкість. 4). Дослідити метод cортуванняна економність використання пам’яті. 5). Дослідити метод на можливу специфіку вхідної послідовності (чи може послідовність містити елементи з однаковими ключами, чи має бути вхідна послідовність частково відсортована, чи мають елементи послідовності знаходитись у певному діапазоні і т.п.). 6). Дослідити ефективність методу. Для цього визначити значення кількості порівнянь (С) і кількості перестановок (М) в найкращому (
) і в найгіршому (
) випадках. Середні значення кількості порівнянь (
) і кількості перестановок (
) визначити, як середнє арифметичне для кожної величини від великої кількості спроб сортування випадкових послідовностей. 7). Визначити до якого класу (підкласу) належить досліджуваний метод. Використовуючи методику аналізу основних алгоритмічних конструкцій та визначення набору "елементарних" операцій, обчислити складність методу, що характеризується функцією трудомісткості. Зробити висновки про ефективність методу. 1.Пірамідальне сортування. Результат виконання програми. / Текст програми: PyramidSorting.cs: using System; namespace Lab2 { classPyramidSorting { //додати1елементпіраміди staticint Add2Pyramid(double[] arr, inti, int N) { intimax; doublebuf; if ((2 * i + 2) < N) { if (arr[2 * i + 1] <arr[2 * i + 2]) { imax = 2 * i + 2; } else { imax = 2 * i + 1; } } elseimax = 2 * i + 1; if (imax>= N) { returni; } if (arr[i] <arr[imax]) { buf = arr[i]; arr[i] = arr[imax]; arr[imax] = buf; if (imax< N / 2) { i = imax; } } returni; } public static void Sorting(double[] arr, intlen) { //Крок 1. Створенняпіраміди for (inti = len / 2 - 1; i>= 0; --i) { longprev_i = i; i = Add2Pyramid(arr, i, len); if (prev_i != i) { ++i; } } //Kрок 2: сортування doublebuf; for (int k = len - 1; k > 0; --k) { buf = arr[0]; arr[0] = arr[k]; arr[k] = buf; inti = 0, prev_i = -1; while (i != prev_i) { prev_i = i; i = Add2Pyramid(arr, i, k); } } } } } Program.cs: using System; namespace Lab2 { class Program { static void Main(string[] args) { double[] arr = new double[20]; //fill the array with random numbers Random rd = new Random(); Console.WriteLine("Масивдосортування:"); for (inti = 0; i<arr.Length; ++i) { arr[i] = rd.Next(1, 21); Console.Write(arr[i] + " "); } PyramidSorting.Sorting(arr, arr.Length); Console.WriteLine("\n\nМасивпiслясортування:"); for (inti = 0; i<arr.Length; ++i) { Console.Write(arr[i] + " "); } Console.ReadLine(); } } } Висновок:Вивчив реалізацію та дослідження ефективності методів сортування даних.