ОПЕРАЦІЇ ЛОГІЧНОГО РІВНЯ

ГЛАВА 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(n²), O(n), O(log(n)).

6. Назвіть всі алгоритми сортувань, що відносяться до групи бульбашкових. Чим характеризуються ці алгоритми?

7. Вкажіть всі можливі модифікації алгоритму сортування Шейкера. Напишіть одну з вказаних процедур Шейкер – сортування.

8. В алгоритмі сортування Шелла шаг d визначається як N dіv 2. А чи можна визначати d інакше, чому запропоновано саме такий алгоритм?

9. В чому основна ідея алгоритму сортування Хоара?

10. Чим ви поясните наявність такої кількості алгоритмів сортування?

11. Поясніть, чому алгоритми сортувань на деревах характеризуються порядком log₂(N)?

12. Назвіть відомі вам алгоритми сортувань, час виконання яких не залежить від стану впорядкованості вхідного масиву.

 

___________