gn="justify"> Мета: дослідити деякі методи сортировок. p align="justify"> Завдання: вивчити літературу по алгоритмах сортировок, скласти підпрограми сортировок, провести аналіз і обчислити середній час кожної сортування, скласти графічне меню.
сортування алгоритм послідовність підпрограма
Теоретичний розділ
Сортування бульбашкою
Сортування простими обмінами, сортува ? вка бульбашок ? м (англ. bubble sort) - простий алгоритм сортування. Для розуміння і реалізації цей алгоритм - найпростіший, але ефективний він лише для невеликих масивів. Складність алгоритму: O (n ВІ ).
Алгоритм вважається навчальним і практично не застосовується поза навчальної літератури, замість нього на практиці застосовуються більш ефективні алгоритми сортування. У той же час метод сортування обмінами лежить в основі деяких більш досконалих алгоритмів, таких як шейкерні сортування, пірамідальна сортування і швидке сортування. Алгоритм полягає в повторюваних проходах по сортованого масиву. За кожен прохід елементи послідовно порівнюються попарно і, якщо порядок у парі невірний, виконується обмін елементів. Проходи по масиву повторюються до тих пір, поки на черговому проході не опиниться, що обміни більше не потрібні, що означає - масив відсортований. При проході алгоритму, елемент, що стоїть не на своєму місці, В«спливаєВ» до потрібної позиції як бульбашка у воді, звідси і назва алгоритму. p align="justify"> Зверніть увагу, що кількість повторів у внутрішньому циклі зменшується з кожною итерацией зовнішнього циклу. Особливість даного алгоритму полягає в наступному: після першого завершення внутрішнього циклу максимальний елемент масиву завжди знаходиться на N-ій позиції. При другому проході, наступний за значенням максимальний елемент знаходитиметься на N-1 місці. І так далі. Таким чином немає необхідності "обходити" весь масив від початку до кінця кожного разу. p align="justify"> Аналіз сортування
При аналізі всякої сортування визначається число операцій порівняння і обміну, виконуваних в кращому, середньому і найгіршому випадках. Для сортування бульбашковим методом число порівнянь залишається незмінним, оскільки два циклу завжди виконуються задане число разів незалежно від впорядкованості вихідного масиву. Це означає, що при сортуванні бульбашковим методом завжди виконується 1/2 (n2-n) операцій порівняння, де "n" задає число сортируемих елементів масиву. Ця формула виводиться на тій підставі, що зовнішній цикл сортування бульбашковим методом виконується n-1 раз, а внутрішній цикл виконується n/2 разів. br/>
Сортування вставками
Сортування вставками - простий алгоритм сорт...
