Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Порівняльна характеристика методів сортування
Інформація про навчальний заклад
ВУЗ:
Інші
Інститут:
О
Факультет:
Педагогічний
Кафедра:
Не вказано
Інформація про роботу
Рік:
2016
Тип роботи:
Курсова робота
Предмет:
Об’єктно-орієнтоване програмування
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і нaуки Укрaїни
Вінницький держaвний педaгогічний університет імені Михaйлa Коцюбинського
Інститут мaтемaтики, фізики і технологічної освіти
Кaфедрa мaтемaтики тa інформатики
Курсова робота з об'єктно-орієнтованого програмування.
на тему
«Порівняльна характеристика методів сортування»
студентa групи 3-АІ,
спеціальності Інформатика*,
Панченка О. В.
Вінниця 2016
Завдання на курсову роботу
Календарний план виконання курсової роботи
Реферат
Метою нашої дослідницької роботи є ознайомлення з простими алгоритмами сортування, спроба проаналізувати їх і висвітлити кожен з них і написати програму, яка б виконувала сортування деякої послідовності за допомогою різних простих алгоритмів сортування.
Отже об'єктом дослідження буде сортування за допомогою різних методів. Предметом дослідження є параметри сортування(час, пам’ять, простота алгоритму та ітерації)
Для виконання мети ми поставили перед собою завдання:
Ознайомитися з алгоритмами сортування;
Проаналізувати алгоритми сортування;
Написати програму, яка виконує сортування послідовності за допомогою різних швидких алгоритмів сортування.
Результатом виконаної роботи є програма, яка сортує масив з десяти елементів методом бульбашки, методом вибору, та методом вставок.
Результат можна використовувати для сортування великих цілих чисел, що широко використовується у логістиці та багатьох інших сферах.
Отже, дана робота допомагає швидко сортувати цілі числа, та показує, яким методом вигідніше скористатись. Адже хоча для великих обсягів даних ці сортування будуть повільними, а починаючи із певної величини, вони занадто повільні, щоб їх можна було використати в практиці. Проте, вони ідеально підходять для сортування невеликої кількості елементів. З простих методів сортування найкращим є сортування вставкою.
Зміст
Завдання на курсову роботу 2
Календарний план виконання курсової роботи 3
Реферат 4
Вступ 6
1.1 Аналіз літературних даних і постановка проблеми 9
1.2 Порівняльний аналіз методів сортування масиву чисел 15
2. Методи сортування масивів 22
Висновки 26
Література 28
Додаток 1. 29
Вступ
В останні роки програмування для обчислювальних машин виділилося в деяку дисципліну, володіння якої стало основним і ключовим моментом, що визначає успіх багатьох інженерних проектів, а сама вона перетворилася на об'єкт наукового дослідження. З ремесла програмування перейшло в розряд академічних наук. Перший великий внесок у її становлення зробили Е. Дейкстра і Ч. Хоар. Основне увагу в їх роботах приділяється побудові та аналізу програм, а більш точно - структурі алгоритмів, які подаються текстом програми. Програми являють собою конкретні, засновані на деякому реальному поданні і будові даних втілення абстрактних алгоритмів.
Алгоритм - це формально описана обчислювальна процедура, яка отримує вихідні дані, звані його аргументом, і видає результат обчислень на вихід. Алгоритми будуються для вирішення тих чи інших обчислювальних задач. Формулювання завдання описує, яким вимогам повинна задовольняти рішення задачі, а алгоритм, вирішальний цю задачу, являє собою метод, застосування якого дозволяє отримати об'єкт, що задовольняє цим вимогам. В даний час слово «Алгоритм» асоціюється, в основному, з комп'ютерами та іншими засобами обчислювальної техніки, хоча розробка алгоритмів почалася на зорі розвитку математики, задовго до появи обчислювальних машин. В останні півстоліття творчий процес створення обчислювальних алгоритмів став найбільш інтенсивним, це пов'язано з виникненням, удосконаленням і розвитком інформаційних технологій та всієї комп'ютерної індустрії.
Для того щоб розробляти власні алгоритми доцільно спочатку вивчити вже існуючі, методи аналізу їх параметрів і ефективності. Тим більше, що світовий досвід програмування нараховує їх безліч. Розглядаючи різні методи вирішення однієї і тієї ж задачі, корисно проаналізувати, скільки обчислювальних ресурсів вони вимагають (час, пам'ять), і вибрати найбільш ефективний. Звичайно, в цьому випадку потрібно враховувати яка модель обчислювальної системи використовується для їх виконання: однопроцесорна ЕОМ або багатопроцесорний комплекс. При аналізі часу роботи алгоритму слід враховувати ряд факторів, що роблять певний вплив на результат: розмірність вихідних даних, структура даних в яку вони організовані, їх місця зберігання і розміщення під час виконання програми.
Програмування містить цілу низку важливих внутрішніх задач. Однією з найбільш важливих таких задач для програмування є задача сортування. Під сортуванням звичайно розуміють перестановки елементів будь-якої послідовності у визначеному порядку. Ця задача є однією з найважливіших тому, що її метою є полегшення подальшої обробки певних даних і, насамперед, задачі пошуку. Так, одним з ефективних алгоритмів пошуку є бінарний пошук. Він працює швидше ніж, наприклад, лінійний пошук, але його можливо застосовувати лише за умови, що послідовність вже упорядкована, тобто відсортована.
Взагалі, відомо, що в будь-якій сфері діяльності, що використовує комп’ютер для запису, обробки та збереження інформації, усі дані зберігаються в базах даних, які також потребують сортування. Певна впорядкованість для них дуже важлива, адже користувачеві набагато легше працювати з даними, що мають певний порядок. Так, можна розташувати всі товари по назві або відомості про співробітників чи студентів за прізвищем або роком народження, тощо.
Актуальність курсової роботи полягає в тому що задача сортування в програмуванні не вирішена повністю. Адже, хоча й існує велика кількість алгоритмів сортування, все ж таки метою програмування є не лише розробка алгоритмів сортування елементів, але й розробка саме ефективних алгоритмів сортування. Ми знаємо, що одну й ту саму задачу можна вирішити за допомогою різних алгоритмів і кожен раз зміна алгоритму приводить до нових, більш або менш ефективних розв’язків задачі. Основними вимогами до ефективності алгоритмів сортування є перш за все ефективність за часом та економне використання пам’яті.
Метою нашої дослідницької роботи є ознайомлення з простими алгоритмами сортування, спроба проаналізувати їх і висвітлити кожен з них і написати програму, яка б виконувала сортування деякої послідовності за допомогою різних простих алгоритмів сортування.
Отже об'єктом дослідження буде сортування за допомогою різних методів. Предметом дослідження є параметри сортування(час, пам’ять, простота алгоритму та ітерації)
Для виконання мети ми поставили перед собою завдання:
Ознайомитися з алгоритмами сортування;
Проаналізувати алгоритми сортування;
Написати програму, яка виконує сортування послідовності за допомогою різних швидких алгоритмів сортування.
Сортування варто розуміти, як процес перегрупування заданої множини об'єктів в деякому конкретному порядку. Мета сортування - полегшити наступний пошук елементів в такій відсортованій множині.
Вибір алгоритму залежить від структури даних, що обробляються. У випадку сортування ця залежність настільки велика, що відповідні методи навіть були розбиті на дві групи - сортування масивів і сортування файлів (послідовностей). Іноді їх називають внутрішнім і зовнішнім і сортуванням, оскільки масиви зберігаються в швидкій внутрішній пам’яті (оперативній) із довільним доступом, а файли розміщуються в менш швидкій, проте більш об'ємній зовнішній пам'яті.
Аналіз літературних даних і постановка проблеми
Сортуванням взагалі називають процес впорядковування множини елементів за певною ознакою. Наприклад, у житті ми стикаємося з таким процесом, коли хочемо відсортувати фрукти за якістю на вітрині, учнів за зростом на уроці фізкультури, банки із фарбами за їх кольором при ремонті тощо. В математиці при побудові многокутника за даними у довільному порядку координатами вершин їх зручно попередньо відсортувати за певною ознакою, наприклад за зростанням абсцис, спаданням ординат, відстанню до початку координат, кутом нахилу радіус-вектора вершини до осі чи будь-якою іншою ознакою.
Саму ж ознаку, за якою виконується сортування, називають ключем сортування. Так, при впорядкуванні слів у словнику ключем є їх лексикографічний порядок
Лексикографічний порядок — це природний спосіб упорядкування послідовностей на основі порівняння індивідуальних символів. На множині всіх розміщень із r елементів означимо порівняння таким чином: / < / , якщо / .
У такому разі говорять, що перестановка / менша від перестановки / , або перестановка / більша від перестановки/
У програмуванні такий лексикографічний порядок використовують для порівняння стрічок, тільки замість чисел беруть символи ASCII чи Unicode (в залежності від типу стрічки) і лексикографічний порядок відповідає порядку символів. Якщо розглянути числа в позиційних системах числення (наприклад, у двійковій або десятковій системі) як слова в алфавіті цифр, то їх лексикографічний порядок збігається із звичайним, якщо всі числа, які порівнюємо мають однакове число розрядів. У загальному випадку ці два види упорядкування можуть не збігатися: наприклад, 10<1073 і 20<1073, але 10 <= 1073, а 20 =>1073. Для того щоб вони збігалися необхідно вирівняти число розрядів у всіх чисел, які порівнюємо, дописуючи зліва нулі. У наведеному прикладі отримаємо 0020 <= 1073. Таке вирівнювання автоматично відбувається при запису цілих чисел в ЕОМ. Послідовність чисел у будь-якій системі числення, записаних у фіксованій розрядній сітці (000, 001, 002, 003, 004, 005, ..., 999).
Лексикографічне упорядкування для чисел виду 06.09.99 (шосте вересня 1999 року) не збігається з природнім упорядкуванням дат від ранніх до пізніх, наприклад 06.09.99 лексикографічно «старше» третього числа будь-якого місяця другого року. Щоб зростання дат збігалося з лексикографічним упорядкуванням, зазвичай цифри потрібно «перевернути» тобто рік помістити зліва: 99.09.06.
Як бачимо, об’єктами впорядкування можуть бути найрізноманітніші елементи. Головним є визначення відношення порядку на сортованій множині елементів, тобто для будь-яких двох елементів множини А і В необхідно виділити закон визначення їх взаємного правильного розміщення (об’єкт A має стояти після об’єкту B чи перед ним).
Як відомо, всі дані, що зберігаються на комп’ютері, оцифровані, тобто представлені у числовому вигляді, тому традиційно програмісти, говорячи про сортування, розуміють впорядкування за зростанням або спаданням числових величин.
Для впорядкування множини елементів розроблено багато алгоритмів сортування, які мають велике практиче значення. Завдяки впорядкуванню значно спрощується пошук необхідних даних у великих інформаційних системах, з’являються спрощені методи їх обробки.
У навчальному процесі ця тема теж має дуже велике значення, оскільки учням, що опановують премудрощами мови програмування, надається можливість реалізувати вже відомі алгоритми, використовуючи мову, що вивчається, як інструмент. Фактично у шкільній програмі ця тема вивчається тоді, коли учні вже знають основні структури даних (скалярні величини та структурований тип даних масив) і базові конструкції мови програмування (циклічні, розгалужені та допоміжні алгоритми). Тому перед ними постає питання, як відомі з життя дії описати, використовуючи особливості комп’ютерного „мислення” та мови програмування. Учням можна дати самостійно пофантазувати і спробувати придумати свій власний алгоритм впорядкування даних. І хоча, як правило, придуманий метод впорядкування буде описувати відомий з життя алгоритм, це дуже заохочує учнів до роботи, зацікавлює їх складним мистецтвом створення нових алгоритмів та їх реалізації.
Традиційно розрізняють внутрішнє та зовнішнє сортування. Перший різновид впорядковує дані, що знаходяться в оперативній (внутрішній) пам’яті комп’ютера, а другий оперує із даними на зовнішніх носіях такого об’єму, для якого не вистачає оперативної пам’яті.
Почнемо розгляд методів впорядкування із внутрішніх методів сортування. Всі ці методи можна класифікувати за кількома ознаками. Так, існують методи, що виконують сортування даних у тому ж масиві, в якому їх отримали (сортування на місці), але є і такі, що заповнюють інший масив за деяким правилом, не порушуючи початковий набір даних. Очевидно, що перший з методів оптимальніший за використанням ресурсів пам’яті, проте, як побачимо далі, сам алгоритм буде або складнішім, або довшим за часом виконання.
Усі алгоритми сортування також поділяються на прості – ті, що працюють порівняно повільно, проте не потребують великих зусиль на реалізацію і відлагодження – та швидкі – ті, що сортують великі масиви даних досить швидко, але зазвичай мають достатньо складний у розумінні та громіздкий алгоритм.
Зверніть також увагу на те, що зберігатися дані в оперативній пам’яті можуть по різному. Відомо, що у більшості мов програмування можливе як статичне, так і динамічне виділення пам’яті. У першому випадку оперативна пам’ять для зберігання масиву даних виділяється на початку роботи програми і вважається зайнятою під час її роботи. Цей метод виділення пам’яті простіший, але не економічний, оскільки на початку роботи програми необхідно зарезервувати стільки пам’яті, скільки вистачить на будь-який об’єм даних у деяких межах. У другому випадку пам’ять для збереження даних виділяється за необхідністю (динамічно), тому цей метод є раціональнішим хоча і складнішим.
Майже всі алгоритми внутрішього сортування можна реалізувати на обох типах наборів даних. Далі, при описі методів сортування ми будемо виділяти деякі відмінності в алгоритмах для тих чи інших структур даних.
Ще один нюанс: очевидно, що всі алгоритми сортування “на місці” (а такими є перевежна більшість із відомих) потребують взаємного обміну двох елементів. Задача тривіальна, але вже тут можна пофантазувати і придумати кілька методів виконання цієї дії.
Стандартний метод – це використання третьої змінної. Елементи масиву даних мають однаковий тип, тому й змінна, що використовується для обміну, теж повинна мати той самий тип.
Незважаючи на значну кількість алгоритмів та вдосконалень відомих методів сортування, основними, серед них є сім методів:
метод лінійного вибору;
лінійного вибору з обміном;
лінійного вибору з підрахунком;
парного обміну;
стандартного обміну;
просіювання;
лінійної вставки.
Існуючі методи сортування, кожен з яких має свої переваги та недоліки , можна згрупувати у відповідності з визначальними принципами функціонування у три основні категорії:
— сортування за допомогою включення (by insertion);
— сортування за допомогою виділення (by selection);
— сортування за допомогою обмінів (by exchange).
Двома найбільш важливими програмними аспектами є об’єм машинного часу, необхідний для роботи програми сортування, і об’єм пам’яті, необхідний для цієї програми.
Чaс сортувaння – основний пaрaметр, що хaрaктеризує швидкодію aлгоритму.
Необхіднa пaм'ять – один з пaрaметрів, який хaрaктеризується тим, що ряд aлгоритмів сортувaння вимaгaють виділення додaткової пaм'яті для тимчaсового зберігaння дaних. При оцінці пaм'яті що використовується не буде врaховувaтися місце, яке зaймaє вихідний мaсив дaних тa витрaти які не зaлежaть від вхідної послідовності, нaприклaд, нa зберігaння коду прогрaми.
Стійкість – це пaрaметр, який відповідaє зa те, що сортувaння не змінює взaємного розтaшувaння рівних елементів.
Природність поведінки – пaрaметр, який вкaзує нa ефективність методу при обробці вже відсортовaних, aбо чaстково відсортовaних дaних. Aлгоритм поводиться природно, якщо врaховує цю хaрaктеристику вхідної послідовності і прaцює крaще.
Доброю мірою ефективності може бути число необхідних порівнянь та число перепосилань (перестановок) елементів масиву. Ці величини є функціями від числа елементів n, які сортуються. Ефективні алгоритми сортування потребуються порядку n
17.01.2017 14:01-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора