Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Порозрядне сортування
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Не вказано
Інформація про роботу
Рік:
2012
Тип роботи:
Інші
Предмет:
Алгоритми та методи обчислень
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки, молоді та спорту України
Національний університет ”Львівська політехніка”
з курсу алгоритми та методи обчислень
на тему: «Порозрядне сортування»
Львів - 2012
Зміст
Вступ……………………………………………………………3
Сортування……………………………………………………..4
Порозрядне сортування…………………………………...…..7
Алгоритм…………………………………………………….....8
Порозрядне сортування для списків……………………….....9
Порозрядне сортування для масивів…………………..…......10
Ефективність порозрядної сортування……………………....13
Література……………………………………………………....14
Вступ
В наш час нові інформаційні технології посідають дуже важливе місце не лише в спеціалізованих, але й в повсякденних сферах життя. Комп’ютери застосовуються в бізнесі, менеджменті, торгівлі, навчанні та багатьох інших сферах діяльності людини. Нові інформаційні технології дуже актуальні в наш час і потребують багато уваги для подальшої розробки та вдосконалення. Поряд з цим, велике значення має також і програмування, яке є одним із фундаментальних розділів інформатики і тому не може залишатись осторонь.
Програмування містить цілу низку важливих внутрішніх задач. Однією з найбільш важливих таких задач для програмування є задача сортування. Під сортуванням звичайно розуміють перестановки елементів будь-якої послідовності у визначеному порядку. Ця задача є однією з найважливіших тому, що її метою є полегшення подальшої обробки певних даних і, насамперед, задачі пошуку. Так, одним з ефективних алгоритмів пошуку є бінарний пошук. Він працює швидше ніж, наприклад, лінійний пошук, але його можливо застосовувати лише за умови, що послідовність вже упорядкована, тобто відсортована.
Взагалі, відомо, що в будь-якій сфері діяльності, що використовує комп’ютер для запису, обробки та збереження інформації, усі дані зберігаються в базах даних, які також потребують сортування. Певна впорядкованість для них дуже важлива, адже користувачеві набагато легше працювати з даними, що мають певний порядок. Так, можна розташувати всі товари по назві або відомості про співробітників чи студентів за прізвищем або роком народження, тощо.
Задача сортування в програмуванні не вирішена повністю. Адже, хоча й існує велика кількість алгоритмів сортування, все ж таки метою програмування є не лише розробка алгоритмів сортування елементів, але й розробка саме ефективних алгоритмів сортування. Ми знаємо, що одну й ту саму задачу можна вирішити за допомогою різних алгоритмів і кожен раз зміна алгоритму приводить до нових, більш або менш ефективних розв’язків задачі. Основними вимогами до ефективності алгоритмів сортування є перш за все ефективність за часом та економне використання пам’яті.
Метою нашої дослідницької роботи є ознайомлення з методами впорядкування об’єктів, а саме алгоритмами сортування, спроба проаналізувати їх і висвітлити кожен з них. Також метою даної курсової роботи є порівняльний аналіз основних методів сортування, використовуваних для обробки даних, вивчення характеристик і особливостей кожного алгоритму сортування.
Сортування
Сортування (sortіng) − процес, що дозволяє впорядкувати безліч подібних даних у зростаючому або спадаючому порядку.
Алгоритми сортування добре досліджені і вивчені. Різні підходи до сортування мають різні характеристики. Хоча деякі методи в середньому можуть бути краще інших, жоден з методів не буде ідеальним для всіх ситуацій, тому кожен програміст повинен мати у своєму розпорядженні кілька різних типів сортування.
Сортування застосовується в усіх без винятку областях програмування, будь-то бази даних чи математичні програми.
Практично кожен алгоритм сортування можна розбити на три частини:
- порівняння, що визначає впорядкованість пари елементів;
- перестановку, що змінює місцями пару елементів;
- власне сортуючий алгоритм, що здійснює порівняння і перестановку елементів доти, поки всі елементи множини не будуть впорядковані.
Подібними властивостями володіють і ті п'ять алгоритмів сортування, що розглянуті нижче. Вони відібрані з безлічі алгоритмів, тому що:
по-перше, найбільш часто використовуються;
по-друге, тому що більшість інших алгоритмів є різними модифікаціями описаних нижче алгоритмів.
Існує два види алгоритмів сортування: сортування масивів, що можуть знаходитися як в операційній пам'яті, так і на диску у вигляді файлу прямого доступу, і сортування послідовних файлів, що знаходяться на дисках чи магнітних стрічках. В даній курсовій розглядаються в основному сортування першого виду, оскільки воно становить найбільший інтерес для користувачів комп'ютерів.
Основна відмінність між сортуванням масивів і сортуванням послідовних файлів полягає в тому, що кожен елемент масиву є доступним у будь-який час. Це значить, що в будь-який час будь-який елемент масиву може порівнюватися з будь-яким іншим елементом масиву і будь-які два елементи масиву можуть мінятися місцями. Напроти, у послідовному файлі в будь-який момент часу досяжний лише один елемент. Через ці відмінності методи сортування істотно відрізняються для цих двох видів сортування. У загальному випадку при сортуванні даних тільки частина інформації використовується як ключ сортування, що використовується для порівнянь. Коли виконується обмін, передається вся структура даних. Наприклад, у списку поштових відправлень як ключ сортування може використовуватися поштовий індекс, а в операціях обміну до поштового індексу додаються повне ім'я й адреса.
В даній курсовій роботі спочатку будуть розглядатись деякі "элеметарные" методи, які добре працюють для невеликих файлів чи файлів спеціальної структури. Існує кілька причин по яким бажане вивчення цих простих методів.
По-перше, вони дають нам відносно безболісний спосіб вивчити термінологію й основні механізми роботи алгоритмів сортування, що дозволяє одержати необхідну базу для вивчення більш складних алгоритмів.
По-друге, для багатьох задач сортування буває краще використовувати прості методи, чим більш складні алгоритми. І нарешті деякі з простих методів можна розширити до більш кращих методів або використовувати їх для поліпшення більш складних.
Як було зазначено раніше, у деяких програмах сортування краще використовувати прості алгоритми. Програми сортування часто використовуються тільки один раз (або кілька разів). Якщо кількість елементів, які потрібно відсортувати не велика (скажімо менше ніж 500 елементів), то можливо, що використання простого алгоритму буде більш ефективним, чим розробка і налагодження складного алгоритму. Елементарні методи завжди придатні для маленьких файлів (скажімо менших чим 50 елементів); малоймовірно, що складний алгоритм було б розумно використовувати для таких файлів, якщо звичайно не потрібно сортувати велику кількість таких файлів.
Як правило, елементарні методи, що ми будемо обговорювати, роблять приблизно N2 операції для сортування N довільно узятих елементів. Якщо N досить маленьке, то це може і не бути проблемою, і якщо елементи розподілені не довільним чином, то ці алгоритми можуть працювати навіть швидше, ніж складні. Однак варто запам'ятати те, що ці алгоритми не слід використовувати для великих, довільно впорядкованих файлів.
Перед тим, як розглядати який-небудь конкретний алгоритм, було б корисно вивчити термінологію і деякі основні положення про алгоритми сортування.
Під сортуванням розуміють, процес перестановки об'єктів множини у визначеному порядку. Метою алгоритму сортування є переорганізація записів у файлі так, щоб вони розташовувалися в ньому в якому-небудь строго визначеному порядку (звичайно в алфавітному чи числовому).
Нехай нам дана послідовність елементів: a1, a2, ..., an сортування означає − перестановку цих елементів у такому порядку: ak1,ak2, .. ,akn, що при заданій функції впорядкування f(x), справедливе відношення :
f(ak1) <= f(ak2)<= .. <= f(akn) - функція впорядкування не обчислюється, а міститься в кожному елементі у вигляді явного компонента і її значення називають ключем елемента. Отже, для представлення і-ого елемента послідовності щонайкраще підходить структура запису. Ключі є тільки частиною запису (часто дуже маленькою їх частиною), використовуються для керування процесом сортування.
Якщо файл, що сортується цілком міститься в пам'ять або цілком міститься в масиві, то для нього ми використовуємо внутрішні методи сортування. Сортування даних з диска чи стрічки називають зовнішнім сортуванням.
Одна з головних характеристик, що буде нас цікавити в алгоритмі - це час його роботи. Час роботи алгоритму характеризується числом необхідних порівнянь.
Прості алгоритми для сортування N елементів потребують час роботи пропорційний N2, у той час як більш складні алгоритми використовують час пропорційний NlogN. (Можна довести, що ніякий алгоритм сортування не може використовувати менш, ніж NlogN порівнянь між ключами.)
Мірою ефективності алгоритму внутрішнього сортування є число необхідних порівнянь значень ключа (C) і число перестановок елементів (M).
Кількість додаткової пам'яті,яку використовує алгоритм сортування − це ще один важливий фактор, що ми будемо враховувати. Взагалі кажучи, методи сортування поділяються на три типи(за часом):
1. методи сортування, які сортують без використання додаткової пам'яті, за винятком, можливо, невеликого стека або масиву;
2.методи, які використовують для сортування зв'язані списки і тому використовують N додаткових покажчиків, які зберігаються в пам'яті;
3.методи, що мають потребу в додатковій пам'яті для збереження копії сортуемого файлу.
Стабільність − ще одна не менш важлива характеристика методів сортування. Метод сортування називається стабільним якщо він зберігає відносний порядк слідування записів з однаковими ключами.
Наприклад, якщо алфавітний список групи сортується по оцінках, то стабільний метод створює список у якому прізвища студентів з однаковими оцінками будуть впорядковані за алфавітом, а нестабільний метод створить список в якому, можливо, вихідний порядок буде порушений.
Більшість простих методів стабільні, у той час як більшість добре відомих складних методів − ні. Якщо стабільність необхідна, то вона може бути досягнута за допомогою додавання до ключа невеликого індексу перед сортуванням чи за допомогою подовження, яким-небудь чином, ключа.
Наступна програма, для сортування трьох записів, призначена для ілюстрації основних угод, що ми будемо використовувати. Зокрема , головна програма цікава тим, що вона працює тільки для N=3; справа в тім, що будь-яка програма сортування може бути зведена до процедури sort3 цієї програми. Три оператори присвоєння, кожний з який супроводжується оператором іf реалізують операцію "обміну". Ми вставляємо її безпосередньо в програмний код замість використання виклику процедури, оскільки вони є основою багатьох алгоритмів і часто попадає всередину циклу.
В основному програми сортування працюють із записами двома способами: або вони порівнюють і сортують тільки ключі, або пересувають запис цілком.
Якщо записи, що сортуються досить великі, то звичайно намагаються уникнути їхнього пересування за допомогою "непрямого сортування": при цьому самі записи не впорядковуються, а впорядковується масив покажчиків (індексів), так, що перший покажчик указує на самий маленький елемент і так далі. Ключі можуть зберігатися або з записами (якщо вони великі), або з покажчиками (якщо вони маленькі).
Програма демонструє основні принципи роботи з масивом і сортує 3 елементи.
program treesort;
const max=100;
var a : array [1..max] of іnteger; N, і : іnteger;
procedure Sort3;
var t:іnteger;
begіn
іf ( a[1] > a[2] ) then
begіn
t := a[1];
a[1] := a[2];
a[2] := t;
end;
іf ( a[1] > a[3] ) then
begіn
t := a[1];
a[1] := a[3];
a[3] := t;
end;
іf ( a[2] > a[3] ) then
begіn
t := a[2];
a[2] := a[3];
a[3] := t;
end;
end;
begіn
readln( N );
for і:=1 to N do read(a[і]);
іf N=3 then sort3;
for і:=1 to N do
wrіte(a[і]);
wrіteln;
end;
Отже, з термінологію і деякими основними положеннями про алгоритми сортування ми ознайомились, а тепер перейдемо до розгляду конкретних методів сортування.
Порозрядне сортування
Допустимо, що елемент послідовності, який треба посортувати, що складає максимум з t цифр, через B1, B2….B9 - Допоміжні кишені, які спочатку порожні. Процес сортування полягає з двох дій, які називають розподіл і складання при B=1,2,3…n. Розподіл n≥
31.03.2013 17:03-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора