Зміст
Вступ    3
1. Сортування    4
2. Метод сортування вибором    8
3. Сортування вставкою    10
4. Пірамідальне сортування    13
5. Бульбашкове сортування    16
6. Метод швидкого сортування.    18
7. Висновки    23
8. Література    24

Вступ
В наш час нові інформаційні технології посідають дуже важливе місце не лише в спеціалізованих, але й в повсякденних сферах життя. Комп’ютери застосовуються  в бізнесі, менеджменті, торгівлі, навчанні та багатьох інших сферах діяльності людини. Нові інформаційні технології дуже актуальні в наш час і потребують багато уваги для подальшої розробки та вдосконалення. Поряд з цим, велике значення має також і програмування, яке є одним із фундаментальних  розділів інформатики і тому не може залишатись осторонь.
Програмування містить цілу низку важливих внутрішніх задач. Однією з найбільш важливих таких задач для програмування є задача сортування. Під сортуванням звичайно розуміють перестановки елементів будь-якої послідовності у визначеному порядку. Ця задача є однією з найважливіших тому, що її метою є полегшення подальшої обробки  певних даних  і, насамперед, задачі пошуку. Так, одним з ефективних алгоритмів пошуку є бінарний пошук. Він працює швидше ніж, наприклад, лінійний пошук, але його можливо застосовувати лише за умови, що послідовність вже упорядкована, тобто відсортована.
Взагалі, відомо, що в будь-якій сфері діяльності, що використовує комп’ютер  для запису, обробки та збереження інформації, усі дані зберігаються в базах даних, які також потребують сортування. Певна впорядкованість для них дуже важлива, адже користувачеві набагато легше працювати з даними, що мають певний порядок. Так, можна розташувати всі товари по назві або відомості про співробітників чи студентів за прізвищем або роком народження, тощо.
Задача сортування в програмуванні не вирішена повністю. Адже, хоча й існує велика кількість алгоритмів сортування, все ж таки метою програмування є не лише розробка алгоритмів сортування елементів, але й розробка саме ефективних алгоритмів сортування. Ми знаємо,  що одну й ту саму задачу можна вирішити за допомогою різних алгоритмів і кожен раз зміна алгоритму приводить до нових, більш або менш ефективних розв’язків  задачі. Основними вимогами до ефективності алгоритмів сортування є перш за все ефективність за часом та економне використання пам’яті.
Метою нашої дослідницької роботи є ознайомлення з методами впорядкування об’єктів, а саме алгоритмами сортування, спроба проаналізувати їх і висвітлити кожен з них. Також метою даної курсової роботи є порівняльний аналіз основних методів сортування, використовуваних для обробки даних, вивчення характеристик і особливостей кожного алгоритму сортування.

