Реферат
Програма для сортування даних методами вибору.
Ключові слова: СОРТИРОВКИ, МЕТОДИ СОРТУВАННЯ, ВИБІРКА, пірамідальна, плавно, МАСИВИ.
Мета роботи: Проектування і розробка програми для здійснення сортування даних методами «Вибору» з використанням мови C # і Visual Studio 2012.
Об'єкт дослідження: Методи сортування Вибором.
Предмет дослідження: Програма мовою С #.
Зміст
Зміст
Введення
. ОПИС ПРЕДМЕТНОЇ ОБЛАСТІ
.1 Сортування вибором
.2 Пірамідальна сортування
.3 Плавний метод сортування
.4 Постановка завдання
. ТЕХНОЛОГІЯ РОЗРОБКИ ДОДАТКИ
.1 Алгоритм рішення
.2 Макет програми
.3 Опис програми
ВИСНОВОК
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ
ДОДАТОК-Лістинг ПРОГРАМИ
Введення
У сучасному світі ми часто стикаємося з великими обсягами потрібної нам інформації. Її так багато, що можна заплутатися, що ж робити? Дійсно, нерідко серед величезного потоку інформації можуть загубитися необхідні дані. Щоб уникнути цього, а також прискорити пошук потрібної інформації використовують методи сортувань. Існує два види сортування даних: зовнішній і внутрішній.
Внутрішня сортування оперує з масивами, цілком поміщається в оперативній пам'яті з довільним доступом до будь комірці. Цей вид сортування характерний тим, що дані сортуються на тому ж місці, без додаткових витрат.
У свою чергу методи внутрішнього сортування діляться на прямі і поліпшені:
Прямі методи:
· вставкою (включенням)
· Вибором (виділенням)
· Обміном («бульбашкова»)
Поліпшені методи:
· Швидка
· Шелла
Зовнішня сортування - сортування даних, розташованих на периферійних пристроях і не вміщаються в оперативну пам'ять, тобто коли застосувати одну з внутрішніх сортувань неможливо.
Варто відзначити, що внутрішня сортування значно ефективніше зовнішньої, так як на звернення до оперативної пам'яті витрачається набагато менше часу, ніж до магнітних дисків, стрічок і т. п.
Розглянутий в даній курсовій роботі вид сортування «Вибір» має три варіанти реалізації: проста вибірка, пірамідальна, плавна.
У відповідності з поставленою метою були сформульовані наступні завдання:
· Провести предметний аналіз в області
· Розробити необхідну програму
· Провести тестування програми
· Визначити ефективність розробленої програми
1.Описание ПРЕДМЕТНОЇ ОБЛАСТІ
1.1 Сортування вибором
Сортування вибором (від англ. Selection sort) - алгоритм сортування. Може бути як стійкий, так і нестійкий. На масиві з n елементів має час виконання у найгіршому, середньому і кращому випадку? (), Припускаючи, що порівняння робляться за постійний час.
Ідея методу полягає в тому, щоб створювати відсортовану послідовність шляхом приєднання до неї одного елемента одним в правильному порядку. Будемо будувати готову послідовність, починаючи з лівого кінця масиву. Алгоритм складається з n послідовних кроків, починаючи від нульового і закінчуючи (n - 1) -му. На i-му кроці вибираємо найменший з елементів a [i] ... a [n] і міняємо його місцями з a [i]. Послідовність кроків при n=5 зображена на рис.1
Рисунок1. Демонстрація послідовних кроків при n=5
Незалежно від номера поточного кроку i, послідовність a [0] ... a [i] є впорядкованою. Таким чином, на (n - 1) -му кроці вся послідовність, крім a [n] виявляється відсортованої, а a [n] стоїть на останньому місці по праву: все менші елементи вже пішли вліво.
Для знаходження найменшого елемента з n + 1 розглянутих алгоритм здійснює n порівнянь. З урахуванням того, що кількість розглянутих на черговому кроці елементів зменшується на одиницю, загальна кількість операцій:
n + (n - 1) + (n - 2) + (n - 3) + ... 1=1/2 * (+ n)=Theta ().
Таким чином, оскільки число обмінів завжди буде менше числа порівнянь, час сортування зростає квадратично щодо кількості елементів.
1.2 Пірамідальна сортування
Пірамідальна сортування є методом, швидкодія якого оцінюється як О (n log n). В якості деякої прелюдії до основного...