Основна стратегія прискорення алгоритмів сортування - обміни між якомога більш далекими елементами вихідного файлу - в методі швидкого сортування реалізована за рахунок того, що один із ключів у вихідному файлі використовується для поділу його на два подфайла так, щоб зліва від вибраного елемента знаходилися тільки елементи з меншими ключами, а праворуч - тільки з великими. Елемент, що розділяє файл, поміщається між його двома подфайламі і процедура виконується рекурсивно для кожної половини до тих пір, поки в черговому новому подфайле не виявиться менше, ніж М елементів, де М - заздалегідь вибране число.
Сортування подфайлов, що містять менше ніж М елементів, виконується будь-яким простим методом, наприклад простими вставками. Таким чином, реалізація методу залежить від двох параметрів: значення М і способу вибору елемента, який призначений для розділення файлу на дві частини.
Блок вибору Х в найпростішому випадку формулюється як X = K [l], однак це може призвести до вкрай неефективного алгоритму. Найбільш просте краще рішення - вибирати Х як випадковий ключ з діапазону K [l] ... K [r] і обміняти його з K [l].
Час роботи алгоритму t приблизно оцінюється формулою:
t = a * N * logN + b * N
де a, b - невідомі константи, що залежать від програмної реалізації алгоритму.
Обмінна поразрядное сортування
Даний метод використовує двійкове подання ключів. Файл сортується послідовно по бітах двійкового представлення ключів, починаючи зі старшого. Ключі, що мають значення даного біта, равноенулю, ставляться в ліву половину файлу, а ключі із значенням біта 1 в праву. Функція b (ключ) повертає значення ьіта з номером b аргументу, m-якомога більше значущих бітів в ключах.
Час роботи алгоритму t приблизно оцінюється формулою: t = a * N * logN + b * N
де a, b - невідомі константи, що залежать від програмної реалізації алгоритму.
Паралельна сортування Бетчера
Для отримання алгоритму обмінної сортування, час роботи якого менше, ніж NЅ, необхідно вибирати для порівняння та обміну ключі, розташовані можливо далі один від одного. Ця ідея вже була реалізована в алгоритмі сортування Шелла вставок з убуваючим кроком, проте в даному алгоритмі порівняння виконуються по-іншому.
Час роботи алгоритму t приблизно оцінюється формулою: t = a * N * (logN) Ѕ
де a, b - невідомі константи, що залежать від програмної реалізації алгоритму.
Сортування за допомогою вибору
Ідея методу досить проста: знайти найбільший елемент файлу і по-ставити його на місце N, знайти наступний максимум і поставити його на місце N-1 і т.д. до 2-го елемента.
Час роботи алгоритму t приблизно оцінюється формулою: t = a * NЅ + b * N * logN
де a, b - невідомі константи, що залежать від програмної реалізації алгоритму.
Використання пов'язаного списку для зберігання інформації про проміжної максимумах.
В алгоритмі максимум серед K [1] ... K [j-1] визначається в циклі від j-1 до 1 c метою забезпечити менше число обмінів у разі рівності ключів і збереженні колишнього порядку рівних елементів. Однак, якщо змінити порядок перегляду елементів на протилежний і змінити структуру даних, ввівши додаткові покажчики, можна приклад-но в два рази скоротити кількість повторень у циклі пошуку максісмума. Кожен ключ K [i] постачається покажчиком L [i] на елемент, максимальний серед перших i-1 елементів.
Тоді після обміну елементів K [j] і K [m] пошук максимуму в наступному циклі по j можна здійснювати серед елементів K [L [m]] ... K [j] при началь-них значеннях X = K [L [m]], m = L [m], тому що максимум може "оновитися" тільки за рахунок елементів, що лежать правіше локального максимуму. Таким чином середня кількість переглядаються при пошуку максимуму елементів зі-Припиняються приблизно в два рази.
Час роботи алгоритму t приблизно оцінюється формулою: t = a * NЅ + b * N * logN
де a, b - невідомі константи, що залежать від програмної реалізації алгоритму.
Сортування за допомогою злиття
Алгоритми сортування цього класу грунтуються на об'єднанні кількох (найчастіше двох) вже упорядоченнх файлів. Розглянуті далі алгоритми вибирають з вихідного файлу впорядковані відрізки і об'єднують їх в більш довгі.
Природне двоколійних злиття
Цей алгоритм шукає впорядковані відрізки з двох кінців файлу іперепісивает їх по черзі також в обидва кінці. Повторюючи цю процедуру в циклі, ми приходимо до середини файлу, що означає закінчення сортування.
Елементи файлу пересилаються з однієї області в іншу, міняючи напрямок пересилки. Для запам'ятовування напрямку пересилання служить мінлива s, що приймає значення TRUE і FALSE поперемінно. Інший логічний ознака f служить сигналом продовження-закінчення алгоритму, якщо всі області злилися в кінці кінців в одну. Змінна d приймає поперемінно значення +1 -1 і вказує напрям перегляду файлу: вперед чи назад.Операція <-> позначає обмін значеннями двох змінних. Операція Џ позначає інверсію логічної змінної або виразу.
Час роботи алгоритму t приблизно оцінюється формулою:
t = a * N * lgN + b * N
де a, b - невідомі константи, що залежать від програмної реалізації алгоритму.
Просте двоколійних злиття.
В алгоритмі природного двоколійних злиття упорядкований відрізки файлу визначалися випадковим розташуванням елементів у вихідному файлі. У даному алгоритмі довжина відрізків фіксується на кожному кроці. У вихідній файлі всі відрізки мають довжину 1, після першого кроку вона дорівнює 2, після другого 4, після третього - 8, після к-го кроку -2 в ступеня к.
Час роботи алгоритму t приблизно оцінюється формулою: t = a * N * lgN + b * N
де a, b - невідомі константи, що залежать від програмної реалізації алгоритму.
1.2 ОБГРУНТУВАННЯ ВИБОРУ МЕТОДУ РОЗВ'ЯЗАННЯ ЗАДАЧІ
Сортування масиву швидким методом є прекрасним прикладом целесооразності використання рекурсивного звернення до програмувати мовою Сі. Метод швидкого сортування був запропонований К. А. Р. Хоор у 1962р. Запропонована версія швидкого сортування, зрозуміло, не найшвидша серед всіх можливих, але зате вона з найпростіших.
Основна стратегія прискорення алгоритмів сортування - обміни між якомога більш далекими елементами вихідного файлу - в методі швидкого сортування реалізована за рахунок того, що один із ключів у вихідному файлі використовується для поділу його на два подфайла так, щоб зліва від вибраного елемента знаходилися тільки елементи з меншими ключами, а праворуч - тільки з великими.
Алгоритми сортування методом злиття грунтуються на об'єднанні кількох (найчастіше двох) вже упорядоченнх файлів. Цей алгоритм шукає впорядковані відрізки з двох кінців файлу і переписує їх по черзі також в обидва кінці. Повторюючи цю процедуру в циклі, ми приходимо до середини файлу, що означає закінчення сортування.

