Размещено на http://www.allbest.ru/

Технічний коледж ТНТУ імені Івана Пулюя

Циклова комісія комп'ютерних дисциплін

Курсова робота

з дисципліни:

СИСТЕМНЕ ПРОГРАМУВАННЯ

«Розробка програмного забезпечення для сортування масивів різними способами»

Тернопіль-2014

ЗМІСТ

ВСТУП

1. ЗАГАЛЬНИЙ РОЗДІЛ

1.1 Аналіз технічного завдання

1.1.1 Найменування та область застосування

1.1.2 Призначення розробки

1.1.3 Вимоги до програмного забезпечення

1.1.4 Часові характеристики

1.1.5 Умови експлуатації

1.1.6 Стадії та етапи розробки

1.1.7 Порядок контролю та прийому

2. РОЗРОБКА ТЕХНІЧНОГО ТА РОБОЧОГО ПРОЕКТУ

2.1 Постановка задачі на розробку програмного забезпечення

2.2 Опис та обґрунтування вибору методу організації вхідних та вихідних даних

2.2.1 Вхідні дані

2.2.2 Вихідні дані

2.3 Опис методів реалізації функцій програми

2.3.1 Головне вікно

2.3.2 Сортування масиву методом «бульбашки»

2.3.4 Сортування масиву методом Шелла

2.3.5 Сортування масиву методом вибірки

2.3.6 Сортування масиву методом вставки

2.3.7 Сортування масиву методом пірамід

2.3.8 Метод швидкого сортування Хоара

2.4 Визначення інформаційних зв'язків програмних компонентів

2.5 Написання текстів програми

2.6 Тестування та налагодження програми

3. СПЕЦІАЛЬНИЙ РОЗДІЛ

3.1 Інструкція по встановленню та використанню програми

ВИСНОВКИ

ПЕРЕЛІК ПОСИЛАНЬ

ДОДАТКИ

ВСТУП

С - це мова програмування загального призначення, добре відома своєю ефективністю, економічністю, і переносимістю. Зазначені переваги С забезпечують хорошу якість розробки майже будь-якого виду програмного продукту. Використання С в якості інструментальної мови дозволяє отримувати достатньо швидкі і компактні програми. У багатьох випадках програми, написані на С, порівняні по швидкості з програмами, написаними на мові асемблера. При цьому вони мають кращу наочність.

С поєднує ефективність і потужність у відносно не великій за розміром мові. Хоча С не містить вбудованих компонент мови, що виконують введення-виведення, розподіл пам'яті, маніпуляцій з екраном або управління процесами, тим не менш, системне оточення С має у своєму розпорядженні бібліотеку об'єктних модулів, в якій реалізовані подібні функції. Бібліотека підтримує багато з функцій, які потрібні для написання багато функціонального програмного забезпечення.

Мова С - це універсальна мова програмування, для якого характерні економічність виразів, сучасний потік управління і структури даних, багатий набір операторів. Мова С не є мовою " дуже високого рівня", і не призначається для деякої спеціальної області застосування, але відсутність обмежень і спільність мови роблять її більш зручною і ефективною для багатьох завдань, ніж мови, більш високого рівня.

Вона тісно пов'язана з операційною системою "UNIX", так як на цій системі програмне забезпечення написано на "C". Проте сама мова, не пов'язана з якою-небудь однією операційною системою або машиною ; і хоча її називають - «мовою системного програмування», так як вона зручна для написання операційних систем, але С успішно використовувався при написанні великих обчислювальних програм, програм для обробки текстів і баз даних.

Перерахуємо деякі істотні особливості мови С:

- С забезпечує повний набір операторів структурного програмування;

- С пропонує незвично великий набір операцій. Багато операцій С відповідають машинним командам і тому допускають пряму трансляцію в машинний код. Різноманітність операцій дозволяє вибирати їх різні набори для мінімізації результуючого коду;

С підтримує показники на змінні і функції. Показник на об'єкт програми відповідає машинній адресі цього об'єкта. За допомогою розумного використання показників можна створювати ефективно виконувані програми, оскільки показники дозволяють посилатися на об'єкти тим же самим шляхом, як це робить ЕОМ. С підтримує арифметику показників, і тим самим дозволяє здійснювати безпосередній доступ і маніпуляції з адресами пам'яті.

Проте, слід зазначити, що переваги мови С стають очевидними при реалізації великих програмних проектів. Перші ж кроки при програмуванні на С вимагають від програміста ретельного проектування програми, а також певної дисципліни при програмуванні.

1. ЗАГАЛЬНИЙ РОЗДІЛ

1.1 Аналіз технічного завдання

1.1.1 Найменування та область застосування

Сортування - це упорядкування елементів за зростанням або спаданням. Сортування дуже важлива операція в усіх сферах програмування. Необхідність сортування деяких величин виникає в програмуванні дуже часто, оскільки досить часто зустрічаються ситуації, коли попереднє сортування даних дозволяє скоротити змістовну частину алгоритму в кілька разів, а час його виконання - в десятки разів.

Однак невдало реалізоване сортування вхідних даних, здатна помітно знизити ефективність алгоритму в цілому. Тому якщо хороший і ефективний в цілому алгоритм програми, але він використовує " поганий" метод сортування, то програма може працювати досить повільно.

Методи впорядкування поділяються на внутрішні ( їоброблювальні масиви ) і зовнішні ( що займаються тільки файлами).

У курсовій роботі розглядаються методи внутрішнього сортування. Їх особливість полягає в тому, що ці алгоритми не вимагають додаткової пам'яті і вся робота з упорядкування проходить всередині одного і того ж масиву.

Придумано досить багато алгоритмів внутрішнього сортування, вони відрізняються різною швидкодією і вимагають різного обсягу додаткової пам'яті, а також відрізняються стійкістю збереження вихідного порядку однакових ключів.

Основні класи алгоритмів внутрішнього сортування наступні:

* Сортування вибіркою;

* Сортування вставкою;

* Сортування бульбашкою;

* Сортування методом Шела;

* Сортування за методом пірамід;

* Швидке сортування Хора;

Алгоритм швидкого сортування запропонував C.A.R.Hoare, сортування методом «Шелла» запропоноване - Donald L. Shell, вказати авторство інших, більш «очевидних» алгоритмів не представляється можливим. Всі ці алгоритми досить старі - до середини 60 -х років двадцятого століття вони були відомі.

Методи сортування характеризуються своєю складністю своїх дій. Однак потрібно враховувати, що кількість дій, необхідних для впорядкування деякої послідовності даних, залежить не тільки від довжини цієї послідовності, але і від її структури. Так, якщо на вхід подається вже впорядкована послідовність, то кількість дій буде значно менше, ніж у випадку невпорядкованих вхідних даних.