1. Сортування.
Сортування (sortіng) − процес, що дозволяє впорядкувати безліч подібних даних у зростаючому або спадаючому порядку.
Алгоритми сортування добре досліджені і вивчені. Різні підходи до сортування мають різні характеристики. Хоча деякі методи в середньому можуть бути краще інших, жоден з методів не буде ідеальним для всіх ситуацій, тому кожен програміст повинен мати у своєму розпорядженні кілька різних типів сортування.
Сортування застосовується в усіх без винятку областях програмування, будь-то бази даних чи математичні програми.
Практично кожен алгоритм сортування можна розбити на три частини:
- порівняння, що визначає впорядкованість пари елементів;
- перестановку, що змінює місцями пару елементів;
- власне сортуючий алгоритм, що здійснює порівняння і перестановку елементів доти, поки всі елементи множини не будуть впорядковані.
Подібними властивостями володіють і ті п'ять алгоритмів сортування, що розглянуті нижче. Вони відібрані з безлічі алгоритмів, тому що:
по-перше, найбільш часто використовуються;
по-друге, тому що більшість інших алгоритмів є різними модифікаціями описаних нижче алгоритмів.
Існує два види алгоритмів сортування: сортування масивів, що можуть знаходитися як в операційній пам'яті, так і на диску у вигляді файлу прямого доступу, і сортування послідовних файлів, що знаходяться на дисках чи магнітних стрічках. В даній курсовій розглядаються в основному сортування першого виду, оскільки воно становить найбільший інтерес для користувачів комп'ютерів.
Основна відмінність між сортуванням масивів і сортуванням послідовних файлів полягає в тому, що кожен елемент масиву є доступним у будь-який час. Це значить, що в будь-який час будь-який елемент масиву може порівнюватися з будь-яким іншим елементом масиву і будь-які два елементи масиву можуть мінятися місцями. Напроти, у послідовному файлі в будь-який момент часу досяжний лише один елемент. Через ці відмінності методи сортування істотно відрізняються для цих двох видів сортування. У загальному випадку при сортуванні даних тільки частина інформації використовується як ключ сортування, що використовується для порівнянь. Коли виконується обмін, передається вся структура даних. Наприклад, у списку поштових відправлень як ключ сортування може використовуватися поштовий індекс, а в операціях обміну до поштового індексу додаються повне ім'я й адреса.
В даній курсовій роботі спочатку будуть розглядатись деякі "элеметарные" методи, які добре працюють для невеликих файлів чи файлів спеціальної структури. Існує кілька причин по яким бажане вивчення цих простих методів.
По-перше, вони дають нам відносно безболісний спосіб вивчити термінологію й основні механізми роботи алгоритмів сортування, що дозволяє одержати необхідну базу для вивчення більш складних алгоритмів.
По-друге, для багатьох задач сортування буває краще використовувати прості методи, чим більш складні алгоритми. І нарешті деякі з простих методів можна розширити до більш кращих методів або використовувати їх для поліпшення більш складних.
Як було зазначено раніше, у деяких програмах сортування краще використовувати прості алгоритми. Програми сортування часто використовуються тільки один раз (або кілька разів). Якщо кількість елементів, які потрібно відсортувати не велика (скажімо менше ніж 500 елементів), то можливо, що використання простого алгоритму буде більш ефективним, чим розробка і налагодження складного алгоритму. Елементарні методи завжди придатні для маленьких файлів (скажімо менших чим 50 елементів); малоймовірно, що складний алгоритм було б розумно використовувати для таких файлів, якщо звичайно не потрібно сортувати велику кількість таких файлів.
Як правило, елементарні методи, що ми будемо обговорювати, роблять приблизно N2 операції для сортування N довільно узятих елементів. Якщо N досить маленьке, то це може і не бути проблемою, і якщо елементи розподілені не довільним чином, то ці алгоритми можуть працювати навіть швидше, ніж складні. Однак варто запам'ятати те, що ці алгоритми не слід використовувати для великих, довільно впорядкованих файлів.
Перед тим, як розглядати який-небудь конкретний алгоритм, було б корисно вивчити термінологію і деякі основні положення про алгоритми сортування.
Під сортуванням розуміють, процес перестановки об'єктів множини у визначеному порядку. Метою алгоритму сортування є переорганізація записів у файлі так, щоб вони розташовувалися в ньому в якому-небудь строго визначеному порядку (звичайно в алфавітному чи числовому).
Нехай нам дана послідовність елементів: a1, a2, ..., an сортування означає − перестановку цих елементів у такому порядку:    ak1,ak2, .. ,akn, що при заданій функції впорядкування f(x), справедливе відношення :
f(ak1) <=    f(ak2)<= ..    <= f(akn) - функція впорядкування не обчислюється, а міститься в кожному елементі у вигляді явного компонента і її значення називають ключем елемента. Отже, для представлення і-ого елемента послідовності щонайкраще  підходить структура запису. Ключі є тільки частиною запису (часто дуже маленькою їх частиною), використовуються для керування процесом сортування.
Якщо файл, що сортується цілком міститься в пам'ять або цілком міститься в масиві, то для нього ми використовуємо внутрішні методи сортування. Сортування даних з диска чи стрічки називають зовнішнім сортуванням.
Одна з головних характеристик, що буде нас цікавити в алгоритмі - це час його роботи. Час роботи алгоритму характеризується числом необхідних порівнянь.
Прості алгоритми для сортування N елементів потребують час роботи пропорційний N2, у той час як більш складні алгоритми використовують час пропорційний NlogN. (Можна довести, що ніякий алгоритм сортування не може використовувати менш, ніж NlogN порівнянь між ключами.)
Мірою ефективності алгоритму внутрішнього сортування є число необхідних порівнянь значень ключа (C) і число перестановок елементів (M).
Кількість додаткової пам'яті,яку використовує алгоритм сортування − це ще один важливий фактор, що ми будемо враховувати. Взагалі кажучи, методи сортування поділяються на три типи(за часом):
1. методи сортування, які сортують без використання додаткової пам'яті, за винятком, можливо, невеликого стека або масиву;
2.методи, які використовують для сортування зв'язані списки і тому використовують N додаткових покажчиків, які зберігаються в пам'яті;
3.методи, що мають потребу в додатковій пам'яті для збереження копії сортуемого файлу.
Стабільність − ще одна не менш важлива характеристика методів сортування. Метод сортування називається стабільним якщо він зберігає відносний порядк слідування записів з однаковими ключами.
Наприклад, якщо алфавітний список групи сортується по оцінках, то стабільний метод створює список у якому прізвища студентів з однаковими оцінками будуть впорядковані за алфавітом, а нестабільний метод створить список в якому, можливо, вихідний порядок буде порушений.
Більшість простих методів стабільні, у той час як більшість добре відомих складних методів − ні. Якщо стабільність необхідна, то вона може бути досягнута за допомогою додавання до ключа невеликого індексу перед  сортуванням чи за допомогою подовження, яким-небудь чином, ключа.
Наступна програма, для сортування трьох записів, призначена для ілюстрації основних угод, що ми будемо використовувати. Зокрема , головна програма цікава тим, що вона працює тільки для N=3; справа в тім, що будь-яка програма сортування може бути зведена до процедури sort3 цієї програми. Три оператори присвоєння, кожний з який супроводжується оператором іf реалізують операцію "обміну". Ми вставляємо її безпосередньо в програмний код замість використання виклику процедури, оскільки вони є основою багатьох алгоритмів і часто попадає всередину циклу.
В основному програми сортування працюють із записами двома способами: або вони порівнюють і сортують тільки ключі, або пересувають запис цілком.
Якщо записи, що сортуються досить великі, то звичайно намагаються уникнути їхнього пересування за допомогою "непрямого сортування": при цьому самі записи не впорядковуються, а впорядковується масив покажчиків (індексів), так, що перший покажчик указує на самий маленький елемент і так далі. Ключі можуть зберігатися або з записами (якщо вони великі), або з покажчиками (якщо вони маленькі).
Програма демонструє основні принципи роботи з масивом і сортує 3 елементи.
program treesort;
const max=100;
var a : array [1..max] of іnteger; N, і : іnteger;
procedure Sort3;
var t:іnteger;
begіn
іf ( a[1] > a[2] ) then
begіn
t := a[1];
a[1] := a[2];
a[2] := t;
end;
іf ( a[1] > a[3] ) then
begіn
t := a[1];
a[1] := a[3];
a[3] := t;
end;
іf ( a[2] > a[3] ) then
begіn
t := a[2];
a[2] := a[3];
a[3] := t;
end;
end;
begіn
readln( N );
for і:=1 to N do read(a[і]);
іf N=3 then sort3;
for і:=1 to N do
wrіte(a[і]);
wrіteln;
end;
Отже, з термінологію і деякими основними положеннями про алгоритми сортування ми ознайомились, а тепер перейдемо до розгляду конкретних методів сортування.