3. РОЗРОБКА АЛГОРИТМУ РІШЕННЯ ЗАДАЧІ
Алгоритм рішення завдання гранично простий. Функція main ()-це також функцією меню і виконує опитування клавіатури. Залежно від натиснутої клавіші виконує відповідні дії програми. Для читання інформації про програму з файлу text.hlp використовується функція help (), яка працює з файловим висновком. Функція file () основна оскільки з її допомогою виконується сортування масиву (виклик функцій qqsort () і srecmg ()) визначення часу сортування виклик функції побудова гістограм. Масив складається з випадкових чисел вводяться в нього функцією генератора випадкових чисел. Далі функція file () викликає відповідні функції сортування, засікає час сортування відповідним способом, і заносить цей час в масив simvol []. Далі дані з масиву передаються у функцію grafix (), де вони використовуються при виведенні на екран гістограм в графічному режимі. Програма передбачає випадки відсутності деяких програмних елементів. У цьому випадку викликається функція Error (), яка створює вікно повідомлення в яке вписуються характеристика помилки. Так програма не буде виконуватися якщо не знайдений файл "text.hlp" або драйвер EGAVGA.BGI
.
3. РОЗРОБКА ПРОГРАМИ
3.1 ОПИС ПРОГРАМИ
Дана програма називається "TEST" (ім'я виконуваного файлу test.exe) і призначена для аналізу методів сортування одновимірного масиву. Програма працює на IBM сумісних комп'ютерах сімейства х86 починаючи з 286 і вище, в операційній системі типу Ms-DOS 3.0 і вище.
Програма містить п'ять основних функцій: main (), file (), qsort (), srecmg (), grafix (). Всі змінні, що використовуються в програмі є локальними.
Функція main () містить пункти меню і викликає інші виконавчі функції залежно від натискання запропонованих функціональних клавіш F1, F2 і F10. Кожна з цих функцій працює автономно і незалежно від двох інших.
Програма реалізована як у псевдографічним так і в графічному режимі (у зв'язку з чим вона може компілюватися тільки в DOSовскіх версіях BorlandC + + або BorlandC). У графічному режимі вона виводить на екран гістограму яка характеризує час сортування масивів двома способами.
Програма використовує як стандартний так і файловий ввід-висновок інформації. Стандартне введення представлений запитом програми на введення функціональних клавіш, які задають характер виконуваної дії. Файловий ввід-висновок використовується у функції help (), для виводу на екран інформації про розробника програми, її функціональні клавіші і про можливі помилки в процесі виконання. Крім того програма працює з функцією часу clock () і змінними часу типу clock_t.
Так само програма містить стандартні функції мови Сі, описані в бібліотеках: <string.h>, <stdlib.h>, <time.h>, <stdio.h>, <conio.h>, <graphics.h>. Нижче перераховані бібліотеки з функціями і дано короткий опис використаних у програмі стандартних функцій.
З бібліотеки <time.h>:
clock () - ця функція повертає час, що фіксується процесором від початку рахунку програми, або -1, есле воно не відомо. Для повернення цього часу в секундах застосовується формула clock () / CLK_TCK.
З бібліотеки <stdlib.h>:
rand () - ця функція видає псевдо випадкове число в діапазоні від 0 до RAND_MAX не менше 32767.
exit () - викликає нормальне завершення програми.
З бібліотеки <stdio.h>:
printf () - ця функція здійснює висновок рядка на екран.
fopen () - ця функція відкриває файл із заданим ім'ям і повертає потік або NULL, якщо спроба відкриття була невдалою.
fclose () - ця функція проводить дозапис ще незаписаних буферізірованний даних, скидає нечитаний буферізірованний введення, звільняє всі автоматичні запитані буфера, після чого закриває потік. Повертає EOF у разі помилки і 0 у противному випадку.
fgetc () - ця функція повертає следущуюлітеру з потоку stream у вигляді unsigned char або EOF, якщо вичерпано файл або виявлена ​​помилка.
puts () - пише стринг s та літеру нова - рядок в stdout. Повертає EOF у разі помилки, або позитивне значення, якщо запис пройшов нормально.
З бібліотеки <conio.h>
textbackground () - за допомогою цієї функції встановлюється колір фону для функції cprintf ().
textcolor () - за допомогою цієї функції встановлюється колір тексту для функції cprintf ().
clrscr () - функція очищення екрана, кольором встановленим функцією textbackground ().
cprintf () - за допомогою цієї функції здійснюється виведення рядка з урахуванням квітів встановлених функціями textbackground (), textcolor ().
_setcursortype () - за допомогою даної функції здійснюється зміна режиму відображення курсора. Даних режимів у си всього три - NOCURSOR (курсор вимкнений), SOLIDCURSOR (курсор у вигляді суцільного блоку) NORMALCURSOR (звичайний курсор).
getch () - функція getch здійснює зчитування першого єдиного символу з клавіатури, використовується при зчитуванні клавіш курсору при переміщенні по вікну вибору режиму роботи програми.
gotoxy () - ця функція переміщує курсор в потрібну частину екрану, зазвичай використовується перед функцією cprintf ().
У цій бібліотеці описані всі символічні константи квітів використовувані функціями textbackground (), textcolor (). У ній також описані всі типи курсорів використовуваних функцією _setcursortype ().
3.1.1 ОПИС ФУНКЦІЇ main ()
Функція main має тип void і є функцією меню. Main виконує опитування клавіатури і залежно від натиснутої функціональної клавіші виконується відповідна дія (виклик допомоги, тестування і вихід з програми). Ця можливість реалізована завдяки конструкції множинного вибору switch. Функція має одну локальну змінну divss має тип char. Вона сприймає символ з клавіатури без виведення на екран і використовується в конструкції switch при переході до іншої виконуваної функції. У даній функції викликається допоміжна функція windows (), яка створює псевдографічний інтерфейс при запуску програми. При виборі пункту виходу з програми стандартна функція textbackground () створює чорний екран, а функція exit () здійснює вихід з програми.
При виклику функції допомоги (help ()) програма звертається до цієї функції, яка зчитує і виводить інформацію файловим способом. Викликаний фаил зберігається під ім'ям test.hlp і при його відсутності видається вікно повідомлення: «Фаил text.hlp не знайдений".
Виклик функції побудови гістограм виконується при натисканні клавіші F2. При цьому функція main () звертається до функції file ().
3.1.2 ОПИС ФУНКЦІЇ srecmg ().
Для побудови упорядкованого списку В 'зі списку В = <к1, к2 ,..., Кn> при сортуванні злиттям список В ділиться на n підсписків В1 = <к1>, В2 = <к2>, ... , Вn = <Кn> довжини 1. Потім відбувається процедура проходження в якій m ≥ 2 упорядкованих списків В1, В2 ,..., Вm змінюються на m / 2 (або (m +1) / 2) упорядкованих списків які створюються злиттям B2i-1и B2i (2i ≤ m) і підсумовуванням Bm c непарним m. Процес повторюється до появи однієї послідовності довжини m. Кількість дій, необхідних для сортування злиттям, дорівнює n log2n, тому що за одне проходження виконується n порівнянь, а всього необхідно здійснити log2n проходжень. Сортування сліянііем дастаточно ефективно і використовується при великих значення n.
Функція srecmg () є рекурсивної, і сортує масив а [n]. За кожним викликом масив для сортування ділиться на дві частини - від а [0] до
a [i-1] і від a [i] до a [n], кожна з яких впорядковується окремо, а потім виконується їх злиття. Злиття виконується за допомогою викликається функції merge () в яку передається покажчик на масив, поточний номер елемента масиву і кількість елементів масиву. Параметрами функції merge () є масив w [], його довжина l / 2 і довжина першої частини масиву l1. Функція merge () виконує злиття подмассивов, утворюючи на їх місці впорядкований масив w [0], w [1 ],... , w [l2-2], w [l2-1].
3.1.3 ОПИС ФУНКЦІЇ qqsort ()
Швидке сортування полягає в тому, що список В = <k1,k2,…,kn> реорганізується в B ', <k1>, B ", де В' - подспісок В з елементами, не великими k1, а B" - підсписок У з елементами великими k1. У списку В ', <k1>, В "елемент К1 вже знаходиться на місці де він повинен бути в отсортірованом списку. Далі до списків В 'і В''застосовується упорядованіченіе швидкої сортуванням.
Рекурсивна функція qqsort упорядоваечет швидкої сортуванням ділянку масcіва цілих чисел перший елемент якого вказується показником v [left], останній - показником v [right].
Якщо ділянка масива більш ніж з двох елементів, v [left] - low> 1, то перебуває ділив елемент і переноситься в V [0]. Мінно last присвоюється значення першого елемента масиву left. Потім масив ділиться на дві частини, елементи яких відповідно більше і менше last. Далі функція виконує перезапам'ятовування ділить елемента і викликає себе для розбитих підсписків.
Обмін елементів виконується за допомогою функції swap (), в яку з функції qqsort () перелається покажчик на масив і елементи, місце-розташування яких у масиві потрібно звернути.
Час побудови списку залежить від його початкового стану. Час буде мінімальним, якщо кожен крок розділу дає підсписки В ', B''приблизно однакової довжини; тоді необхідно (n log2 n) кроків. Якщо початковий список мало чим відрізняється від звичайного відсортовані то необхідно (n ^ 2) / 2 кроків. Швидке сортування вимагає додаткової пам'яті порядку O (log2n) для виконання рекурсивної функції qqsort () (неявного стека).