Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

Информатика->Реферат
Сегодня управление предприятием без компьютера просто немыслимо. Компью­теры давно и прочно вошли в такие области управления, как бухгалтерский учет, ...полностью>>
Информатика->Шпаргалка
Знания (англ., knowledge) – в широком смысле – результат познавательной деятельности человека. Знания – в узком смысле – вид информации, отражающей оп...полностью>>
Информатика->Реферат
«ИНЭК-Аналитик» существенно отличается от программных продуктов аналогичного класса тем, что результатом работы с ним является и всесторонний финансов...полностью>>
Информатика->Лекция
Курс лекций дисциплины "Информационные технологии в профессиональной деятельности" предназначен для реализации Государственных требований к минимуму с...полностью>>

Главная > Курсовая работа >Информатика

Сохрани ссылку на реферат в одной из сетей:

Міністерство освіти і науки України

Курсова робота на тему:

Порівняльний аналіз ефективності та складності алгоритмів сортування файлів і послідовностей

Зміст

Вступ

1. Сортування прямим злиттям

2. Природне злиття

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

4. Багатофазне злиття

Висновки

Література

Додатки

Вступ

Комп’ютери тісно увійшли в наше життя. Ми і не помітили, як вони заполонили всі галузі нашого господарства, зайдеш в супермаркет – візьмеш товар, тобі автоматично виб’ють чек за штрих кодом, в бібліотеку зайдеш – по каталогу знайдуть потрібну книжку і скажуть в якому ряду і на якій полиці вона розміщена. Потрібно знайти реферат, - будь-ласка, заходиш в Інтернет-кафе, відкриваєш пошуковий сервер, вводиш слова із потрібної теми і вже за секунду тобі відкриваються посилання на можливі сайти. Аналогічним чином ви заходите в магазин і замовляєте вкрай необхідну деталь для вашої пральної машини і вже за секунду вам повідомляють чи є вона на прилавку магазину, чи можливо лежить неподалік на складі чи її зможуть замовити і привезти наступного тижня.

Проте рідко хто задумувався, як так швидко ви отримуєте цю інформацію? А все дуже просто, існує певна база даних, по ній проводиться пошук і вже по результатах вибірки робляться висновки. Зрозуміло, рядовому користувачу вникати в деталі неважливо, проте ми в своїй курсовій роботі зачепимо ряд питань.

Так, пошук проводиться в базі даних. Для того щоб він був швидкий, база даних повинна бути впорядкована. Отже, хоч програмування містить цілу низку важливих внутрішніх задач, та все ж однією з найбільш важливих таких задач для програмування є задача сортування. Під сортуванням звичайно розуміють перестановки елементів будь-якої послідовності у визначеному порядку. Ця задача є однією з найважливіших тому, що її метою є полегшення подальшої обробки певних даних і, насамперед, задачі пошуку. Так, одним з ефективних алгоритмів пошуку є бінарний пошук. Він працює швидше ніж, наприклад, лінійний пошук, але його можливо застосовувати лише за умови, що послідовність вже упорядкована, тобто відсортована.

Взагалі, відомо, що в будь-якій сфері діяльності, що використовує комп’ютер для запису, обробки та збереження інформації, усі дані зберігаються в базах даних, які також потребують сортування. Певна впорядкованість для них дуже важлива, адже користувачеві набагато легше працювати з даними, що мають певний порядок. Так, можна розташувати всі товари по назві або відомості про співробітників чи студентів за прізвищем або роком народження, тощо.

Задача сортування в програмуванні не вирішена повністю. Адже, хоча й існує велика кількість алгоритмів сортування, все ж таки метою програмування є не лише розробка алгоритмів сортування елементів, але й розробка саме ефективних алгоритмів сортування. Ми знаємо, що одну й ту саму задачу можна вирішити за допомогою різних алгоритмів і кожен раз зміна алгоритму приводить до нових, більш або менш ефективних розв’язків задачі. Основними вимогами до ефективності алгоритмів сортування є перш за все ефективність за часом та економне використання пам’яті. Згідно цих вимог, прості алгоритми сортування (такі, як сортування вибором і сортування включенням) не є дуже ефективними.

