Вставки в кілька зв'язаних списків

Ідея методу ґрунтується на припущенні, що ключі у вихідному файлі мають значення в деякому відомому діапазоні MAX і в цьому діапазоні вони розподілені досить рівномірно. Тоді за аналогією з методом вставки в один зв'язаний список можна організувати трохи, наприклад, Q списків. Величина Q залежить від очікуваної середньої кількості елементів M у кожнім списку тобто Q=N/M, N - кількість ключів. При розробці програми потрібно проаналізувати залежність часу роботи методу від параметра М для різних вихідних файлів дати рекомендації з вибору оптимального значення.

Схема алгоритму має наступний вид. Через Q позначена кількість списків, масив B[1]...B[Q] служить для збереження покажчиків на початки окремих списків. Перед початком роботи алгоритму елементи масиву В передбачаються рівними 0.Кожен і-й елемент вихідного файлу містить ключ K[і] і покажчик L[і] на наступний елемент списку. Значення L[і]=0 відповідає останньому елементу в списку, покажчик B[1] указує на початок першого подсписка й одночасно на початок усього списку. Через mіn позначене мінімальне значення ключа у файлі, через М - середнє обране значення кількості елементів у подсписке. d - номер поточного списку, у який повинний бути вставлений елемент K[j]. Величина R=MAX/Q є діапазон значень ключів, що приходиться на один список.

for j=N-1 to 1

┌────────────────────────────────────────────┐

│ X=K[j]; d= (X-minK)/R+1;(поділ націло)│

│ p=B[d]; │

│ q=0; │

│ │

│ ┌─while(p>0 & X>K[p]) ──────────┐ │

│ │ │ │

│ │ просування за списком │ │

│ ├────────────────────────────────┤ │

│ │ q=p; │ │

│ │ p=L[p]; │ │

│ └────────────────────────────────┘ │

│ ┌────────────────────────────────┐ │

│ │Вставка элемента Х │ │

│ ├────────────────────────────────┤ │

│ │ if(q=0) B[d]=j; else L[q]=j; │ │

│ │ L[j]=p; │ │

│ └────────────────────────────────┘ │

└────────────────────────────────────────────┘

Час роботи алгоритму t приблизно оцінюється формулою: t=a*N¤ + b*N

де a,b - невідомі константи, що залежать від програмної реалізації алгоритму.

Вимоги до оформлення звіту лабораторної роботи:

Звіт повинний містити:

1. Тема і ціль лабораторної роботи.

2. Короткі теоретичні зведення.

3. Завдання і програму.

4. Результати виконання програми.

Лабораторна робота №6

Тема: Методи сортування

Завдання: Розробити програму сортування методом Шелла

Програма повинна забезпечувати введення чи генерацію вихідних даних і візуалізувати результати сортування.

Лабораторна робота №7

Тема: Методи сортування

Завдання: Розробити програму сортування методом "сортування злиттям". Програма повинна забезпечувати введення чи генерацію вихідних даних і візуалізувати результати сортування.

Лабораторна робота №8

Тема: Методи сортування

Завдання: Розробити програму сортування методом "сортування вибором". Програма повинна забезпечувати введення чи генерацію вихідних даних і візуалізувати результати сортування.

Поиск по сайту: