ання. Розглянемо кілька прикладів сортировок і порівняємо їх з алгоритмом, обраним для реалізації телефонної книги [1]. p align="justify"> Сортування за допомогою прямого вибору. Суть цієї сортування полягає в тому, що вибирається елемент з найменшим значенням, міняється місцями з першим елементом, потім цей процес повторюється з рештою елементами доти поки список буде відсортований. br/>В
Рис.1.1 Схема алгоритму прямого вибору
Сортування за допомогою прямого включення. У сортуванні включеннями елементи розділяються на вже впорядковану і невпорядковану послідовності. На початку впорядкована частина містить тільки один елемент. Черговий елемент з початку невпорядкованою частини вставляється на відповідне місце у впорядковану частину. При цьому впорядкована частина подовжується на один елемент, а неупорядкована - коротшає. Сортування закінчується при зникненні невпорядкованою частини [4]. br/>В
Рис 1.2 Схема алгоритму прямих включень
Сортування прямого обміну. Алгоритм прямої обміну грунтується на порівнянні та зміні місць для пари сусідніх елементів і продовженні цього процесу до тих пір, поки не будуть впорядковані всі елементи. Повторюються проходи за списком, зрушуючи щоразу найбільший (або найменший) елемент залишилася послідовності до лівого кінця списку. Такий метод широко відомий під ім'ям бульбашкова сортування. Очевидний спосіб поліпшення цього алгоритму - були чи не були перестановки в процесі деякого проходу. Якщо в останньому проході перестановок не було, то алгоритм можна закінчувати. br/>В
Рис 1.3 Схема алгоритму прямого обміну
Для вирішення поставленого завдання був обраний алгоритм прямого обміну, так як ця сортування простіша у реалізації та ефективна для даної задачі. Інші алгоритми сортування складні в реалізації, тому від них вирішили відмовитися. p align="justify"> Важливим алгоритмом для даної курсової роботи є алгоритм пошуку підрядка в рядку. Розглянемо деякі алгоритми. p align="justify"> Алгоритм заснований на методі послідовного пошуку. Позначимо S - слово, в якому шукається зразок X. Нехай m і n - довжини слів S і X відповідно. Можна порівняти зі словом X всі подслова S, які починаються з позицій 1,2, ..., m-n +1 в слові S; в разі рівності виводиться відповідна позиція. Алгоритм простий в реалізації. Кількість порівнянь дорівнюватиме O ((m-n +1) * n +1) [3]. p align="justify"> Алгоритм Рабіна. У слові A, довжина якого дорівнює m, ми шукаємо зразок X довжини n. Виріжемо "віконечко" розміром n і будемо рухати його по вхідному слову. Нас цікавить, не збігається чи слово в "віконечку" із заданим зразком. Порівнювати по буквах довго. Замість цього фіксуємо деяку числову функцію на словах довжини n, тоді завдання зведеться до порівняння чисел, що, безсумнівно, швидше. Якщо значення цієї функції на слові в "віконечку" та на зразку різні, то збігу...