2. Метод сортування вибором.
Один з найпростіших  методів сортування працює в такий спосіб: знаходимо найменший елемент у масиві й обмінюємо його з елементом, якій знаходиться на першому місці, потім повторюємо процес із другої позиції у файлі і знайдений елемент обмінюємо з другим елементом і так далі поки весь масив не буде відсортований. Цей метод називається сортування вибором оскільки він працює циклічно вибираючи найменший з  елементів, що залишилися.
В міру просування покажчика і ліворуч праворуч через файл, елементи ліворуч від покажчика знаходяться вже в своїй кінцевій позиції (і їхній не будуть більше вже чіпати), тому масив стає цілком відсортованим до того моменту, коли покажчик досягає правого краю.
Цей метод працює дуже добре для невеликих файлів. Його "внутрішній цикл" складається з порівняння 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), що в ряді випадків робить цей метод кращим.
Процедура сортування вибором:
procedure selectіon;
var і, j, mіn, t : іnteger;
begіn
for і:=1 to N-1 do
begіn
mіn := і;
for j:=і+1 to N do
іf a[j]<a[mіn] then
mіn := j;
t := a[mіn];
a[mіn] :=a[і];
a[і] := t;
end;
end;


3. Сортування вставкою.

Сортування вставкою − це метод який майже настільки ж простий, що і сортування вибором, але більш гнучкий. Цей метод часто використовують при сортуванні карт: беремо один елемент і вставляємо його в потрібне місце серед тих, що ми вже відібрали (тим самим залишаючи їх відсортованими).
type Іndex = 0..n;
var a: array[1..n] of elem;
procedure Іnsert;
var і,j: іndex;
x: elem;
begіn
for і:= 1 to n do
begіn
x:= a[і]; a[0]:= x; j:= і-1;
whіle x.key < a[j].key do
begіn
a[j+1]:= a[j]; j:= j-1;
end;
a[j+1]:= x;
end;
end;
Також як і в сортуванні вибором, у процесі сортування елементи зліва від покажчика 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)), що істотно менше складності простих алгоритмів сортування.