Складність алгоритмів підраховують окремо за кількістю порівнянь і за кількістю переміщень даних у пам'яті (пересилань), оскільки виконання цих операцій займає різний час. Однак точні значення вдається знайти рідко, тому для оцінки алгоритмів обмежуються лише поняттям "пропорційно", яке не враховує конкретні значення констант, що входять в підсумкову формулу. Загальну ж ефективність алгоритму зазвичай оцінюють як середнє арифметичне від складності алгоритму "в кращому випадку" і "в гіршому випадку".

До простих методів внутрішнього сортування відносять методи, складність яких пропорційна квадрату розмірності вхідних даних. Іншими словами, при сортуванні масиву, що складається з N компонент, такі алгоритми будуть виконувати С*N² дій, де С - деяка константа. Тобто складність простих сортировок складає ~N².

На відміну від простих сортировок, до поліпшених сортувань відносяться алгоритми з загальною складністю ~ N * logN.

На невеликих наборах сортируемих даних ( при N < 100 ) ефективність швидких сортировок не настільки очевидна: виграш стає помітним тільки при великих N. Отже, якщо необхідно відсортувати невеликий набір даних, то вигідніше застосувати методи простіші.

1.1.2 Призначення розробки

Експлуатаційне призначення даного програмного виробу полягає в створенні програми для сортування даних в одновимірних масивах.

Програмний виріб повинен бути написаний на мові програмування С.

1.1.3 Вимоги до програмного забезпечення

Для створення даної програми необхідна мова програмування C. Використання цієї мови програмування дозволяє з допомогою мінімальних зусиль створити якісний програмний продукт.

Програми написані на C складаються з модулів або фрагментів, називаються функціями. Оптимальним для середовища є блочний метод побудови програм, який на відміну від лінійного дозволяє використовувати стандартні функції для написання. Є такі види функцій:

· функції є стандартні (бібліотеки мови Сі);

· функції, які створює сам користувач;

· функції створені іншими користувачами;

· функції WinAPI;

Програма написана в цьому середовищі включає в себе ідентифікатори, ключові слова, функції, змінні, константи, вирази, директиви препроцесора і процесора, структури, масиви.

Існують стандартні потоки для вводу інформації з клавіатури, виводу даних на екран, а також для виклику в випадку виникнення помилки. Крім того, додатки підтримують роботу з стандартними потоками виведення на друк і додатковими консольними потоками. В загальному випадку кожен з перерахованих потоків може бути представлений як деякий віртуальний файл (байт-потік), закріплений за певним фізичним пристроєм. Стандартний потік входу/виходу може бути представлений так, щоб наприклад, вихід був не на екран, а в певний файл. Проект - це сукупність файлів, з яких складається Cі-програма.

Програмне забезпечення повинно бути простим та доступним і використанні та невимогливим до технічних характеристик персонального комп'ютера.

Водночас воно повинно забезпечувати надійність зберігання та безпеку даних.

Програма повинна працювати в операційних системах DOS та Windows. Вона не повинна використовувати багато дискового простору та ресурсів персонального комп'ютера.

Вхідні дані

Вхідними являються дані, введені користувачем. Ці дані використовується протягом всього процесу виконання програми.

Вихідні дані

Вихідні дані в цьому програмному продукті представлені виводом на екран. Джерелом вихідної інформації є дані зчитані з клавіатури та опрацьовані програмою.

1.1.4 Часові характеристики

Розроблений програмний продукт не повинен мати певних часових характеристик. Термін його використання залежить від терміну відповідності характеристик програмного забезпечення вимогам користувача. Але оскільки, він буде написаний на мові програмування С, а сама програма буде запускатися під операційною системою Windows, то час безперервної дії програмного виробу буде залежати від безперервної дії самої операційної системи Windows, яка, виходячи з твердження розробників, може нормально функціонувати потягом трьох діб.

1.1.5 Умови експлуатації

Дана програма повинна виконувати наступні функції:

· ввід початкових даних від користувача з клавіатури

· виведення необхідної інформації на екран у вигляді впорядкованих даних;

Програмне забезпечення не вимагає від користувача особливих навичок та знань. Користувач повинен лише володіти основними навичками роботи з персональним комп'ютером та використовуваною операційною системою Windows NT/ 7.

Для повноцінної роботи з програмою вона повинна знаходитися на жорсткому диску комп'ютера, флеш-носії чи іншому носії інформації,який забезпечить програмі можливість роботи з введеними даними.

Системні вимоги для даного програмного продукту:

· Операційна система: Windows NT, Windows 7/8;

· Процесор: 800 MHz і більше;

· Оперативна пам'ять: 128 Mb і більше;

· Місце на жорсткому диску: 10 Mb і більше;

· Управління: клавіатура, мишка;

1.1.6 Стадії та етапи розробки

Даний програмний продукт повинен мати наступні стадії розробки:

· визначення вимог до функцій та можливостей програми;

· створення блок-схеми, необхідної для подальшої розробки програми;

· створення в середовищі програмування С даного програмного продукту;

· тестування та налагодження роботи створеної програми;

· створення інструкції з експлуатації;

· написання технічної документації.

1.1.7 Порядок контролю та прийому

Тестування програми буде проводитись на базі ПК такої конфігурації апаратного та програмного забезпечення:

· встановлена операційна система: Windows 7;

· процесор: Процесор: AMD-A4-4300;

· оперативна пам'ять: 4 ГБ;

· відеокарта ATI Radeon HD Graphics, 1024 Mb;

2. РОЗРОБКА ТЕХНІЧНОГО ТА РОБОЧОГО ПРОЕКТУ

2.1 Постанова задачі на розробку програмного забезпечення

Метою даної курсової роботи є створення програми для використання алгоритмів сортування масивів різними ми способами.

Завдання сортування: Нехай є послідовність a₀, a₁... a_n і функція порівняння, яка на будь-яких двох елементах послідовності приймає одне з трьох значень: менше, більше або дорівнює. Завдання сортування полягає в перестановці членів послідовності таким чином, щоб виконувалася умова: a_i <= a_i+1, для всіх i від 0 до n.

2.2 Опис та обґрунтування вибору методу організації вхідних та вихідних даних

програмний інформаційний масив алгоритм

2.2.1 Вхідні дані

Вхідними являються дані, введені користувачем за допомогою графічного інтерфейсу, зокрема за допомогою графічного елемента випадаючий список (ComboBox) та кнопок.

Описані дані вводяться відповідно до натиснутих кнопок, а з випадаючого списку за допомогою наступних дій:

· Зчитування рядка з випадаючого списку

· Пошук вибраного рядка в файлі і запис в відповідну структуру програми

2.2.2 Вихідні дані

Вихідними даними являються повідомлення про помилки, та статус роботи відслідковуваної програми.

Для виводу помилок використовується вбудоване вікно MessageBox.

Вивід стану відслідковуваної програми відбувається в стрічку стану в нижній частині вікна. Яка в свою чергу складається з двох частин «Назва процесу» та «Стан процесу».

2.3 Опис методів реалізації функцій програми

