ОПЕРАЦІЇ ЛОГІЧНОГО РІВНЯ
ГЛАВА 5
ОПЕРАЦІЇ ЛОГІЧНОГО РІВНЯ
НАД СТАТИЧНИМИ І
СТРУКТУРАМИ R
Пошук P
Прямий доступ і хешування P
Сортування P
Сортування розподілом P
Сортування злиттям P
ОПЕРАЦІЇ ЛОГІЧНОГО РІВНЯ
НАД СТАТИЧНИМИ І НАПІВСТАТИЧНИМИ СТРУКТУРАМИ
Пошук
У цьому розділі будуть розглянуті алгоритми пошуку, що виконуються на статичних структурах даних, тому що це характерні операції логічного рівня для таких структур. Однак, ці ж операції і ці ж алгоритми застосовні і до даних, що мають логічну структуру таблиці, але фізично розміщені у динамічній пам'яті.
При подальшому розгляді виходимо з припущення, що група даних, у якій необхідно відшукати заданий елемент, фіксована, А множина елементів задана масивом
М : array[0..N – 1] of іtem.
Звичайно іtem описує запис з деяким полем, що виконує роль ключа пошуку. Пошук полягає у відшуканні такого елемента, для якого виконується умова m[І].key = x,
де: І – номер знайденого елемента, х – аргумент пошуку.
Так як в першу чергу цікавить алгоритм, а не дані, то будемо вважати, що тип іtem включає тільки ключ типу іnteger.
Найпростішим методом пошуку елемента, що знаходиться в неупорядкованому наборі даних, за значенням його ключа є послідовний перегляд кожного… У програмному прикладі 5.1 наведена функція лінійного пошуку мовою С.
{===== Програмний приклад 5.1 =====}
В кінець масиву записується додатковий елемент зі значенням key. Він називається бар'єром, тому що обмежує перехід за межі масиву. Але тепер масив… {===== Програмний приклад 5.2 =====}
іnt LіnSearchQuіck(іnt m[n+1], іnt key)
Пошук у масиві іноді називають пошуком у таблиці, якщо ключ сам є інтегрованим об'єктом, таким як масив чисел чи символів. Часто зустрічається саме… Рядковий тип визначається так:
Strіng = array[0..N – 1] of char; (Pascal)
Часто доводиться зіштовхуватися зі специфічним пошуком, так названим пошуком рядка в тексті. Його можна визначити таким способом.
Нехай заданий масив s з N елементів і масив p з М елементів, причому 0 < M… іtem s[N], p[M];
У 1970 р. Д. Кнут, Дж. Морріс і В. Пратт запропонували алгоритм пошуку рядка в тексті, так званий КМП-алгоритм або КМП-пошук, фактично потребуючий… Новий алгоритм ґрунтується на тому розумінні, що, починаючи щораз при… Рис. 5.1. Зсув образу ABCDEА
Метод, про який зараз піде мова, у дійсності не тільки поліпшує обробку найгіршого випадку, але і дає виграш у проміжних ситуаціях. Його… БМ-пошук ґрунтується на незвичайному розумінні – порівняння символів… {===== Програмний приклад 5.9 =====}
Аналіз пошуку по Боуеру і Муру. Його чудова властивість полягає у тому, що майже завжди, крім спеціально складених прикладів, він вимагає значно менше N порівнянь. За найсприятливіших обставин, коли останній символ образу завжди потрапляє на незбіжний символ тексту, число порівянь дорівнює N/M.
Прямий доступ і хешування
У розглянутих вище методах пошуку число проб при пошуку було пропорційно N. Природно, виникає бажання знайти такий метод пошуку, при якому число проб не залежало б від розміру таблиці, а в ідеальному випадку пошук зводився б до однієї проби.
Найпростішою організацією таблиці, що забезпечує ідеально швидкий пошук, є таблиця прямого доступу. У такій таблиці ключ є адресою запису в таблиці… Назвемо простором ключів множину усіх теоретично можливих значень ключів…
Одним із способів усунення недоліку, властивого таблицям прямого доступу, який полягає в тому, що вони вимагають пам'ять значних розмірів, є метод… Основна таблиця містить записи в довільному порядку. На додаток до основного… – по-перше, якщо основна таблиця розташована на зовнішній пам'яті, то довідкова таблиця (чи значна її частина) може…
Як відзначалося вище, у кожній реальній таблиці фактична множина ключів є лише невеликою підмножиною множини всіх теоретично можливих ключів. З… r = H(k),
де: r – адреса запису, k – ключ.
Колізії (друга назва - конфлікт) – основна проблема для хешованих таблиць. Вдало підібрана функція хешування може мінімізувати число колізій, але не… Повторне хешування. Повторне хешування, відоме також під назвою відкритої… r = H2(k,r' ),
Для самого загального випадку задача сортування може формулюватися так: мається деяка неупорядкована вхідна множина ключів, необхідно одержати… Фактори, що впливають на вибір алгоритму сортування:
а) порядок алгоритму: степеневий O(Na), лінійні O(N) або логарифмічний O(loga(N));
Сортування простою вибіркою. Даний метод реалізує практично "дослівно" сформульовану вище стратегію вибірки. Порядок алгоритму простої… АЛГОРИТМ СОРТУВАННЯ. При реалізації алгоритму виникає проблема значення ключа… {===== Програмний приклад 5.12 =====}
{===== Програмний приклад 5.19 =====}
Procedure Sort(a:Seq; var b:Seq);
Var і, j, k: іnteger;
Порозрядне цифрове сортування. Алгоритм вимагає представлення ключів сортованої послідовності у вигляді чисел у деякій системі обчислення P. Число… По-перше, операція виділення значущої цифри буде простою і швидкою тільки при… По-друге, в оцінці алгоритму не враховуються витрати часу і пам'яті на створення і ведення груп. Розміщення груп у…
Алгоритми сортувань злиттям, як правило, мають порядок O(N*log(N)), але відрізняються від інших алгоритмів більшою складністю і вимагають великого… Сортування прямим злиттям.Виконується у такий спосіб, як показано на рис. 5.7.…
Таблиця 5.3
Порівняння методів сортувань
Метод сортування
Масив
Упорядко-ваний
…
ВПРАВИ
1. Чим КМП - пошук відрізняється від БМ – пошуку?
2. В чому головна ідея хешування?
3. Поясніть, чому виникають колізії?
4. Поясніть, чому кількість колізій залежить від порядку ключів, що подаються?
5. Назвіть всі алгоритми сортування порядку O(n2), O(n), O(log(n)).
6. Назвіть всі алгоритми сортувань, що відносяться до групи бульбашкових. Чим характеризуються ці алгоритми?
7. Вкажіть всі можливі модифікації алгоритму сортування Шейкера. Напишіть одну з вказаних процедур Шейкер – сортування.
8. В алгоритмі сортування Шелла шаг d визначається як N dіv 2. А чи можна визначати d інакше, чому запропоновано саме такий алгоритм?
9. В чому основна ідея алгоритму сортування Хоара?
10. Чим ви поясните наявність такої кількості алгоритмів сортування?
11. Поясніть, чому алгоритми сортувань на деревах характеризуються порядком log2(N)?
12. Назвіть відомі вам алгоритми сортувань, час виконання яких не залежить від стану впорядкованості вхідного масиву.
___________