Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Аналіз сортування алгоритму методом прямого вибирання
Інформація про навчальний заклад
ВУЗ:
Вінницькій національний технічний університет
Інститут:
Інститут комп’ютерних наук та інформаційних технологій
Факультет:
ФІТКІ
Кафедра:
КН
Інформація про роботу
Рік:
2024
Тип роботи:
Лабораторна робота
Предмет:
Теорiя алгоритмiв i математичнi основи представленння знань
Група:
КН 2
Варіант:
13
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Вінницький національний технічний університет
Факультет інформаційних технологій і комп’ютерної інженерії
Кафедра комп’ютерних наук
Лабораторна робота №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
Графік залежності часу виконання масиву від входу:
/
/
/
Висновок: провівши аналіз сортування алгоритму методом прямого вибирання можна зробити висновок, що представлений метод зручний для сортування середньої кількості послідовностей. Виходячи з даних таблиці зрозуміло, що на час виконання сортування значно впливає к-сть вхідних даних, вихідної впорядкованості масиву.
Найбільше часу потрібно для сортування відсортованого у зворотньому напрямку масиву, найменше – для вже відсортованого масиву. Чим більша к-сть вхідних даних, тим більший час потрібний для його сортування.
Перевагами цього алгоритму є простота, стійкість та відсутність додаткової пам’яті.
Недоліками є те, що для його реалізації потрібно додатковий масив та той факт, що для знаходження мінімального елемента і його індексу на кожному проході доводиться переглядати всі елементи масиву.
24.10.2018 17:10-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора