Пошук, сортування та поняття складності у програмуванні, Детальна інформація

{ A[k] є останнім від початку елементом, }

{ значення якого менше v }

swap ( A[lo], A[k] ); { A[k] = v }

quicksort ( A , lo, k - 1 );

quicksort ( A , k + 1, hi );

1: end

Якщо за виконання кожного виклику після циклу while значення змінної k приблизно рівне (lo+hi)/2, то складність швидкого сортування масиву з n елементів можна оцінити як O(nlogn). Середня кількість порівнянь елементів усіх можливих числових послідовностей довжини n також має оцінку O(nlogn); доведення є, наприклад, у книзі [АХУ]. Емпіричні дослідження свідчать, що швидке сортування вимагає в середньому елементарних дій приблизно вдвічі менше, ніж сортування деревом, і вчетверо менше, ніж сортування злиттям. Але якщо початковий масив близький до відсортованого, то його сортування за наведеним алгоритмом вимагає вже O(n2) порівнянь. У такому випадку відокремлюючим елементом не можна вибирати значення A[lo].

Існує багато способів вибору іншого відокремлюючого значення. Наприклад, можна вибрати значення елемента з випадковим номером серед номерів lo, … , hi, або середнє із значень A[lo], A[hi], та A[(lo+hi)div2]. У такому разі перед оператором процедури

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 \xF0A3 1000) найменших значень числової послідовності довільної довжини за умови, що

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

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

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

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

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

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

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

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

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

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

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

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

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