Розділ і. Алгоритми "швидкого сортування" та "сортування вибором"
1.1.Постановка Задачі
1)Розглянути два алгоритми сортування.
2) Описати способи опрацювання, суть та практичнее застосування цих алгоритмiв.
3)Проаналiзувати складнiсть використання алгоритмiв "Швидкого сортування" та "Сортування вибором", та визначити доцiльнiсть застосування цих алгоритмiв.
Актуальнiсть використання алгоритмiв сортування має досить велике значення для роботи , подальшого розвитку та впровадження комп`ютерних технлогiй у всi сфери дiяльностi людини.
На сьогоднiшнiй день комп`ютер є невiд`ємною частиною роботи майже будь-якої людини. Саме для полегшення цiєї роботи i створенi алгоритми сортування. Для швидкого пошуку потрiбних даних серед необмеженої кiлькостi iнформацiї.
1.2. Суть алгоритму "Швидкого сортування"
Швидке сортування — алгоритм сортування, добре відомий, як алгоритм розроблений Чарльзом Хоаром, який не потребує додаткової пам'яті і виконує у середньому O(n log n) операцій. Однак, у найгіршому випадку робить O(n2) порівнянь. Оскільки алгоритм використовує дуже прості цикли і операції, він працює швидше інших алгоритмів, що мають таку ж асимптотичну оцінку складності. Наприклад, зазвичай більш ніж удвічі швидший порівняно з сортуванням злиттям.
Алгоритм швидкого сортування було розроблено Чарльзом Хоаром (C. A. R. Hoare) у 1962 під час роботи у маленькій британській компанії Elliott Brothers.
В класичному варіанті, запропонованому Хоаром, з масиву обирався один елемент, і весь масив розбивався на дві частини по принципу: в першій частині — ті що не більші даного елементу, в другій частині — ті що не менші даного елемента.
"Швидке сортування", хоч і було розроблено більше 40 років тому, є найбільш широко застосовуваним і одним їх найефективніших алгоритмів. Метод заснований на підході "розділяй-і-володарюй". Загальна схема така: 1) з масиву вибирається деякий опорний елемент a [i], 2) запускається процедура поділу масиву, яка переміщує всі ключі, менші, або рівні a [i], вліво від нього, а всі ключі, більші, або рівні a [i] - вправо,
3) тепер масив складається з двох підмножин, причому ліва менша, або дорівнює правiй,
-
<=a[i]
a[i]
>=a[i]
4) для обох пiдмасивiв: якщо в підмасиві більше двох елементів, рекурсивно запускаємо для нього ту ж процедуру.
Наприкінці вийде повністю відсортована послідовність.
1 |
3 |
5 |
6 |
5 |
7 |
8 |
2 |
9 |
1.3. Суть алгоритму "Сортування вибором"
Сортування вибором — простий алгоритм сортування лінійного масиву, на основі вставок. Має ефективність n2, що робить його неефективним при сортування великих масивів, і в цілому, менш ефективним за подібний алгоритм сортування включенням. Сортування вибором вирізняється більшою простотою, ніж сортування включенням, і в деяких випадках, вищою продуктивністю.
Алгоритм працює таким чином:
1. Знаходить у списку найменше значення
2. Міняє його місцями із першим значеннями у списку
3. Повторює два попередніх кроки, доки список не завершиться (починаючи з другої позиції)
Фактично, таким чином ми поділили список на дві частини: перша (ліва) — повністю відсортована, а друга (права) — ні.
Сортування вибором не є складним в аналізі та порівнянні його з іншими алгоритмами, оскільки жоден з циклів не залежить від даних у списку. Знаходження найменшого елементу вимагає перегляду усіх n елементів (у цьому випадку n − 1 порівняння), і після цього, перестановки його до першої позиції. Знаходження наступного найменшого елементу вимагає перегляду n − 1 елементів, і так далі, для
(n − 1) + (n − 2) + ... + 2 + 1 = n(n − 1) / 2 ∈ Θ(n2) порівнянь .
Кожне сканування вимагає однієї перестановки для n − 1 елементів (останній елемент знаходитиметься на своєму місці).
РОЗДІЛ II. СЕРЕДОВИЩЕ ПРОГРАМУВАННЯ С++ BUILDER
2.1. Основні характеристики середовища програмування
C++ Builder
Вікно середовища C++ Builder при завантаженні складається з таких елементів :
1. вікно форми;
2. вікно коду програми;
3. головне меню;
4. «гарячі» кнопки інструментальних панелей;
5. палітра компонентів;
6. вікно інспектора об`єктів