Курсова робота - Порівняльний аналіз методу Шелла і методу Бетчера за критерієм ефективності

n1.doc (8 стор.)
Оригінал


  1   2   3   4   5   6   7   8



Федеральне агентство з освіти

ФІЛІЯ ДЕРЖАВНОГО ОСВІТНЬОГО УСТАНОВИ ВИЩОЇ ОСВІТИ

Московського державного індустріального університету в м. Вязьмі Смоленської області

(ВФ ГОУ МГИУ)


Курсова робота


З дисципліни: Структури та алгоритми комп'ютерної обробки даних

Тема: Порівняльний аналіз методу Шелла і методу Бетчера за критерієм ефективності застосування до різних вихідним даним

Спеціальність: 080801 «Прикладна інформатика в економіці»


2009

ЗМІСТ


Сортування Шелла. 9

1.3 Паралельна сортування Бетчера 10

Аналіз сортування Бетчера. 12

РОЗДІЛ 3 ПОРІВНЯЛЬНИЙ АНАЛІЗ МЕТОДІВ Шеллі і БЕТЧЕРА ПО КРИТЕРІЮ ЕФЕКТИВНОСТІ ЗАСТОСУВАННЯ До РІЗНИМ ВИХІДНИХ ДАНИХ 21

3.3 Порівняльний аналіз двох алгоритмів 32

ВИСНОВОК 35

Додаток А Програма № 1: Метод Шелла 39

Додатку Б Програма № 2: Метод Бетчера 41

ЗАВДАННЯ
Вивчити способи сортування та пошуку інформації із застосуванням методів сортування Шелла і Бетчера.

Розробити програми на мові Turbo Pascal 7.0. для реалізації вивчених методів. Побудувати регресійні моделі для аналізу ефективності методів. Виконати порівняльний аналіз алгоритмів Шелла і Бетчера на основі отриманих регресійних моделей.
ВСТУП
В останні роки програмування для обчислювальних машин виділилося в деяку дисципліну, володіння якої стало основним і ключовим моментом, що визначає успіх багатьох інженерних проектів, а сама вона перетворилася на об'єкт наукового дослідження. З ремесла програмування перейшло в розряд академічних наук. Перший великий внесок у її становлення зробили Е. Дейкстра і Ч.Хоар. Основна увага в їхніх роботах приділяється побудові та аналізу програм, а більш точно - структурі алгоритмів, які подаються текстом програми. Програми являють собою конкретні, засновані на деякому реальному поданні і будові даних втілення абстрактних алгоритмів.

Алгоритм - це формально описана обчислювальна процедура, яка отримує вихідні дані, звані його аргументом, і видає результат обчислень на вихід. Алгоритми будуються для вирішення тих чи інших обчислювальних задач. Формулювання завдання описує, яким вимогам повинна задовольняти рішення задачі, а алгоритм, вирішальний цю задачу, являє собою метод, застосування якого дозволяє отримати об'єкт, що задовольняє цим вимогам. В даний час слово «алгоритм» асоціюється, в основному, з комп'ютерами та іншими засобами обчислювальної техніки, хоча розробка алгоритмів почалася на зорі розвитку математики, задовго до появи обчислювальних машин. Формула Герона для обчислення кореня квадратного з неотрицательного числа, процес знаходження найбільшого спільного дільника, виявлення простих чисел з чисел натурального ряду («решето Ератосфена») все це алгоритми, які можна реалізувати за допомогою будь-якої мови програмування і на будь-якій сучасній ЕОМ. В останні півстоліття творчий процес створення обчислювальних алгоритмів став найбільш інтенсивним, це пов'язано з виникненням, удосконаленням і розвитком інформаційних технологій і всієї комп'ютерної індустрії.

