Мета роботи. Отримати практичні навички програмування на С++задач, де використовується пошук і сортування інформації

Отримати практичні навички програмування на С++ задач, де використовується пошук і сортування інформації.

7.2 Методичні вказівки до організації самостійної роботи студентів

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

Сортування — це задача розташування довільних об'єктів у порядку (не-) зменшення чи (не-)зростання деякої ознаки. Існує велика кількість методів сортування, що відрізняються друг від друга як тимчасовою складністю, так і універсальністю.

7.2.1 Лінійний пошук

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

7.2.2 Пошук розподілом навпіл (двійковий пошук)

Пошук може бути більш ефективним, якщо дані будуть упорядковані. Основна ідея – вибрати випадково деякий елемент а_m і порівняти його з аргументом пошуку х. Якщо він дорівнює х, то пошук закінчується, якщо він менше х, то всі елементи з індексами, меншими чи рівними m, можна виключити з подальшого пошуку; якщо ж він більше х, то виключаються індекси, більші чи рівні m.