Міністерство освіти і науки України Вінницький національний технічний університет Факультет інформаційних технологій і комп’ютерної інженерії Кафедра комп’ютерних наук Лабораторна робота №2 З дисципліни: Теорія алгоритмів Тема: «Аналіз сортування алгоритму методом прямого вибирання» Вінниця, 2017 Аналіз сортування алгоритму методом прямого вибирання Мета: проаналізувати складність алгоритму методом прямого вибирання, практично та аналітично. Навчитись оцінювати асимптотичну складність алгоритму. Ідея алгоритму: Серед n елементів масиву вибирається найменший. Він міняється місцями з першим елементом a1. Далі цей процес повторюється із рештою n - 1 елементами, n – 2 елементами і т. д. доти, поки не залишиться один, найбільший елемент. Такий алгоритм, у певному смислі, протилежний алгоритму сортування вставками. В останньому випадку на кожному кроці розглядається тільки один черговий елемент вихідної послідовності та всі елементи готової послідовності, серед яких відшуковується точка вставки; при прямому виборі для пошуку одного елементу з найменшим ключем проглядаються всі елементи вихідної послідовності і знайдений розташовується як черговий елемент у готову послідовність. Час роботи алгоритму: Як і у випадку сортування вставками, склавши внески всіх рядків отримаємо час виконання в загальному випадку: Відсортований масив: Цей випадок є найсприятливіший, оскільки не виконуються блоки 6 і 7, а отже час виконання буде найменшим. Відсортований у зворотному напрямку масив: Цей випадок є найнесприятливіший, оскільки кожен елемент масиву потрібно переміщати, а отже час виконання буде найбільший. Псевдокод алгоритму сортування прямим вибором: Блок-схема алгоритму сортування прямим вибором: Код програми: using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; using System.Diagnostics; namespace _1234 { class Program { static void Main(string[] args){ // Створення масиву// Random zap = new Random();//для отримання випадкових цілих чисел Console.WriteLine("Введiть кiлькiсть елементiв масива:"); int a = Convert.ToInt32(Console.ReadLine());//конвертуєм змінну а в int Stopwatch watch0 = new Stopwatch(); watch0.Start(); int[] arr1 = new int[a]; Console.WriteLine("Невідсортований массив:"); //створюєм масив for (int q = 0; q < a; q++) { arr1[q] = zap.Next(1, 100); Console.Write(arr1[q] + " "); } watch0.Stop(); Console.WriteLine("\nЧас виконання програми в мілесекундах : " + watch0.ElapsedMilliseconds + "mc.\r\n"); //Сортування масиву// Stopwatch watch = new Stopwatch(); //для визначення часу виконання масиву watch.Start(); int min = 0, temp = 0; for (int i = 0; i < a - 1; i++) //сортуємо масив { min = i; for (int j = i + 1; j < a; j++) { if (arr1[j] < arr1[min]) { min = j; } } temp = arr1[i]; arr1[i] = arr1[min]; arr1[min] = temp; } Console.WriteLine("\nВiдсортований масив"); for (int i = 0; i < arr1.Length; i++) { Console.Write(arr1[i] + " "); //виводимо масив } watch.Stop(); Console.WriteLine("\nЧас виконання програми в мілесекундах : " + watch.ElapsedMilliseconds + "mc.\r\n"); //Сортування масиву у зворотньому напрямку// Stopwatch watch1 = new Stopwatch(); //для визначення часу виконання масиву watch1.Start(); int min1 = 0, temp1 = 0; for (int i = 0; i < a - 1; i++) //сортуємо масив { min1 = i; for (int j = i + 1; j < a; j++) { if (arr1[j] > arr1[min1]) { min1 = j; } } temp1 = arr1[i]; arr1[i] = arr1[min1]; arr1[min1] = temp1; } Console.WriteLine("\nВiдсортований у зворотньому напрямку масив"); for (int i = 0; i < arr1.Length; i++) { Console.Write(arr1[i] + " "); //виводимо масив } watch1.Stop(); Console.WriteLine("\nЧас виконання програми в мілесекундах : " + watch1.ElapsedMilliseconds + "mc.\r\n"); Console.ReadLine(); } } } Дослідження залежності часу (в мс.) виконання масиву від входу Кількість елементів масиву Відсортований масив Не відсортований масив Відсортований у зворотному напрямку  n = 4 000 29 31 31  n = 8 000 114 120 122  n = 10 000 181 189 196  n = 15 000 401 410 414  n = 20 000 713 722 729   Графік залежності часу виконання масиву від входу: / / / Висновок: провівши аналіз сортування алгоритму методом прямого вибирання можна зробити висновок, що представлений метод зручний для сортування середньої кількості послідовностей. Виходячи з даних таблиці зрозуміло, що на час виконання сортування значно впливає к-сть вхідних даних, вихідної впорядкованості масиву. Найбільше часу потрібно для сортування відсортованого у зворотньому напрямку масиву, найменше – для вже відсортованого масиву. Чим більша к-сть вхідних даних, тим більший час потрібний для його сортування. Перевагами цього алгоритму є простота, стійкість та відсутність додаткової пам’яті. Недоліками є те, що для його реалізації потрібно додатковий масив та той факт, що для знаходження мінімального елемента і його індексу на кожному проході доводиться переглядати всі елементи масиву.