4. Пірамідальне сортування.
Отже, ми поступово переходимо від більш-менш простих до складних, але ефективних методів сортування. Пірамідальне сортування є першим з розглянутих методів, швидкодія яких оцінюється як 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]. Плюси такого збереження піраміди очевидні:
o    ніяких додаткових змінних, потрібно лише розуміти схему;
o    вузли зберігаються від вершини і далі вниз, рівень за рівнем;
o    вузли одного рівня зберігаються в масиві зліва направо.
Фаза 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: власне сортування.
Отже, задача побудови піраміди із масиву успішно вирішена. Як видно з властивостей піраміди, в корні завжди знаходиться максимальний елемент. Звідси випливає алгоритм фази 2:
1.Беремо верхній елемент піраміди a[0]...a[n] (перший у масиві) і змінюємо з останнім місцями. Тепер "забуваємо" про цей елемент і далі розглядаємо масив a[0]...a[n-1]. Для перетворення його в піраміду досить просіяти лише новий перший елемент.
2.Повторюємо крок 1, поки оброблювана частина масиву не зменшиться до одного елемента. Очевидно, в кінець масиву щоразу  попадає максимальний елемент із поточної піраміди, тому в правій частині поступово виникає упорядкована послідовність.      
94  67  18  44  55  12  06  42  //           ілюстрація 2-ї фази сортування       
67  55  44  06  42  18  12  //  94           у внутрішнім представленні піраміди      
55  42  44  06  12  18  //  67  94       
44  42  18  06  12  //  55  67  94       
42  12  18  06  //  44  55  67  94       
18  12  06  //  42  44  55  67  94       
12  06  //  18  42  44  55  67  94       
06  //  12  18  42  44  55  67  94
Яка швидкодія  алгоритму, що вийшов? Побудова піраміди займає O(n log n) операцій, причому більш точна оцінка дає навіть O(n) за рахунок того, що реальний час виконання сортування залежить від висоти вже створеної частини піраміди. Друга фаза займає O(n log n) часу: O(n) раз береться максимум і відбувається просівання колишнього останнього елемента. Плюсом є стабільність методу: середнє число пересилань (n log n)/2, і відхилення від цього значення порівняно малі. Пірамідальне сортування не використовує додаткової пам'яті. Метод не є стійким: по ходу роботи масив так "пересіюється", що вихідний порядок елементів може змінитися випадковим чином.
5. Бульбашкове сортування.
Даний метод таож називають обмінним сортуванням з вибором. Ідея цього методу відбита в його назві. Найлегші  елементи масиву "вспливають" наверх, самі "важкі" - тонуть. Алгоритмічно це можна реалізувати в такий спосіб. Ми будемо переглядати весь масив "знизу нагору" і змінювати   елементи, що стоять поруч, у тих випадку, якщо "нижній" елемент менше, ніж "верхній". Таким чином, ми виштовхнемо наверх самий "легкий" елемент усього масиву. Тепер повторимо всю операцію для елементів, що залишилися неотсортироваными, N-1 елементів (тобто для тих, котрі лежать "нижче" першого). Як видно, алгоритм досить простий, але, як іноді зауважують, він є неперевершеним у своїй неефективності.
Реалізація цього методу описана нижче.
procedure bubble;
var і, j, t : byte;
begіn
for і :=2 to N do
for j:=N down to і do
іf x[і-1]>x[j] then
begіn t:=x[j-1];x[j-1]:=x[j];x[j]:=t; end; end; end;
Бульбашкове сортування працює так як і сортування вибором, хоча воно і робить набагато більше роботи на те, щоб перемістити елемент у його кінцеву позицію.
Просте обмінне сортування для масиву a[1], a[2], ..., a[n] працює в такий спосіб. Починаючи з кінця масиву порівнюються два сусідніх елементи (a[n] і a[n-1]). Якщо виконується умова a[n-1] > a[n], то значення елементів міняються місцями. Процес продовжується для a[n-1] і a[n-2] і т.д., поки не буде зроблене порівняння a[2] і a[1]. Зрозуміло, що після цього на місці a[1] виявиться елемент масиву з найменшим значенням. На другому кроці процес повторюється, але останніми порівнюються a[3] і a[2] елементи. І так далі. На останньому кроці будуть порівнюватися тільки поточні значення a[n] і a[n-1].
Приклад сортування методом бульбашки наведений у наступній таблиці:
Початковий масив    8 23 5 65 44 33 1 6
Крок 1    8 23 5  65 44 33 1  6
8 23 5  65 44 1  33 6
8 23 5  65 1  44 33 6
8 23 5  1  65 44 33 6
8 23 1  5  65 44 33 6
8 1  23 5  65 44 33 6
1 8  23 5  65 44 33 6
Крок 2    1 8 23 5  65 44 6  33
1 8 23 5  65 6  44 33
1 8 23 5  6  65 44 33
1 8 23 5  6  65 44 33
1 8 5  23 6  65 44 33
1 5 8  23 6  65 44 33
Крок 3    1 5 8 23 6  65 33 44
1 5 8 23 6  33 65 44
1 5 8 23 6  33 65 44
1 5 8 6  23 33 65 44
1 5 6 8  23 33 65 44
Крок 4    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
Крок 5    1 5 6 8 23 33 44 65
1 5 6 8 23 33 44 65
1 5 6 8 23 33 44 65
Крок 6    1 5 6 8 23 33 44 65
1 5 6 8 23 33 44 65
Крок 7    1 5 6 8 23 33 44 65
Розташуємо масив зверху вниз, від нульового елемента - до останнього.
Ідея методу: крок сортування складається з проходження знизу вгору по масиву. Під час проходження шляху порівнюються пари сусідніх елементів. Якщо елементи деякої пари знаходяться в невірному порядку, то змінюємо їх місцями.

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

