Курсова робота
на тему: В«Порівняльне дослідження ефективності методів сортування В»
Завдання
Порівняльне дослідження ефективності методів сортування.
Базова структура даних - вектор
Методи сортування - метод Шелла, метод Флойда.
Примітка: Порівняння приводитися у вигляді графіків залежностей кількості порівнянь і числа перестановок елементів від обсягу даних.
Введення
В останні роки програмування для обчислювальних машин виділилося в деяку дисципліну, володіння якої стало основним і ключовим моментом, що визначає успіх багатьох інженерних проектів, а сама вона перетворилася на об'єкт наукового дослідження. З ремесла програмування перейшло в розряд академічних наук. Перший великий внесок у її становлення зробили Е. Дейкстра і Ч. Хоар. Основне увагу в їх роботах приділяється побудові та аналізу програм, а більш точно - структурі алгоритмів, які подаються текстом програми. Програми являють собою конкретні, засновані на деякому реальному поданні і будові даних втілення абстрактних алгоритмів.
Алгоритм - це формально описана обчислювальна процедура, яка отримує вихідні дані, звані його аргументом, і видає результат обчислень на вихід. Алгоритми будуються для вирішення тих чи інших обчислювальних задач. Формулювання завдання описує, яким вимогам повинна задовольняти рішення задачі, а алгоритм, вирішальний цю задачу, являє собою метод, застосування якого дозволяє отримати об'єкт, що задовольняє цим вимогам. В даний час слово В«АлгоритмВ» асоціюється, в основному, з комп'ютерами та іншими засобами обчислювальної техніки, хоча розробка алгоритмів почалася на зорі розвитку математики, задовго до появи обчислювальних машин. Формула Герона для обчислення кореня квадратного з неотрицательного числа, процес знаходження найбільшого загального дільника, виявлення простих чисел з чисел натурального ряду (В«решето Ератосфена В») все це алгоритми, які можна реалізувати за допомогою будь-якого мови програмування і на будь-якій сучасній ЕОМ. В останні півстоліття творчий процес створення обчислювальних алгоритмів став найбільш інтенсивним, це пов'язано з виникненням, удосконаленням і розвитком інформаційних технологій та всієї комп'ютерної індустрії.
Для того щоб розробляти власні алгоритми доцільно спочатку вивчити вже існуючі, методи аналізу їх параметрів і ефективності. Тим більше, що світовий досвід програмування нараховує їх безліч. Розглядаючи різні методи вирішення однієї і тієї ж задачі, корисно проаналізувати, скільки обчислювальних ресурсів вони вимагають (час, пам'ять), і вибрати найбільш ефективний. Звичайно, в цьому випадку потрібно враховувати яка модель обчислювальної системи використовується для їх виконання: однопроцесорна ЕОМ або багатопроцесорний комплекс. При аналізі часу роботи алгоритму слід враховувати ряд факторів, що роблять певний вплив на результат: розмірність вихідних даних, структура даних в яку вони організовані, їх місця зберігання і розміщення під час виконання програми.
При порівнянні методів сортування, з точки зору їх ефективності, виконують багаторазове тестування розробленої програми на даних різної довжини з усілякими перестановками. Для кожного вхідного вектора значень розмірності n визначається число порівнянь sr і число обмінів m , виконуваних з його координатами в процесі роботи алгоритму. Отримані статистичні дані відображають середні значення параметрів, на підставі яких можна зробити висновок про ефективність того або іншого методу сортування або пошуку.
При порівнянні способів організації деякої логічної структури даних, наприклад, списку або дерева, в процесі аналізу враховують, наскільки швидко і просто виконується її формування за допомогою деякої фізичної реалізації, скільки часу і обчислювальних ресурсів потрібно для її модифікації (вставки, видалення, перестроювання), як швидко здійснюється пошук необхідної інформації в такій структурі.
Алгоритми сортування інформації
Хоча у словниках слово В«СортуванняВ» визначається як процес розділення об'єктів по виду або сорту, програмісти традиційно використовують його в набагато більш вузькому сенсі, позначаючи їм таку перестановку предметів, при якій вони розташовуються в порядку зростання або спадання.
Під сортуванням масивів розуміють процес перестановки елементів масиву в певному порядку.
Мета сортування - полегшити подальший пошук елементів у відсортованому масиві.
Методи сортування важливі при обробці даних, з ними пов'язані багато фундаментальні прийоми побудови алгоритмів.
Сортировки можуть бути виконані з використанням різних алгоритмів: як простих, так і ускладнених (Але більш ефективних). Основна вимога до методів сортування: економне використання пам'яті і швидкодія. Перша вимога може бути виконане, якщо переупорядоченіе елементів буде виконуватися на тому ж місці. Хороші алгоритми сортування вимагають порядку n * lognсравненій.
Прості методи сортування можна розбити на три основні класи залежно від лежачого в їх основі прийому:
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]), діапазон індексів розширюється.
Метод Шелла
Для алгоритму сортування, який кожного разу переміщує запис тільки на одну позицію, середній час буде в кращому випадку пропорційно N 2 , тому що в процесі сортування кожна запис повинна пройти в середньо...