З винайденням комп’ютерної техніки проблемою створення алгоритмів сортування займалося дуже багато людей. Проводилися досліди, експерименти із швидкодії одних методів і їх переваги над іншими, наводилися їх математичні моделі для оцінки затраченого часу виконання.

З часом, ці методи були розбиті на декілька категорій, найбільш відомі серед яких, це прямі методи сортування масивів і послідовностей:

- сортування прямим включенням.

- сортування бінарним включенням.

- сортування прямим вибором.

- сортування прямим обміном.

Та швидкі методи сортування:

- сортування алгоритмом Шелла;

- сортування алгоритмом Quick Sort;

- сортування алгоритмом Тree Sort;

- сортування алгоритмом Heap Sort.

Звичайно, це не всі методи сортування масивів. Та з часом виявилося, що вони не повністю вичерпують проблеми пов’язані із питанням сортування. Так, в реальних задачах виникають послідовності, що зберігаються в файлах і не можуть уміщатися в оперативній пам'яті у вигляді масивів. Наприклад, у великому місті може бути кілька мільйонів абонентів телефонної мережі. Звичайно, для швидкого пошуку дані про абонентів мають бути відсортованими. Виникає задача сортування файлів за умови, що файли цілком не можна подавати в оперативній пам'яті. Тому, алгоритми сортування стали ще умовно поділяти не лише на прямі та швидкі а і на внутрішні (ті що обробляються оперативною пам’яттю) та зовнішні.

Метою роботи є: Знайомство з теоретичним положенням, що стосуються методів сортування файлів, реалізація їх на мові програмування Turbo Pascal.

Предмет дослідження: Зовнішні алгоритми сортування послідовностей.

Об'єкт дослідження: Математична модель доцільності використання зовнішніх алгоритмів сортування на практиці.

Досягненням мети й відповідно до поставленої гіпотези визначаються наступні завдання:

  1. Вивчити літературу по темі алгоритми сортування файлів;

  2. Проаналізувати зовнішні методи сортування;

  3. Реалізувати на Turbo Pascal алгоритми сортування файлів довільної величини;

  4. Розробити закінчений програмний продукт по темі дослідження;

  5. Провести аналіз математичних моделей різних методів.

1. Сортування прямим злиттям

Перш ніж розглядати зовнішні алгоритми сортування, давайте подумаємо, яким же чином можна відсортувати величезний файл, що не поміщається в оперативній пам’яті? Перше, що приходить на розум, це взяти його, розбити на велику кількість файлів і відсортувавши кожен потім злити. Тому, давайте розглянемо приклад злиття двох відсортованих масивів та проведемо аналіз швидкості його виконання.

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

Нехай у масиві Y з елемента Y[m] починається впорядкована ділянка довжиною s, а з елемента Y[m+s] – впорядкована ділянка довжини r. Наприклад,

Y

1

3

13

2

4

88

M

m+1

m+s-1

m+s

m+s+1

m+s+r

Результатом злиття повинна бути ділянка довжини r+s у масиві X:

X

1

2

3

4

13

88

m

m+1

m+2

m+3

m+s+r

Дане злиття двох ділянок у масиві Y у ділянку масиву X задає процедура:

procedure mrg(var Y: ArT; m, s, r: Indx; var X: ArT);

var mr, k: Indx; i, j: Extind;

begin

mr:= m + s; { mr – початок правої частини }

i:= m; j:= mr; { i та j пробігають ліву й праву ділянки масиву Y}

for k:= m to m + s + r - 1 do {заповнення X[m], …, X[m+s+r-1]}

if i > m + s - 1 then begin X[k]:= Y[j]; j:= j + 1 end

else if j > mr + r - 1 then

begin X[k]:= Y[i]; i:= i + 1 end else

if Y[i] < Y[j] then

begin X[k]:= Y[i]; i:= i + 1 end else

begin X[k]:= Y[j]; j:= j + 1 end

end;