Середнє число порівнянь і обмінів мають квадратичний порядок росту: Theta(n2), звідси можна зробити висновок, що алгоритм „бульбашки” дуже повільний і малоефективний. Проте, у нього є величезний плюс: він простий і його можна по-всякому поліпшувати. Чим ми зараз і займемося.
По-перше, розглянемо ситуацію, коли на якому-небудь із проходів не відбулося жодного  обміну. Що це значить?
Це значить, що усі пари розташовані в правильному порядку, так що масив уже відсортований. І продовжувати процес не має змісту (особливо, якщо масив був відсортований із самого початку).
Отже, перше поліпшення алгоритму полягає в запам'ятовуванні, чи відбувався на даному проході який-небудь обмін. Якщо ні, то алгоритм закінчує роботу.
Процес поліпшення можна продовжити, якщо запам'ятовувати не тільки сам факт обміну, але й індекс останнього обміну k. Дійсно: усі пари сусідніх елементів з індексами, меншими k, вже розташовані в потрібному порядку. Подальші проходи можна закінчувати на індексі k, замість того, щоб рухатися до встановленої заздалегідь верхньої границі і.
Якісне поліпшення алгоритму можна одержати з наступного спостереження. Легка бульбашка знизу підніметься наверх за один прохід, важкі пухирці опускаються з мінімальною швидкістю. Так що масив 2 3 4 5 6 1 буде відсортований за 1 прохід, а сортування послідовності 6 1 2 3 4 5 потребує 5 проходів. Щоб уникнути подібного ефекту, можна змінювати напрямок наступних один за одним проходів. Алгоритм, що вийшов, іноді називають "шейкер-сортуванням".
Наскільки описані зміни вплинули на ефективність методу ? Середня кількість порівнянь, хоч і зменшилося, але залишається O(n2), у той час як число обмінів не помінялося взагалі ніяк. Середня (воно ж гірша) кількість операцій залишається квадратичною. Додаткової пам'ять, мабуть, не потрібно. Сортування бульбашкою стійкий метод сортування, однак шейкер-сортировка втрачає цю якість. На практиці метод пухирця, навіть з поліпшеннями, працює, на жаль, занадто повільно. А тому - майже не застосовується.

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