Даний програмний продукт складається з основного тіла програми, де організовується ввід та вивід даних.

У даній програмі з допомогою дерективи #include підключаються наступні бібліотечні файли: stdio.h, mbstring.h, windows.h. З файлу stdio.h використовуються функції вводу-виводу, з файлу windows.h - використовуються функції WinApi. mbstring.h - робота з стрічками.

В програмному продукті використані одні з наступних функцій:

CreateWindow - створює перекриваюче, вискакуюче або дочірнє вікно. Вона визначає клас, заголовок, стиль вікна і (необов'язково) початкову позицію і розмір вікна. Функція також визначає і власника, якщо такі є, і меню вікна.

SendMessage - відправляє задане повідомлення вікну або вікнам. Функція викликає віконну процедуру для заданого вікна і не повертає значення до тих пір, поки віконна процедура не обробить повідомлення.

lstrcmp - порівнює два рядки символів. Порівняння залежно від регістру.

DefWindowProc - викликається віконною процедурою за замовчуванням, щоб забезпечити обробку за замовчуванням будь-якого повідомлення вікна, яке програма не обробляє. Ця функція гарантує те, що обробляється кожне повідомлення. Функція DefWindowProc викликається з тими ж самими параметрами, прийнятими віконної процедурою.

PostQuitMessage - вказує системі, що потік зробив запит на те, щоб завершити свою роботу (вийти). Це зазвичай використовується у відповідь на повідомлення WM_DESTROY.

Також в програмі реалізовані власні функції, опис яких подається в наступних розділах.

2.3.1 Головне вікно

Головне вікно даної програми призначене для зручного доступу до основних функцій програми. Головне вікно створюється за допомогою функції CreateWindow, наступним чином:

HWND CreateWindow (LPCTSTR lpClassName, // покажчик на зареєстроване ім'я класу  LPCTSTRlpWindowName, // покажчик на ім'я вікна  DWORDdwStyle, // стиль вікна  int x, //горизонтальна позиція вікна int y, // вертикальна позиція вікна int nWidth, // ширина вікна int nHeight, // висота вікна HWND hWndParent, // дескриптор батьківського або вікна власника HMENU hMenu, // дескриптор меню або ID дочірнього вікна HANDLE hInstance, // дескриптор екземпляра додатка LPVOID lpParam // покажчик на дані створення);

Параметри CreateWindow:

lpClassName

Вказує на рядок з нульовим символом в кінці або на атом класу, створений попереднім викликом функції RegisterClass або RegisterClassEx. Атом - 16- розрядне значення менше, ніж 0xC000, має бути в молодшому слові lpClassName ; старше слово повинно бути нульове. Якщо lpClassName - рядок, вона визначає ім'я класу вікна. Ім'я класу може бути будь-яким ім'ям, зареєстрованим функцією RegisterClass або RegisterClassEx за умови, що модуль, який реєструє клас, є також модулем, який створює вікно. Ім'я класу може також бути будь-яким із зумовлених системних імен класу. За списком системних імен класів, зверніться до розділу Зауважень.

lpWindowName

Вказує на рядок з нульовим символом на кінці, яка визначає ім'я вікна. Якщо стиль вона визначає область заголовка, заголовок вікна, зазначений lpWindowName відображається в області заголовка. Коли використовується функція CreateWindow, щоб створити органи управління, такі як кнопки, перемикачі і статичні елементи управління, параметр lpWindowName використовують, щоб встановити текст органу управління. При створенні статичного органу управління зі стилем SS_ICON, параметр lpWindowName використовуйте, щоб встановити ім'я піктограми або ідентифікатора. Щоб встановити ідентифікатор, використовуйте синтаксис "# num ".

dwStyle

Визначає стиль створюваного вікна. Цей параметр може бути комбінацією стилів вікна і стилів органів управління, позначених нище.

x

Визначає початкову горизонтальну позицію вікна. Для перекривання або відображення вікна, параметр x - початкова координата лівого верхнього кута вікна, в екранних координатах. Для дочірнього вікна x - координата лівого верхнього кута вікна щодо лівого верхнього кута робочої області батьківського вікна.

y

Визначає початкову вертикальну позицію вікна. Для перекривання або відображення вікна, параметр y - початкова координата лівого верхнього кута вікна, в екранних координатах. Для дочірнього вікна, y - початкова координата лівого верхнього кута дочірнього вікна щодо лівого верхнього кута робочої області батьківського вікна. Для вікна зі списком, y - координата лівого верхнього кута робочої області вікна зі списком щодо лівого верхнього кута робочої області батьківського вікна.

nWidth

Визначає ширину вікна в одиницях виміру для пристрою. Для перекриваючих вікон, nWidth є шириною вікна в екранних координатах.

nHeight

Визначає висоту вікна в одиницях виміру пристрою. Для вікон nHeight - висота вікна, в екранних координатах.

hWndParent

Дескриптор вікна батька або власника створюваного вікна. Правильний дескриптор вікна повинен бути виданий при створенні дочірнього вікна або вікна власника. Цей параметр є необов'язковим для вікон, що вискакують.

hMenu

Дескриптор меню або визначає ідентифікатор дочірнього вікна в залежності від стилю вікна. Для перекривання або вискакування вікна, hMenu ідентифікує меню, яке буде використовуватися з вікном ; якщо має використовуватися меню класу, він може бути значенням ПУСТО (NULL ). Для дочірнього вікна, параметр hMenu визначає ідентифікатор дочірнього вікна, цілочисельне значення, використовуване елементом управління діалогового вікна, щоб попереджати батьківське вікно про події. Прикладна програма визначає ідентифікатор дочірнього вікна; він повинен бути унікальним для всіх дочірніх вікон того ж самого батьківського вікна.

hInstance

Windows 95/98/Me : Дескриптор примірника модуля, який буде пов'язаний з вікном.

Windows NT/2000/XP : Це значення ігнорується.

lpParam

Вказує на значення, передане вікна через структуру CREATESTRUCT, передану в параметрі lParam повідомлення WM_CREATE. Якщо прикладна програма викликає CreateWindow, щоб створити робоче вікно багатодокументного інтерфейсу ( MDI ), lpParam повинен вказувати на структуру CLIENTCREATESTRUCT.

Список можливих стилів вікна dwStyle:

WS_BORDER - задає праметр вікна, який має тонку лінію рамки.

WS_CAPTION - задає праметр вікна, який має рядок заголовка (включає в себе стиль WS_BORDER ).

WS_CHILD - Створює дочірнє вікно. Цей стиль не може використовуватися зі стилем WS_POPUP.

WS_CHILDWINDOW - Те ж саме, що і стиль WS_CHILD.

WS_CLIPCHILDREN - Виключає область, зайняту дочірніми вікнами, коли промальовування відбувається всередині батьківського вікна. Цей стиль використовується при створенні батьківського вікна.

WS_CLIPSIBLINGS - Закріплює дочірні вікна відносно один одного, тобто коли окреме дочірнє вікно приймає повідомлення WM_PAINT, стиль WS_CLIPSIBLINGS закріплює всі інші дочірні вікна поза області дочірнього вікна, яку потрібно модифікувати. Якщо стиль WS_CLIPSIBLINGS не визначений, а дочірні вікна перекриваються, то, можливо, що при промальовуванні всередині робочої області дочірнього вікна, виводитиметься внутрішня робоча область сусіднього дочірнього вікна.

WS_DISABLED - задає праметр вікна, який спочатку заблоковано. Заблоковане вікно не може приймати інформацію від користувача.

WS_DLGFRAME - задає праметр вікна, який має стиль рамки, що часто використовується з діалоговими вікнами. Вікно з цим стилем не може мати рядок заголовка.

WS_GROUP - Визначає перший елемент керування у групі елементів управління. Група складається з цього першого елемента управління і всіх певних елементів управління після нього, до наступного елемента керування зі стилем WS_GROUP. Перший елемент управління в кожній групі зазвичай має стиль WS_TABSTOP, щоб користувач міг переміщатися з групи в групу. Користувач може згодом передавати фокус клавіатури від однієї групи елементів управління в наступну групу елементів управління, використовуючи клавіші зі стрілками.

WS_HSCROLL - задає праметр вікна, яке має горизонтальну лінійку прокрутки.

WS_ICONIC - задає праметр вікна, яке спочатку згорнуто. Той же самий стиль, що і WS_MINIMIZE.

WS_MAXIMIZE - задає праметр вікна, яке спочатку розгорнуто.

WS_MAXIMIZEBOX - задає праметр вікна, яке має кнопку Розгорнути (Maximize). Не може бути об'єднаний зі стилем WS_EX_CONTEXTHELP. До того ж має бути визначений стиль WS_SYSMENU.

WS_MINIMIZE - задає праметр вікна, яке спочатку згорнуто. Той же самий стиль, що і WS_ICONIC.

WS_MINIMIZEBOX - задає праметр вікна, яке має кнопку Згорнути (Minimize). Не може бути об'єднаний зі стилем WS_EX_CONTEXTHELP. До того ж має бути визначений стиль WS_SYSMENU.

WS_OVERLAPPED - Створює перекриваюче вікно. Перекриваюче вікно має рядок заголовка і рамку. Той же самий стиль, що і WS_TILED.

WS_OVERLAPPEDWINDOW - Створює перекриваюче вікно зі стилями WS_OVERLAPPED, WS_CAPTION, WS_SYSMENU, WS_THICKFRAME, WS_MINIMIZEBOX і WS_MAXIMIZEBOX. Той же самий, що і стиль WS_TILEDWINDOW.

WS_POPUP - Створює вискакуюче вікно. Цей стиль не може використовуватися зі стилем WS_CHILD.

WS_POPUPWINDOW - Створює вискакуюче вікно зі стилями WS_BORDER, WS_POPUP і WS_SYSMENU. Стилі WS_CAPTION і WS_POPUPWINDOW повинні бути об'єднані, щоб зробити меню вікна (window) видимим.

WS_SIZEBOX - задає праметр вікна, яке має установку розмірів рамки вікна. Той же самий, що і стиль WS_THICKFRAME.

WS_SYSMENU - задає праметр вікна, яке має меню вікна ( window - menu ) у його рядку заголовка. До того ж має бути визначений стиль WS_CAPTION.

WS_TABSTOP - Визначає елемент управління, який може приймати фокус клавіатури, коли користувач натискає клавішу табуляції ( TAB ). Натискання на клавіші табуляції передає фокус клавіатури на наступний елемент управління зі стилем WS_TABSTOP.

WS_THICKFRAME - задає праметр вікна, яке має установку розмірів рамки вікна. Те ж саме, що і стиль WS_SIZEBOX.

WS_TILED - Створює перекриваюче вікно. Перекриваюче вікно має рядок заголовка і рамку. Те ж саме, що і стиль WS_ OVERLAPPED.

WS_TILEDWINDOW - Створює перекриваюче вікно зі стилями WS_OVERLAPPED, WS_CAPTION, WS_SYSMENU, WS_THICKFRAME, WS_MINIMIZEBOX і WS_MAXIMIZEBOX. Те ж саме, що і стиль WS_ OVERLAPPEDWINDOW.

WS_VISIBLE - задає праметр вікна, яке є спочатку видимим.

WS_VSCROLL - задає праметр вікна, яке має вертикальну лінійку прокрутки.

Інші графічні елементи створюються за допомогою тієї ж функції CreateWindow, лише використовуються зареєстровані назви класів відповідно до створюваного елемента.

Список зареєстрованих назв класів графічних елементів:

Button ( Кнопка )

Позначає маленьке прямокутне дочірнє вікно, яке являє собою кнопку, у якій користувач може клацати мишею, щоб включити або виключити її. Кнопки управління можуть використовуватися самостійно або в групах, і вони можуть або бути підписані або з'являтися без тексту. Кнопки управління зазвичай змінюють свій вигляд, коли користувач клацає мишею по них.

Combobox ( Комбіноване Вікно )

Позначає елемент управління, з вікна зі списком і поля вибору, схожого на вікно редагування тексту. При використанні цього стилю, прикладна програма повинна або показувати на екрані вікно зі списком весь час або включати вікно списку, що розкривається.

Якщо вікно зі списком видиме, введення символів із клавіатури в поле вибору підсвічує перший запис вікна зі списком, яка відповідає символам, які вводяться з клавіатури. І, навпаки, при виборі пункту у вікні зі списком, на екрані, в поле вибору, показується вибраний текст.

Edit ( Вікно редагування тексту )

Позначає прямокутне дочірнє вікно, всередині якого користувач може надрукувати з клавіатури текст. Користувач вибирає орган управління і дає йому фокус клавіатури, клацаючи по ньому мишею або переміщаючи в нього, каретку шляхом натискання клавіші табуляції (TAB). Користувач може вводити текст, коли вікно редагування тексту відображає миготливу каретку (caret); використовуйте мишу, щоб переміщати курсор, для вибірки символи для заміни або установки курсору в позицію вставки символів ; або використовуйте клавішу ПОВЕРНЕННЯ НА ПОЗИЦІЮ (BACKSPACE), щоб видаляти символи

В головному вікні даного програмного продукту використовуються наступні елементи:

– Combobox ( Комбіноване Вікно);

– Вікно редагування тексту;

– Кнопка;

Блок-схема роботи функції WinMain (створення головного вікна) показана на рисунку 2.1.



Рисунок 2.1 - Блок-схема роботи функції WinMain (створення головного вікна)

2.3.2 Сортування масиву методом «бульбашки»

Ідея алгоритму сортування методом « бульбашки » наступна:

1. Беруться два поруч стоять елемента масиву, і якщо елемент з меншим індексом більше елемента з великим індексом, то вони міняються місцями.

2. Ці дії відбуваються до тих пір, поки маса не буде відсортований.

Алгоритм проходить по масиву від початку до кінця. У процесі роботи алгоритму знаходиться елемент з максимальним значенням, який поміщається в кінець масиву, тому кожен раз кількість переглядаються сортуванням елементів масиву зменшується на 1.

Щоразу на своє місце стає хоча б один елемент масиву, тому кількість проходів по ньому дорівнює кількості елементів в масиві.

Алгоритм називається бульбашковим, так як максимальний елемент масиву як би спливає наверх.

Більш формально алгоритм сортування методом « бульбашки » можна описати таким чином. Послідовно проглядаються числа a₁,..., a_n знаходиться найменше і таке, що a_i > a_i+1. Міняються місцями a_i і a_i+1, поновлюється перегляд з елемента a_i+1 і т.д. Тим самим найбільше число пересунеться на останнє місце. Наступні перегляди починаються знову спочатку, зменшуючи на одиницю кількість переглядаються елементів. Масив буде впорядкований після перегляду в якому брали участь тільки перший і другий елементи. Сортування бульбашкою дуже простий, компактний, але повільний алгоритм сортування.

Розглянемо метод сортування бульбашкою на прикладі. На рисунку 2.2 показаний масив, розташований зверху вниз, від нульового елемента - до останнього.



 Рисунок 2.2. Метод сортування «бульбашкою», нульовий прохід

Після нульового проходу по масиву " вгорі " виявляється самий " легкий" елемент. Наступний прохід робиться до другого зверху елемента, таким чином другий за величиною елемент піднімається на правильну позицію.

Проходи виконуються по все зменшується нижній частині масиву доти, поки в ній не залишиться тільки один елемент. На цьому сортування закінчується, так як послідовність впорядкована за зростанням (див. рис. 2.3). Середнє число порівнянь і обмінів мають квадратичний порядок росту : О ( N2), звідси можна зробити висновок, що алгоритм бульбашки дуже повільний і малоефективний.

Однак алгоритм сортування бульбашкою має величезний плюс: він простий в реалізації.

Рисунок 2.3 - Хід дій для сортування методом «бульбашки ».

Код програми:

int *bubble(int *a,int n,bool amb){

int c;

for(int x=(n-1); x>=1; x-=1)

for(int i=1; i<=x; i+=1)

if (sravni(a[i],a[i-1],amb)){

c=a[i];

a[i]=a[i-1];

a[i-1]=c;}

return(a);}

Алгоритм функції сортування методом бульбашки

Рисунок 2.4

2.3.4 Сортування масиву методом Шелла

Алгоритм сортування Шелла є вдосконаленим варіантом сортування вставками. Ідея методу Шелла полягає в порівнянні елементів, що стоять не тільки поруч, але і на певній відстані один від одного. Іншими словами - це сортування вставками з попередніми «грубими» проходами. Аналогічний метод удосконалення бульбашкового сортування називається сортування гребінцем.

При сортуванні Шелла спочатку порівнюються і сортуються між собою значення, віддалені один від одного на деякій відстані d. Після цього процедура повторюється для деяких менших значень d, а завершується сортування Шелла упорядкуванням елементів при d = 1 (тобто, звичайної сортуванням вставками). Ефективність сортування Шелла в певних випадках забезпечується тим, що елементи «швидше» встають на свої місця (в простих методах сортування, наприклад, бульбашки, кожна перестановка двох елементів зменшує кількість інверсій у списку максимум на 1, а при сортуванні Шелла це число може бути більше ).

На кожному кроці ( нехай змінна t зберігає номер цього кроку) потрібно провести наступні дії:

· вичленувати всі підпослідовності, відстань між елементами яких становить k_t;

· кожну з цих послідовностей впорядкувати методом вставки.

Знаходження спадної послідовності відстаней k_t, k_t-1..., k₁ становить головну проблему цього алгоритму. Численні дослідження дозволили виявити її обов'язкові властивості :

· k₁ = 1;

· для всіх t k_t > k_t-1;

· бажано також, щоб всі k_t були кратними одна одній ( для того, щоб не повторювалася обробка раніше відсортованих елементів).

Величина кроку d - називається приростом і є важливою характеристикою алгоритму Шелла. І вибір динаміки зменшення цієї величини дуже істотно позначається на продуктивності алгоритму в цілому, дозволяючи досягати пропорцій від ~ O(N^7/6) в кращому випадку до ~ O(N^4/3) в гіршому.

Головна вимога до приросту d, щоб на останній ітерації воно дорівнювало 1. Динаміка зміни цієї величини дуже істотно позначається на продуктивності алгоритму в цілому.

Очевидно, що програміст може вибрати будь-який алгоритм зменшення цього приросту на кожному кроці, головне, щоб врешті воно прийняло значення 1. Існує чимало стратегій розрахунку приросту на кожному проході алгоритму Шелла.

Наприклад, Р. Седжвік, запропонував таку схему обчислення збільшень:

d[i] = 9*2ⁱ - 9*2^i/2 + 1, якщо парно

d[i] = 8*2ⁱ - 6*2^(i+1)/2 + 1, якщо не парно

Було доведено, що використовуючи цю схему продуктивність алгоритму зростає ~ O(n^7/6)в середньому і ~ O(n^4/3) в гіршому випадку. При розрахунку збільшень за цим методом зупинятися слід на значенні d [ i - 1 ], якщо 3 * d [ i ] > n. Зазвичай розрахунок починається з нульових значень i ( = [ 0,1,2...] ) і триває до такого i, коли 3 * d [ i +1 ] > n, як було сказано раніше. Т.ч. дана процедура розрахунку запускається перед самою сортуванням Шелла і потім зберігає отриману таблицю збільшень в пам'яті, а алгоритм сортування на кожному кроці до неї звертається за черговим значенням.

Дональд Кнут пропонує дві "хороші" послідовності відстаней:

1, 4, 13, 40, 121, _ (k_t = 1+3*k_t-1)

1, 3, 7, 15, 31, _ (k_t = 1+2*k_t-1 = 2^t -1)

Перша з них підходить для сортувань досить довгих масивів, друга ж більш зручна для коротких.

Незважаючи на те, що сортування Шелла в багатьох випадках повільніше, ніж швидке сортування, вона має ряд переваг:

* відсутність потреби в пам'яті під стек;

* відсутність деградації при невдалих наборах даних - швидке сортування легко деградує до O ( n І ), що гірше, ніж найгірше гарантований час для сортування Шелла.Розглянемо наступний алгоритм сортування масиву a [ 0 ].. a [ 15 ] (див. рис. 2.5).

рисунок 2.5 - Вихідний масив для сортування методом Шелла.

1.Спочатку сортуємо простими вставками кожні 8 груп з 2 -х елементів ( a [ 0 ], a [ 8 [ ), ( a [ 1 ], a [ 9 ]),..., ( a [ 7 ], a [ 15 ] ) (див. рис. 2.6). 

Рисунок 2.6 Перший прохід сортування Шелла

2.Потім сортуємо кожну з чотирьох груп по 4 елементи ( a [ 0 ], a [ 4 ], a [ 8 ], a [ 12 ]),..., ( a [ 3 ], a [ 7 ], a [ 11 ], a [ 15 ] ) (див. рис. 2.7) 

Рисунок 2.7 Другий прохід сортування Шелла.

У нульовий групі будуть елементи 4, 12, 13, 18, в першій - 3, 5, 8, 9 і т.п.

3. Далі сортуємо 2 групи по 8 елементів, починаючи з ( a [ 0 ], a [ 2 ], a [ 4 ], a [ 6 ], a [ 8 ], a [ 10 ], a [ 12 ], a [ 14 ] ) (див. рис. 2.8 ). 



Рисунок 2.8 Третій прохід сортування Шелла

4. Наприкінці сортуємо вставками всі 16 елементів. 

Рисунок 2.9 Закінчення сортування Шелла

Код програми:

int *shell(int *a,int n,bool amb){

bool c;

int e,g,i,j;

int tmp;

n = n-1;

g = (n+1)/2;

do{i = g;

do{j = i-g;

c = true;

do{if(sravni(a[j]-1,a[j+g],amb)){

c = false;}

else{

tmp = a[j];

a[j] = a[j+g];

a[j+g] = tmp;}

j = j-1;}

while(j>=0&&c);

i = i+1;}

while(i<=n);

g = g/2;}

while(g>0);

return a;}

2.3.5 Сортування масиву методом вибірки

Один з найпростіших методів сортування працює в такий спосіб: знаходимо найменший елемент у масиві й обмінюємо його з елементом, якій знаходиться на першому місці, потім повторюємо процес із другої позиції у файлі і знайдений елемент обмінюємо з другим елементом і так далі поки весь масив не буде відсортований. Цей метод називається сортування вибором оскільки він працює циклічно вибираючи найменший з елементів, що залишилися.

В міру просування покажчика і ліворуч праворуч через файл, елементи ліворуч від покажчика знаходяться вже в своїй кінцевій позиції (і їхній не будуть більше вже чіпати), тому масив стає цілком відсортованим до того моменту, коли покажчик досягає правого краю.

Цей метод працює дуже добре для невеликих файлів. Його "внутрішній цикл" складається з порівняння a[і]<a[mіn] (плюс код необхідний для збільшення j та перевірки на те, що він не перевищив N), що навряд чи можна ще спростити.

Більш того, незважаючи на те, що цей метод очевидно є методом "грубої сили", він має дуже важливе застосування: оскільки кожен елемент пересувається не більш ніж раз, тому він дуже зручний для великих записів з маленькими ключами.

Якщо довжина нашого масиву дорівнює n, то нам потрібно пройтися по n - 1 елементам. Щораз нам може знадобитися зсунути n - 1 інших елементів. От чому цей метод вимагає таки багато часу. Сортування вставками відноситься до числа методів сортування по місцю. Іншими словами, їй не потрібно допоміжна пам'ять, ми сортуємо елементи масиву, використовуючи тільки пам'ять, яку займає сам масив. Крім того, вона є стійкою ? якщо серед ключів, які ми сортируємо є однакові, після сортування вони залишаються у вихідному порядку.

При сортуванні масиву a[1], a[2],..., a[n] методом простого вибору серед всіх елементів знаходиться елемент із найменшим значенням a[і], після чого елементи a[1] та a[і] обмінюються значеннями. Потім цей процес повторюється для одержуваних підмасивів a[2], a[3],..., a[n],... a[j], a[j+1],..., a[n] доти, поки ми не дійдемо до підмасива a[n], що має до цього моменту найбільше значення. Робота алгоритму ілюструється прикладом наведеним нижче у таблиці.

Приклад сортування вибором:

Початковий стан масиву 8 23 5 65 44 33 1 6

Крок 1 1 23 5 65 44 33 8 6

Крок 2 1 5 23 65 44 33 8 6

Крок 3 1 5 6 65 44 33 8 23

Крок 4 1 5 6 8 44 33 65 23

Крок 5 1 5 6 8 33 44 65 23

Крок 6 1 5 6 8 23 44 65 33

Крок 7 1 5 6 8 23 33 65 44

Крок 8 1 5 6 8 23 33 44 65

Для методу сортування простим вибором необхідне число порівнянь - n*(n-1)/2. Порядок необхідного числа пересилань (включаючи ті, котрі вимагаються для вибору мінімального елемента) у гіршому випадку складає O(n2). Однак порядок середнього числа пересилань є O(n*ln n), що в ряді випадків робить цей метод кращим.

Код програми:

int *select(int *a,int n,bool amb){

int min;

int c;

for(int i=0;i<n-1;i+=1){

min=i;

for(int j=i;j<n;j+=1)

if(sravni(a[j],a[min],amb))min=j;

if(min!=i){

c=a[i];

a[i]=a[min];

a[min]=c;}

}

return a;

}

Алгоритм функції сортування вибором зображено на рисунку 2.9

Рисунок 2.10

2.3.6 Сортування масиву методом вставки

Сортування вставкою ? це метод який майже настільки ж простий, що і сортування вибором, але більш гнучкий. Цей метод часто використовують при сортуванні карт: беремо один елемент і вставляємо його в потрібне місце серед тих, що ми вже відібрали (тим самим залишаючи їх відсортованими).

int *bininsert(int *a,int n,bool amb)

{

int x,left,right,sred;

for(int i=1;i<n;i+=1)

if(sravni(a[i-1],a[i],!amb))

{x=a[i];

left=0;

right=i+1;

while(left<=right){

sred=left;

if(sravni(a[sred],x,amb)) left=sred+1;

else right=sred-1;

}

for(int j=i-1;j>=left;j-=1) a[j+1]=a[j];

a[left]=x;

}

return(a);

}

Також як і в сортуванні вибором, у процесі сортування елементи зліва від покажчика i знаходяться вже у відсортованому порядку, але вони не обов'язково знаходяться у своїй останній позиції, оскільки їх ще можуть пересунути праворуч щоб вставити більш маленькі елементи, які зустрілись пізніше.. Однак масив стає цілком відсортованим, коли покажчик досягає правого краю.

Сортування простими вставками в чомусь схожа на вищевикладений методи сортування вибором. Аналогічним чином робляться проходи по частині масиву, і аналогічним же чином у його початку "виростає" відсортована послідовність... Однак у сортуванні вибором можна було чітко заявити, що на і-м кроці елементи a[0]...a[і] розташовані на остаточних місцях і нікуди більш не перемістяться. Тут же подібне твердження буде більш слабким: послідовність a[0]...a[і] впорядкована. При цьому по ходу алгоритму в нее будуть вставлятися (див. назва методу) все нові елементи.

Будемо розбирати алгоритм, розглядаючи його дії на і-му кроці. Як говорилося вище, послідовність до цього моменту розділена на дві частини: готову a[0]...a[і] і невпорядковану a[і+1]...a[n]. На наступному, кожному (і+1)-му кроці алгоритму беремо a[і+1] елемент і вставляємо на потрібне місце в готову частину масиву. Пошук придатного місця для чергового елемента вхідної послідовності здійснюється шляхом послідовних порівнянь з елементам, що стоять перед ним. У залежності від результату порівняння елемент або залишається на поточному місці (вставка довершена), або вони міняються місцями і процес повторюється.

Таким чином, у процесі вставки ми "просіваємо" елемент x до початку масиву, зупиняючи у випадку, коли

1.Знайдено елемент, менший x або

2.Досягнутий початок послідовності.

Аналогічно сортуванню вибором, середнє, а також гірше число порівнянь і пересилань оцінюються як Theta (n2), додаткова пам'ять при цьому не використовується.

Гарним показником або, краще сказати, перевагою даного методу сортування є те, що : майже відсортований масив буде досортирован дуже швидко. Це, разом із стійкістю алгоритму, робить метод достойним вибором у відповідних ситуаціях.

Алгоритм можна дещо поліпшити. Помітимо, що на кожнім кроці внутрішнього циклу перевіряються дві умови. Можна об'єднати їх в одну умову, поставивши в початок масиву спеціальний „сторожовий елемент”. Він повинний бути свідомо менше всіх інших елементів масиву.

Тоді при j=0 буде свідомо вірно a[0] <= x. Цикл зупиниться на нульовому елементі, що і було метою умови j>=0.

Таким чином, сортування буде відбуватися вірним чином, а у внутрішньому циклі стане на одне порівняння менше. З обліком того, що воно вироблялося Theta(n2) раз, це - реальна перевага. Однак, відсортований масив буде не повний, тому що з нього зникло перше число. Для закінчення сортування це число варто повернути назад, а потім вставити у відсортовану послідовність a[1]...a[n].

Подальшим розвитком методу сортування вставками є сортування методом Шелла, інша назва сортування вставками зі зменшенням відстані. Ми не будемо описувати алгоритм у загальному виді, а обмежимося випадком, коли число елементів у масиві, який треба відсортувати є ступенем числа 2. Для масиву з 2n елементами алгоритм працює в такий спосіб. На першій фазі відбувається сортування включенням усіх пар елементів масиву, відстань між який дорівнює 2(n-1). На другій фазі виробляється сортування включенням елементів отриманого масиву, відстань між який дорівнює 2(n-2). І так далі, поки ми не дійдемо до фази з відстанню між елементами, рівної одиниці, і не виконаємо завершальне сортування з включеннями. Застосування методу Шелла до массиву наведено в наступному прикладі.

Приклад сортування методом Шелла:

Початковий вигляд масиву 8 23 5 65 44 33 1 6

Фаза 1 (сортуються елементи, відстань між якими дорівнює чотири)

8 23 5 65 44 33 1 6

8 23 5 65 44 33 1 6

8 23 1 65 44 33 5 6

8 23 1 6 44 33 5 65

Фаза 2 (сортуються елементи, відстань між якими дорівнює два)

1 23 8 6 44 33 5 65

1 23 8 6 44 33 5 65

1 23 8 6 5 33 44 65

1 23 5 6 8 33 44 65

1 6 5 23 8 33 44 65

1 6 5 23 8 33 44 65

1 6 5 23 8 33 44 65

Фаза 3 (сортуються елементи, відстань між якими дорівнює одиниці)

1 6 5 23 8 33 44 65

1 5 6 23 8 33 44 65

1 5 6 23 8 33 44 65

1 5 6 8 23 33 44 65

1 5 6 8 23 33 44 65

1 5 6 8 23 33 44 65

1 5 6 8 23 33 44 65

У загальному випадку алгоритм Шелла природно переформулюється для заданої послідовності з t відстаней між елементами h1, h2,..., ht, для яких виконуються умови h1 = 1 і h(і+1) < hі. Дональд Кнут показав, що при правильно підібраних t і h складність алгоритму Шелла є O(n(1.2)), що істотно менше складності простих алгоритмів сортування.

2.3.7 Сортування масиву методом пірамід

Отже, ми поступово переходимо від більш-менш простих до складних, але ефективних методів сортування. Пірамідальне сортування є першим з розглянутих методів, швидкодія яких оцінюється як O(n log n). Як деяку прелюдію до основного методу, розглянемо перевернене сортування вибором. Під час проходу, замість вставки найменшого елемента в лівий кінець масиву, будемо вибирати найбільший елемент, а готову послідовність будувати в правому кінці. Приклад дій для масиву a[0]... a[7]:

44 55 12 42 94 18 06 67 початковий масив

44 55 12 42 67 18 06 |94 94 <-> 67

44 55 12 42 06 18 |67 94 67 <-> 06

44 18 12 42 06 |55 67 94 55 <-> 18

06 18 12 42 |44 55 67 94 44 <-> 06

06 18 12 |42 44 55 67 94 42 <-> 42

06 12 |18 42 44 55 67 94 18 <-> 12

06 |12 18 42 44 55 67 94 12 <-> 12

Вертикальною рискою відзначена ліва границя уже відсортованої (правої) частини массиву.

Розглянемо оцінку кількості операцій докладніше.Усього виконується n кроків, кожний з який складається у виборі найбільшого елемента з послідовності a[0]..a[і] і наступному обміні. Вибір відбувається послідовним перебором елементів послідовності, тому необхідний на нього час: O(n). Отже, n кроків по O(n) кожний - це O(n2).Зробимо удосконалення: побудуємо структуру даних, що дозволяє вибирати максимальний елемент послідовності не за O(n), а за O(logn) часу. Тоді загальна швидкодія сортування буде n*O(logn) = O(n log n). Ця структура також повинна дозволяти швидко вставляти нові елементи (щоб швидко її побудувати з вихідного масиву) і вилучати максимальний елемент (він буде міститися у вже відсортованій частині масиву ? його правому кінеці). Отже, назвемо пірамідою (Heap) бінарне дерево висоти k, у якому:

* усі вузли мають глибину k або k-1 - дерево збалансоване;

* при цьому рівень k-1 цілком заповнений, а рівень k заповнений зліва направо, тобто форма піраміди має приблизно такий вигляд:

* виконується "властивість піраміди": кожен елемент менше, або дорівнює батьку.

Як зберігати піраміду? Найменш клопітно - помістити її в масив. Відповідність між геометричною структурою піраміди як дерева і масивом установлюється за наступною схемою:

· в a[0] зберігається корінь дерева;

· лівий і правий сини елемента a[і] зберігаються, відповідно, в a[2і+1] і a[2і+2].

Таким чином, для масиву, що зберігає в собі піраміду, виконується наступне характеристична властивість: a[і] >= a[2і+1] і a[і] >= a[2і+2]. Плюси такого збереження піраміди очевидні:

· ніяких додаткових змінних, потрібно лише розуміти схему;

· вузли зберігаються від вершини і далі вниз, рівень за рівнем;

· вузли одного рівня зберігаються в масиві зліва направо.

Фаза 1 сортування: побудова піраміди

Розпочати побудову піраміди можна з a[k]...a[n], k = [sіze/2]. Ця частина масиву задовольняє властивості піраміди, тому що не існує індексів і,j: і = 2і+1 ( чи j = 2і+2 )... Просто тому, що такі і,j знаходяться за межами масиву. Варто помітити, що невірно говорити про те, що a[k]..a[n] є пірамідою як самостійний масив. Це, узагалі говорячи, не вірно: його елементи можуть бути будь-якими. Властивість піраміди зберігається лише в рамках вихідного, основного масиву a[0]...a[n]. Далі будемо розширювати частину масиву, що володіє настільки корисною властивістю, добавляючи по одному елементу за крок. Наступний елемент на кожнім кроці додавання ? той, котрий стоїть перед уже готовою частиною. Щоб при додаванні елемента зберігалася пірамідальність, будемо використовувати наступну процедуру розширення піраміди a[і+1]..a[n] на елемент a[і] вліво:

1.Дивимося на синів ліворуч і праворуч - у масиві це a[2і+1] і a[2і+2] і вибираємо найбільшого з них.

2.Якщо цей елемент більше a[і] - змінюємо його з a[і] місцями і йдемо до кроку 2, маючи на увазі нове положення a[і] у масиві. Інакше кінець процедури. Новий елемент "просівається" крізь піраміду.

Нижче дана ілюстрація процесу сортування для піраміди з 8-и елементів:

44 55 12 42 // 94 18 06 67 праворуч - частина масиву, що задовольняє 44 55 12 // 67 94 18 06 42 властивості піраміди,

44 55 // 18 67 94 12 06 42

44 // 94 18 67 55 12 06 42 інші елементи додаються

// 94 67 18 44 55 12 06 42 один за іншим, справа наліво.

У геометричній інтерпретації ключі з початкового відрізка a[sіze/2]...a[n] є листами в бінарному дереві, як зображено нижче. Один за одним інші елементи просуваються на свої місця, і так ? поки не буде побудована вся піраміда. На малюнках нижче зображений процес побудови. Неготова частина піраміди (початок масиву) пофарбована в білий колір, що задовольняє властивості піраміди, кінець масиву ? у темний.

2.3.8 Метод швидкого сортування Хоара

Основа алгоритму швидкого сортування була розроблена в 1960 році (C.R.Hoare) і з тих пір уважно вивчалася багатьма людьми. Швидке сортування особливо популярне через легкість його реалізації; це досить гарний алгоритм загального призначення, що добре працює у багатьох ситуаціях, і використовує при цьому менше ресурсів, чим інші алгоритми.

Загальна схема медоту швидкого сортування така:

1.з масиву вибирається деякий опорний елемент a[і];

2.запускається процедура поділу масиву, що переміщає всі ключі, менші, або рівні a[і], вліво від нього, а всі ключі, більші, або рівні a[і] - вправо;

3.тепер масив складається з двох підмножин, причому ліва менше, або дорівнює правій;

4.для обох підмасивів: якщо в підмасиві більш двох елементів, рекурсивно запускаємо ту ж процедуру.

Наприкінці вийде цілком відсортована послідовність.

Розглянемо алгоритм докладніше.

Нехай нам дано масив a[0]...a[N] і опорний елемент p, по якому буде відбуватися поділ.

1.Уведемо два покажчики: і та j. На початку алгоритму вони вказують, відповідно, на лівий і правий кінець послідовності.

2.Будемо рухати покажчик і з кроком у 1 елемент у напрямку до кінця масиву, поки не буде знайдений елемент a[і] >= p. Потім аналогічним образом почнемо рухати покажчик j від кінця масиву до початку, поки не буде знайдений a[j] <= p.

3.Далі, якщо і <= j, міняюємо a[і] та a[j] місцями і продовжуємо рухати і,j по тим же правилам...

4.Повторюємо крок 3, поки і <= j.

Розглянемо роботу процедури для масиву a[0]...a[6] та опорного елемента p = a[3].

Тепер масив розділений на дві частин: всі елементи лівої менше або рівні p, всі елементи правої - більше, або рівні p. Поділ завершений.

Основні переваги цього алгоритму полягають у тому, що він крапковий (використовує лише невеликий додатковий стек), у середньому вимагає тільки біля N log N операцій для того, щоб відсортувати N елементів, і має екстремально короткий внутрішній цикл. Недоліки алгоритму полягають у тому, що він рекурсивен (реалізація дуже утруднена коли рекурсія недоступна), у гіршому випадку він вимагає N2 операцій, крім того він дуже "тендітний": невелика помилка в реалізації, що легко може пройти непоміченою, може призести до того, що алгоритм буде працювати дуже погано на деяких файлах.

Продуктивність швидкого сортування добре вивчена. Алгоритм піддавався математичному аналізу, тому існують точні математичні формули, які стосуються питань його продуктивності. Результати аналізу були неодноразово перевірені емпіричними шляхом, і алгоритм був відпрацьований до такого стану, що став найбільш вживаним для широкого спектра задач сортування. Усе це робить алгоритм вартим більш детального вивчення найбільш ефективних шляхів його реалізації. Схожі способи реалізації підходять також і для інших алгоритмів, але в алгоритмі швидкого сортування ми можемо використовувати їх із упевненістю, оскільки його продуктивність добре вивчена.

Поліпшити алгоритм швидкого сортування є великою спокусою: більш швидкий алгоритм сортування - це своєрідна "мишоловка" для програмістів. Майже з того моменту, як Hoare вперше опублікував свій алгоритм, у літературі стали з'являтися "поліпшені" версії цього алгоритму. Було випробувано і проаналізовано безліч ідей, але все рівно дуже просто помилитися, оскільки алгоритм настільки добре збалансований, що результатом поліпшення в одній його частині може стати більш сильне погіршення в іншій його частині.

Суть алгоритму: число операцій зміни місць розташування елементів всередині масиву значно скоротиться, якщо змінювати місцями далеко розташовані один від одного елементи. Для цього вибирається для порівняння один елемент х, відшукується ліворуч перший елемент, що не менше х, а праворуч перший елемент, що не більше х. Знайдені елементи міняються місцями. Після першого ж проходу всі елементи, що менше х, будуть стояти ліворуч від х, а всі елементи, що більше х, ? праворуч від х. З двома половинами масиву роблять аналогічно. Продовжуючи розподіл цих половин доти поки не залишиться в них по 1 елементу.

...