тього - 8, після k -го кроку - 2 ^ k. Алгоритм: вихідний файл f розбивається на два допоміжних файлу f1 і f2. Допоміжні файли f1 і f2 зливаються в файл f, при цьому поодинокі елементи утворюють впорядковані пари. Отриманий файл f знову обробляється, як зазначено в кроках 1 і 2. При цьому впорядковані пари переходять у впорядковані четвірки. Повторюючи кроки, зливаємо четвірки в вісімки і т.д., кожен раз подвоюючи довжину злитих послідовностей до тих пір, поки не буде впорядкований цілком весь файл;
багатофазна сортування (Фібоначчієва): на кожному кроці ми беремо найменший з початкових елементів вхідних серій і переміщаємо в кінець вихідний серії. Кожна операція злиття серій, очевидно, вимагає n пересилань елементів, де n - загальне число елементів серій. У процесі сортування ми будемо оперувати стрічками - структурами даних, де в кожен момент нам доступний або перший елемент, або наступний елемент після вже прочитаного. У реальній ситуації в якості стрічок виступають одинзв'язні списки або файли. Нехай у нас є N стрічок: N - 1 вхідна і одна порожня. Ми будемо зливати елементи зі вхідних стрічок на вихідну, поки яка-небудь з них не спорожніє. Потім вона стане вхідний. У кожний момент часу злиття відбувається на порожню стрічку з інших, тому число потрібних проходів приблизно дорівнює log n. Далі нам знадобляться числа Фібоначчі порядку p. Очевидно, звичайні числа Фібоначчі мають порядок 1. З цього випливає, що наш алгоритм багатофазного злиття застосуємо тільки до таких вхідним даним, в яких число серій є сума n - 1 таких сум Фібоначчі.
. 2 Побудова діаграм
. 2.1 Діаграма варіантів використання
Цей вид діаграм дозволяє створити список операцій, які виконує система. Часто цей вид діаграм називають діаграмою функцій, тому що на основі набору таких діаграм створюється список вимог до системи і визначається безліч виконуваних системою функцій. Дана діаграма характеризує роботу програмного засобу «Порівняльний аналіз методів внутрішнього сортування даних». У даній діаграмі використовуються наступні варіанти використання: «Порівняльний аналіз методів сортування даних», «Надати опис алгоритмів», «Продемонструвати аналіз методів на різних масивах», «Побудувати гістограми для наочного порівняння методів», «Отримати довідкову інформацію», «Ввести», «Вивести», «Відсортувати масив», «Візуалізувати процес сортування».
Діаграма варіантів використання представлена ??в додатку А.
. 2.2 Діаграма діяльності
При моделюванні поведінки системи виникає необхідність деталізувати особливості алгоритмічної і логічної реалізації виконуваних системою операцій. Для моделювання процесу виконання операцій використовуються так звані діаграми діяльності. Кожен стан на діаграмі діяльності відповідає виконанню деякої елементарної операції, а перехід в наступний стан спрацьовує тільки при завершенні цієї операції в попередньому стані. Графічно діаграма діяльності представляється у формі графа діяльності, вершинами якого є стани дії, а дугами - переходи від одного стану дії до іншого. На діаграмі діяльності відображається логіка або послідовність переходу від однієї діяльності до іншої, при цьому увага фіксується на результаті діяльності.
Стани, використовувані для побудови діаграми: «Теорія про методи», «Теорія з аналізу алгоритмів», «Сортування масиву», «Відображення інформації про методи», «Порівняння швидкодії, кількості перестановок», «Введення масиву »,« Вибір методів »,« Перевірка, введений Чи масив »,« Повідомлення про помилку »,« Перегляд відсортованого масиву »,« Перегляд гістограм порівняння »,« Візуалізація процесу сортування ».
Діаграма діяльності представлена ??в додатку.
1.3 Вибір і обгрунтування засобів розробки
Для розробки програмного засобу були обрані операційна система Windows 7, середа розробки Microsoft Visual Studio 2012, мова програмування C #.
1.3.1 Обгрунтування вибору ОС
Сімейство операційних систем Windows має такі переваги: ??
Графічний інтерфейс користувача. У Windows він заснований на ідеї віконного інтерфейсу, прийнятого так само і в ряді інших сучасних ОС (наприклад, UNIX). Кожна програма має власне вікно, в якому і відбувається обмін повідомлень з користувачем. Для наочності в Windows широко застосовуються іконки (піктограми), що зображують окремі програми. Крім того, інтерфейс Windows в значній мірі стандартизований, що полегшує користувачам процес освоєння нових програм.
Багатозадачність. Багатозадачний режим роботи дозволяє запускати одночасно кілька додатків, наприклад, текстовий процесор, базу даних, гру і перемикатися між ними.
