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

v := A[lo]; {?!}

треба задати обмін значень A[lo] та відповідного елемента, чиє значення вибирається відокремлюючим.

Задачі

8. Переробити процедуру Merges так, щоб на кроці з непарним номером перший масив без копіювання зливався в другий, а на кроці з парним номером, навпаки, другий без копіювання зливався в перший.

9.* Написати нерекурсивний варіант сортування деревом (підр.17.4.2).

10. За масивом із N рядків визначається додатковий індексовий масив: попаpно pізні значення його елементів належать діапазону 1..N і є індексами в масиві рядків. Написати процедуру

а) сортування індексового масиву таким чином, щоб рядки, на які посилаються його послідовні елементи, були лексикогpафічно впоpядковані;

б) друкування рядків масиву за зpостанням у лексикографічному порядку (кожний рядок друкується один pаз незалежно від кількості повтоpень у масиві).

11. Написати процедуру обчислення N (N  1000) найменших значень числової послідовності довільної довжини за умови, що

а)* незалежно від кількості повтоpень усі числа враховуються один pаз кожне;б) число враховується стільки pазів, скільки воно зустрілося в послідовності (але не більше ніж N);

в) числа враховуються один pаз кожне, але ведеться додатковий облік кількостей їх повтоpень.

12. Запрограмувати злиття

а) трьох б) п'яти в) тисячі

упорядкованих послідовностей в одну.

13.* Запрограмувати сортування елементів зв'язаного списку. Складність алгоритму повинна бути O(nlogn).

14. Запрограмувати сортування послідовностей із

а) чотирьох елементів так, щоб виконувалося не більше п'яти порівнянь;

б) п'яти елементів так, щоб виконувалося не більше восьми порівнянь;

в) п'яти елементів так, щоб виконувалося не більше семи порівнянь.

5. Відсортуй, і багато чого побачиш

Вам треба огородити сад із деревами, витративши на огорожу якомога менше матеріалу. Вважатимемо, що дерев не менше трьох, і вони задаються координатами на площині. Розв'язання полягає в побудові так званої опуклої оболонки навколо множини точок із заданими координатами. На площині вона являє собою опуклий багатокутник, що містить усі задані точки і не містить інших опуклих багатокутників, які також "накривають" усі точки.

Якщо намалювати план саду, то побудова оболонки стане очевидною. Треба відшукати якусь "крайню" початкову точку і рухатися від неї, малюючи опуклий багатокутник. Як результат, ми одержимо послідовність вершин – заданих точок, на які "натягнуто" багатокутник. Точки, що потрапили на сторону багатокутника, але не є вершинами, можна відкинути.