ШВИДКІ АЛГОРИТМИ СОРТУВАННЯ І ПОШУКУ

Задачі і вправи

1.Дано масив А[1..900] of 1..999. Знайти трьохзначне число, що не знаходиться у цьому масиві. Розглянути два варіанта задачі:

а) Допоміжні масиви в алгоритмі не використовуються;

б) Використання допоміжних масивів дозволено.

2.Реалізувати алгоритм TreeSort, застосувавши метод вкладення дерева в масив. Для цього використати допоміжний масив В.

3.Реалізувати ітеративну версію алгоритму HeapSort:

а)Замінити рекурсію в процедурі SortTree арифметичним циклом For...downto, що оброблює дерево за рівнями, починаючи з нижнього;

б)Замінити рекурсію в процедурі Conflict ітераційним циклом, керуючим змінною i. { i := 2i або i := 2i + 1 }.

4.Реалізувати ітеративну версію алгоритму процедури HoareSeach, замінивши рекурсію ітераційним циклом.

5-6. Застосувати для розв’язку задач 1-2 параграфа 8 ідею Хоара.

7.Реалізувати алгоритм “тернарного” пошуку елемента в упорядкованому масиві, поділяючи ділянку пошуку на 3 приблизно рівні частини. Оцінити складність алгоритму у термінах С (n). Порівняти ефективності бінарного і тернарного пошуку.

8.Реалізувати алгоритм пошуку максимального і мінімального елементів у масиві (процедура MaxMin) для довільного n.

9.Нехай A[1..n] - масив цілих чисел, упорядкований за зростанням (A[i] <>

10-12. Застосувати для розв’язку задач 3-5 параграфа 8 метод “розділяй і володій”.

13.Реалізувати алгоритм процедури Reverse “на місці”, формуючи обернену підстановку в масиві А.