Тепер розглянемо сортування масиву A злиттям. На першому кроці елементи A[1], …, A[n] копіюються в допоміжний масив B[1], …, B[n]. Його елементи розглядаються парами B[1] і B[2], B[3] і B[4] тощо, як упорядковані послідовності довжиною lp = 1 і зливаються за допомогою процедури mrg в масив A. Тепер там є впорядковані ділянки довжиною 2. За непарного n останній елемент A[n] залишається без змін як послідовність довжиною 1.

На наступному кроці після копіювання в масив B зливаються пари упорядкованих ділянок B[1]B[2] і B[3]B[4], B[5]B[6] і B[7]B[8] тощо. З'являються впорядковані ділянки довжиною 4. Нехай t=n mod 4 – довжина залишку масиву після останньої повної четвірки елементів. При t=1 або t=2 останні t елементів утворюють упорядковану ділянку після попереднього кроку. При t=3 зливаються упорядкована пара B[n-1]B[n-2] та ділянка B[n] у ділянку довжиною t.

Кроки повторюються з подвоєнням довжин упорядкованих ділянок lp, поки lp < n.

Розглянемо сортування злиттям масиву <11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1> довжини n=11. Упорядковані послідовності в ньому вказуються в дужках <>, а пари таких, що зливаються, відокремлені ";":

< <11><10>; <9><8>; <7><6>; <5><4>; <3><2>; <1> >, lp=1

< <10, 11><8, 9>; <6, 7><4, 5>; <2, 3><1> >, lp=2

< <8, 9, 10, 11><4, 5, 6, 7>;<1, 2, 3> >, lp=4

< <4, 5, 6, 7, 8, 9, 10, 11><1, 2, 3> >, lp=8

<1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11>, lp=16, lp³ n.

Як бачимо, нам знадобилося 4 кроки злиття для того, щоб одержати впорядований масив.

Даний спосіб сортування можна описати наступною процедурою Mrgsort:

procedure Mrgsort (var A: ArT; n: Indx);

var B: ArT;

lp, npp, cpp, bpp, tl: integer;

begin



Скачать работу

Похожие работы:

  1. Порівняльний аналіз ефективності та складності алгоритмів пошуку елементів у масивах

    Курсовая работа >> Информатика
    ... Курсова робота на тему: "Порівняльний аналіз ефективності та складності алгоритмів пошуку елементів у ... язані із пошуком певного елемента, послідовності елементів у певному масиві, ... лькості використаних операцій провести сортування масиву даних, а вже пот ...
  2. Порівняльний аналіз ефективності та складності прямих алгоритмів сортування масивів

    Курсовая работа >> Информатика
    ... Порівняльний аналіз ефективності та складності прямих алгоритмів сортування масивів" Зміст Вступ Розділ І. Алгоритми, методи сортування Розділ ІІ. Прямі методи сортування ... дві групи - сортування масивів і сортування файлів (послідовностей). Іноді їх ...
  3. Курс лекций по Логістика

    Реферат >> Логика
    ... і та складності: ... послідовност ... порівняльний аналіз традиційної та логістичної концепції організації виробництва. Таблиця 5.1 Порівняльний анал ... ефективними способами; - висока ефективн ... сортування, затарювання та пакування готової продукції, вантажопереробні та ...
  4. Інформаційні системи в економіці

    Учебное пособие >> Экономика
    ... події Сортування; внесення ... Алгоритмічна Алгоритми ... планування та аналізу ... і складності впровадження ... текстові файли або файли DBF ... послідовності : структурний аналіз; ... порівняльної важливості задоволення одних потреб і ігнорування інших, порівняльної ефективност ...
  5. Інформаційна підтримка внутрішнього контролю на неприбутковому підприємстві

    Дипломная работа >> Менеджмент
    ... ій послідовності, представленій на рис. 1.1. Рис. 1.1. Послідовн ... та звіти розробляються одночасно з безпосереднім впровадженням системи. Порівняльна ... порівняння у системі планових та фактичних показників роботи та впровадження аналізу економічної ефективност ...

Хочу больше похожих работ...