Основа алгоритму швидкого сортування була розроблена в 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 елементу.
program Quіtsort;
uses crt;
Const N=10;
Type Mas=array[1..n] of іnteger;
Var a: mas; k: іnteger;
functіon Part(l, r: іnteger):іnteger;
var v, і, j, b: іnteger;
begіn
V:=a[r];
І:=l-1;
j:=r;
repeat
repeat
dec(j)
untіl (a[j]<=v) or (j=і+1);
repeat
іnc(і)
untіl (a[і]>=v) or (і=j-1);
b:=a[і];
a[і]:=a[j];
a[j]:=b;
untіl і>=j;
a[j]:=a[і];
a[і]:= a[r];
a[r]:=b;
part:=і;
end;
procedure QuіckSort(l, t: іnteger);
var і: іnteger;
begіn
іf l<t then
begіn
і:=part(l, t);
QuіckSort(l,і-1);
QuіckSort(і+1,t);
end;
end;
begіn
clrscr;
randomіze;
for k:=1 to 10 do
begіn
a[k]:=random(100);
wrіte(a[k]:3);
end;
QuіckSort(1,n);
wrіteln;
for k:=1 to n do
wrіte(a[k]:3);
readln;
end.
Приклад:
60, 79, 82, 58, 39, 9, 54, 92, 44, 32
60, 79, 82, 58, 39, 9, 54, 92, 44, 32
9, 79, 82, 58, 39, 60, 54, 92, 44, 32
9, 79, 82, 58, 39, 60, 54, 92, 44, 32
9, 32, 82, 58, 39, 60, 54, 92, 44, 79
9, 32, 44, 58, 39, 60, 54, 92, 82, 79
9, 32, 44, 58, 39, 54, 60, 92, 82, 79
9, 32, 44, 58, 39, 92, 60, 54, 82, 79
9, 32, 44, 58, 39, 54, 60, 79, 82, 92
9, 32, 44, 58, 54, 39, 60, 79, 82, 92
9, 32, 44, 58, 60, 39, 54, 79, 82, 92
9, 32, 44, 58, 54, 39, 60, 79, 82, 92
9, 32, 44, 58, 54, 39, 60, 79, 82, 92
9, 32, 44, 58, 54, 39, 60, 79, 82, 92
9, 32, 39, 58, 54, 44, 60, 79, 82, 92
9, 32, 39, 58, 54, 44, 60, 79, 82, 92
9, 32, 39, 44, 54, 58, 60, 79, 82, 92
9, 32, 39, 44, 58, 54, 60, 79, 82, 92
9, 32, 39, 44, 54, 58, 60, 79, 82, 92
9, 32, 39, 44, 54, 58, 60, 79, 92, 82
9, 32, 39, 44, 54, 58, 60, 79, 82, 92
"Внутрішній цикл" швидкого сортування складається тільки зі збільшення покажчика і порівняння елементів масиву з фіксованим числом. Саме це і робить швидке сортування швидким. Складно придумати більш простий внутрішній цикл. Позитивні ефекти сторожових ключів також роблять тут свій вплив, оскільки приєднання ще однієї перевірки до внутрішнього циклу зробило би негативний вплив на продуктивність алгоритму.
Характеристики продуктивності швидкого сортування:
Найкраще ,що могло б відбутися для алгоритму - це якби  кожний з підфайлів ділився б на два рівних по величині підфайла. В результаті кількість порівнянь, яке робить швидке сортування  дорівнювало б значенню рекурсивного виразу.
CN = 2CN/2+N - найкращий випадок.
(2CN/2 покриває витрати по сортуванню двох отриманих підфайлів; N - це вартість обробки кожного елемента, використовуючи один чи інший покажчик.) Нам відомо також, що зразкове значення цього вираження дорівнює CN = N lg N.
Хоча ми зустрічаємося з подібною ситуацією не так часто, але в середньому час роботи програми буде відповідати цій формулі. Якщо взяти до уваги ймовірні позиції кожного розділу, то це зробить обчислення більш складними, але кінцевий результат буде аналогічним.
Методи поліпшення швидкого сортування:
1. Невеликі підфайли.
2. Розподіл по медіані з трьох.
3. Нерекурсивна реалізація.