Для того щоб розробляти власні алгоритми доцільно спочатку вивчити вже існуючі, методи аналізу їх параметрів і ефективності. Тим більше, що світовий досвід програмування нараховує їх безліч. Розглядаючи різні методи вирішення однієї і тієї ж задачі, корисно проаналізувати, скільки обчислювальних ресурсів вони вимагають (час, пам'ять), і вибрати найбільш ефективний. Звичайно, в цьому випадку потрібно враховувати яка модель обчислювальної системи використовується для їх виконання: однопроцесорна ЕОМ або багатопроцесорний комплекс. При аналізі часу роботи алгоритму потрібно враховувати ряд чинників, надають певний вплив на результат: розмірність вихідних даних, структура даних в яку вони організовані, їх місця зберігання та розміщення під час виконання програми.

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

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


РОЗДІЛ 1 АЛГОРИТМИ СОРТУВАННЯ І ПОШУКУ ІНФОРМАЦІЇ
1.1 Класифікація алгоритмів сортування та пошуку інформації
Хоча в словниках слово «сортування» визначається як процес розділення об'єктів по виду або сорту, програмісти традиційно використовують його в набагато більш вузькому сенсі, позначаючи їм таку перестановку предметів, при якій вони розташовуються в порядку зростання або зменшення.

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

Мета сортування - полегшити подальший пошук елементів у відсортованому масиві.

Методи сортування важливі при обробці даних, з ними пов'язані багато фундаментальні прийоми побудови алгоритмів.

Сортування можуть бути виконані з використанням різних алгоритмів: як простих, так і ускладнених (але більш ефективних). Основна вимога до методів сортування: економне використання пам'яті і швидкодія. Перша вимога може бути виконано, якщо переупорядоченіе елементів буде виконуватися на тому ж місці. Хороші алгоритми сортування вимагають порядку n * log n порівнянь.

Прості методи сортування можна розбити на три основні класи залежно від лежачого в їх основі прийому:

1.сортіровка вибором;

2.сортіровка обміном;

3.сортіровка включенням.

Прості методи сортування вимагають порядку n * n порівнянь елементів (ключів).

Прості методи сортування.

Сортування за допомогою простого вибору.

Сортування заснована на ідеї багаторазового вибору (знаходиться спочатку найбільший елемент, потім другий за величиною і т.д.) і зводиться до наступного:

1.найті елемент з найбільшим значенням;

2.поменять значеннями знайдений елемент і останній;

3.уменьшіть на одиницю кількість переглядаються елементів;

4.Якщо <кількість елементів для наступного перегляду більше одиниці> то <повторити пункти, починаючи з 1-го>.

Алгоритм:

Цикл за кількістю переглядаються елементів {i: = n, n-1, ..., 2}

Знайти номер k максимального елемента серед a [1], a [2], ..., a [i]

Поміняти місцями значення елементів a [k] і a [i]

Сортування обміном (методом бульбашки).

Сортування обміном передбачає систематичний обмін значеннями (місцями) тих пар, у яких порушується впорядкованість, до тих пір, поки таких пар не залишиться.

Алгоритм:

Цикл за кількістю переглядів

Цикл за кількістю порівнюваних значень при черговому перегляді

Якщо <впорядкованість в парі порушена> то <виконати обмін значеннями>.

Кількість переглядів (повторень) у зовнішньому циклі одно n-1.Він може бути зменшено, якщо i-й крок показав, що масив уже впорядкований (у внутрішньому циклі не було перестановок).

Сортування включенням.

Сортування заснована на наступному: передбачається, що елементи a [1], a [2], ..., a [i-1] впорядковані, a [i] вставляється на відповідне місце, не порушуючи властивості впорядкованості. Для цього a [i] порівнюється по черзі з a [i-1], a [i-2], ... до тих пір, поки не буде виявлено, що елемент a [i] слід вставити між a [j], a [ j-1] (j - номер елемента в a [1 ... i-1], за яким слід вставити a [i]). Тоді елементи a [j +1], ..., a [i-1] зсуваються на одну позицію вправо, а нова запис поміщається в позицію j +1. Зручно поєднувати порівняння і переміщення.

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

(A [0]: = a [i]), діапазон індексів розширюється.
1.2 Метод Шелла
Для алгоритму сортування, який кожного разу переміщує запис тільки на одну позицію, середній час буде в кращому випадку пропорційно N 2, тому що в процесі сортування кожна запис повинна пройти в середньому N позицій. Тому, якщо бажано отримати метод, істотно перевершує по швидкості метод простих вставок, необхідний механізм щоб записи могли переміщатися великими стрибками, а не короткими кроками.

Такий метод запропонований в 1959 році Дональдом Л. Шеллом [Donald L. Shell, CACM 2,7 (Java, 1959), 30-32] і відомий у всьому світі під ім'ям свого автора. Нехай є масив записів R1, R2, ...., R16. Ділимо 16 записів на 8 груп по два записи в кожній групі: (R1, R9), (R2, R10), ...., (R8, R16). Сортуємо вибрані пари записів у порядку, наприклад, зростання, тобто якщо в парі (R2, R10): R2> R10, то R2 і R10 міняємо місцями: R1, R10, R3, R4, R5, R6, R7, R8, R9, R2, R11, R12, R13, R14, R15, R16. Те ж саме виконується і для інших пар записів. Це сортування із зсувом 8. Цей процес називається першим проходом. Розділимо тепер запису на чотири групи по чотири записи в кожній: (R1, R5, R9, R13), ..., (R4, R8, R12, R16). Потім знову розсортуємо кожну групу окремо. Це сортування із зсувом 4. На третьому проході відсортуємо 2 групи по 8 записів: (R1, R3, R5, R7, R9, R11, R13, R15) і (R2, R4, R6, R8, R10, R12, R14, R16). Це сортування із зсувом 2. Процес завершується четвертим проходом, під час якого сортуються всі 16 записів. Це сортування із зсувом 1. У кожній з проміжних стадій сортування беруть участь або порівняно короткі масиви, або вже порівняно добре впорядковані масиви, тому на кожному етапі можна користуватися методом простих вставок. Метод сортування Шелла ще називається з «убутним зміщенням», оскільки кожен прохід характеризується зміщенням h, таким, що сортуються записи, кожна з яких відстоїть від попередньої на h позицій. Послідовність значень зміщень 8, 4, 2, 1 не слід вважати незмінною, можна користуватися будь-якою послідовністю зсувів, але останнім зсув має дорівнювати 1.

Метод сортування Шелла також відомий під ім'ям Shellsort і методу сортування з «убутним зміщенням», оскільки кожен прохід характеризується зміщенням h, таким, що сортуються записи, кожна з яких відстоїть від попередньої на h позиції. Послідовність значень зміщень 8, 4, 2, 1 не слід вважати непорушною; можна користуватися будь-якою послідовністю h t -1, h t -2,..., h 0. але останнім зсув h 0 має дорівнювати 1. Наприклад, у таблиці 2 продемонстрована сортування тих же даних із зсувами 7, 5, 3, 1. Як буде показано нижче, вибір значень зміщень на послідовних проходах має досить істотне значення для швидкості сортування.
Навчальний матеріал
© ukrdoc.com.ua
При копіюванні вкажіть посилання.
звернутися до адміністрації