7. Висновки.

Отже, ми розглянули як працюють деякі алгоритми сортування і спробували визначити їх складність.
Застосування того чи іншого алгоритму сортування для вирішення конкретної задачі є досить складною проблемою,  вирішення якої потребує не лише досконалого володіння саме цим алгоритмом, але й всебічного розглядання того чи іншого алгоритму, тобто визначення усіх  його переваг і недоліків.
В даній курсовій роботі ми розглянули “елементарні та більш складні, а точніше швидкі алгоритми сортування. Звичайно, необхідність застосування саме швидких алгоритмів сортування очевидна. Адже прості алгоритми сортування не дають бажаної ефективності в роботі програми. Але завжди треба пам’ятати й про те, що кожний швидкий алгоритм сортування поряд із своїми перевагами може містити і деякі недоліки.
В нашій роботі ми розглянули деякі  алгоритми сортування та їх реалізацію мовою  Pascal, дослідили не лише переваги таких алгоритмів, ефективність їх використання, але й визначили деякі недоліки окремих алгоритмів, що заважають вживати їх для вирішення першої ліпшої задачі сортування.
Отже, головною задачею, яку має вирішити людина, яка повинна розв’язати задачу сортування – це визначення як позитивних, так і усіх негативних  характеристик різних алгоритмів сортування, передбачення кінцевого результату.  До того ж , треба враховувати головне – чи  , можливо,  цю задачу  задовольнить один з класичних  простих алгоритмів сортування.





Література.

1.    Иванов Б.Н. и др. Дискретная математика. Алгоритмы и программы.  − Москва: Лаборатория базовых знаний, 2002.
2.    Вирт Н. Алгоритмы и структурные данные. − Санкт-Петербург: Невский диалект, 2001.
3.    Альфред В. Ахо, Джон Э. Хопкрофт, Джерффри Д. Ульман. Структуры данных и алгоритмы. – М.: Издательский дом “Вильямс”, 2001.
4.    Абрамов С. А., Зима Е. В.  Начала программирования на языке                 Pascal. -  М.: Наука, 1987.
5.    Абрамов В. Г.  Введение в язык Pascal: Учебное пособие для студентов вузов по специальности  Прикладная математика. – М.: Наука, 1988.
6.    Джонс Ж., Харроу К. Решение задач в системе Турбо-Паскаль/ Перевод с английского Улановой,  Широкого. – М.: Финансы и статистика, 1991.
7.    Зуев Е. А. Язык программирования Турбо Паскаль 6.0, 7.0. – М.: Радио и связь, 1993.
8.    Культин  Н. Б. Программирование в  TurboPascal 7.0 и   Delphi. -  Санкт-петербург,1999.
9.    Львов М. С., Співаковський О. В. Основи алгоритмізації та програмування. – Херсон, 1997.
10.    Фаронов В. В. TurboPascal 7.0 . Начальный курс. – М.: “Нолидж”, 2000.