ЗМІСТ
ВСПУП 2
1. ТЕОРЕТИКО-МЕТОДОЛОГИЧЕСКИЕ АСПЕКТЫ ПРОБЛЕМЫ МЕТОДОВ СОРТИРОВКИ ДАННЫХ В ЯЗЫКЕ PASCAL
1.1 Поняття сортування
1.2 Критерії оцінки алгоритмів сортування
1.3 Класифікація алгоритмів сортування
1.4 Постановка задачі сортування і методи її рішення.
1.5 Сортування бульбашковим методом
1.6 Сортування вибором елемента
1.7 Сортування включенням
1.8 Сортування злиттям
1.9 Удосконалені алгоритми сортування. Сортування Шелла
1.10 Метод поділу (алгоритм "швидкого" сортування, метод Хоара)
1.11 Порівняльний аналіз методів сортування
ВИСНОВОК
СПИСОКВИКОРИСТАНИХ ДЖЕРЕЛВСТУП
В наш час нові інформаційні технології посідають дуже важливе місце не лише в спеціалізованих, але й в повсякденних сферах життя. Комп’ютери застосовуються в бізнесі, менеджменті, торгівлі, навчанні та багатьох інших сферах діяльності людини.
Комп’ютерні технології дуже зручні для виконання різноманітних операцій, але в різних сферах застосування ці операції різні. Тому, кожна окрема галузь, яка використовує специфічні технічні засоби, потребує своїх власних програм, які забезпечують роботу комп’ютерів.
Розробкою програмного забезпечення займається така галузь науки, як програмування. Вона набуває все більшого й більшого значення останнім часом, адже з кожним днем комп’ютер стає все більш необхідним, все більш повсякденним явищем нашого життя. Адже обчислювальна техніка минулих років вже майже повністю вичерпала себе і не задовольняє тим потребам, що постають перед людством.
Таким чином, нові інформаційні технології дуже актуальні в наш час і потребують багато уваги для подальшої розробки та вдосконалення. Поряд з цим, велике значення має також і програмування, яке є одним із фундаментальних розділів інформатики і тому не може залишатись осторонь.
Програмування містить цілу низку важливих внутрішніх задач. Однією з найбільш важливих таких задач для програмування є задача сортування. Під сортуванням звичайно розуміють перестановки елементів будь-якої послідовності у визначеному порядку. Ця задача є однією з найважливіших тому, що її метою є полегшення подальшої обробки певних даних і, насамперед, задачі пошуку. Так, одним з ефективних алгоритмів пошуку є бінарний пошук. Він працює швидше ніж, наприклад, лінійний пошук, але його можливо застосовувати лише за умови, що послідовність вже упорядкована, тобто відсортована.
Взагалі, відомо, що в будь-якій сфері діяльності, що використовує комп’ютер для запису, обробки та збереження інформації, усі дані зберігаються в базах даних, які також потребують сортування. Певна впорядкованість для них дуже важлива, адже користувачеві набагато легше працювати з даними, що мають певний порядок. Так, можна розташувати всі товари по назві або відомості про співробітників чи студентів за прізвищем або роком народження, тощо.
Задача сортування в програмуванні не вирішена повністю. Адже, хоча й існує велика кількість алгоритмів сортування, все ж таки метою програмування є не лише розробка алгоритмів сортування елементів, але й розробка саме ефективних алгоритмів сортування. Ми знаємо, що одну й ту саму задачу можна вирішити за допомогою різних алгоритмів і кожен раз зміна алгоритму приводить до нових, більш або менш ефективних розв’язків задачі. Основними вимогами до ефективності алгоритмів сортування є перш за все ефективність за часом та економне використання пам’яті.
У даній роботі мова буде йти про ефективність різних методів сортування даних у мові Pascal.
Об'єкт і предмет дослідження – методи сортування даних, використовувані в мові Pascal.
Метою даного дослідження є аналіз ефективності різних методів сортування даних у мові Pascal.
Взагалі , методи сортування поділяються на три типи:
1. методи сортування, що сортують без використання додаткової пам'яті, за винятком, можливо, невеликого стека і/або масиву;
2. методи, що використовують для сортування зв'язані списки і тому використовують N додаткових покажчиків збережених у пам'яті;
3. і методи, що мають потребу в додатковій пам'яті для збереження копії сортуемого файлу.
Мною були розглянуті переваги і недоліки таких методів сортування, як метод обміну, включення, вибору, злиття, методи Шелла і Хоара.
Основними критеріями ефективності алгоритмів сортування мною був обраний час його роботи й ощадливе використання пам'яті.
І перші три алгоритми, що ми розглянемо, для сортування N елементів мають час роботи пропорційний N2
, у той час як більш складні алгоритми використовують час пропорційне N log N.
Крім часу й обсягу пам'яті, критерії ефективності розглянутих у роботі алгоритмів можуть включати наступні параметри:
1. кількість кроків алгоритму, необхідних для упорядкування;
2. кількість порівнянь елементів;
3. кількість перестановок, виконуваних при сортуванні.
Зрозуміло, що, чим вище показник, тим «гірше» алгоритм сортування.
РОЗДІЛ 1.
ТЕОРЕТИКО-МЕТОДОЛОГІЧНІ АСПЕКТИ ПРОБЛЕМИ методів сортування даних у мові Pascal
1.1 Поняття
сортування
Алгоритм сортування — це алгоритм для упорядкування елементів у списку. У випадку, коли елемент списку має кілька полів, поле, що служить критерієм порядку, називається ключем сортування. На практиці як ключ часто виступає число, а в інших полях зберігаються які-небудь дані, що ніяк не впливають на роботу алгоритму.
Алгоритми сортування інформації створюють основу для величезної більшості прикладних програм. Сортування інформації - це одна зі стандартних функцій, що виникають у процесі рішення задач.
Сортування - це процес упорядкування деякої безлічі елементів, на якому визначені відносини порядку >, <, ³ , £ . Коли говорять про сортування, мають на увазі упорядкування безлічі елементів по зростанню або убуванню. Розглянемо різні алгоритми сортування і з'ясуємо, чому виникла необхідність появи такого великого числа алгоритмів рішення однієї і тієї ж задачі.
Для перемінних символьного типу поняття "зростання" і "убування" відносяться до значень машинного коду, що використовується для представлення символів у пам'яті комп'ютера. Так як всі буквені символи розташовуються в таблиці кодів за алфавітом, то сортування слів тексту завжди приводить до їх упорядкування в алфавітній послідовності.
Сортування даних використовується для ефективного рішення інших задач при програмуванні. Для упорядкованої сукупності даних швидко і легко вирішується задача, як пошук і добір інформації з заданої умови.
Існує багато алгоритмів, що забезпечують рішення задачі сортування. Одні з них мають низьку швидкодію, інші мають дуже високу ефективність і практично використовуються в сучасних комп'ютерних системах.
1.2
Критерії оцінки алгоритмів сортування
Для кожного методу сортування мається багато алгоритмів. Кожен алгоритм має свої переваги, але в цілому оцінка алгоритму сортування залежить від відповідей, що будуть отримані на наступні питання:
1) з якою середньою швидкістю цей алгоритм сортує інформацію?;
2) яка швидкість для кращого випадку і для гіршого випадку?;
3) поводження алгоритму є природним або є не природним?;
4) чи виконується перестановка елементів для однакових ключів?
Якщо у відсортованому масиві елементи з однаковими ключами йдуть у тім же порядку, у якому вони розташовувалися у вихідному масиві, то алгоритм сортування називається стійким.
Давайте докладніше розглянемо ці критерії. Очевидно, що швидкість роботи будь-якого алгоритму сортування має велике значення. Швидкість сортування (синоніми: швидкодія, ефективність) масиву безпосередньо зв'язана з кількістю порівнянь і кількістю обмінів, що відбуваються під час сортування, причому обміни займають більше часу. Порівняння відбувається тоді, коли один елемент масиву порівнюється з іншим; обмін відбувається тоді, коли два елементи міняються місцями. Час роботи одних алгоритмів сортування росте экспоненциально, а час роботи інших логарифмічно залежно від кількості елементів.
Час роботи в кращому і гіршому випадках має значення, якщо одна з цих ситуацій буде зустрічатися досить часто. Алгоритм сортування найчастіше має гарний середній час виконання, але в гіршому випадку він працює дуже повільно.
Поводження алгоритму сортування називається природним, якщо час сортування мінімально для вже упорядкованого списку елементів, збільшується в міру зростання ступеня невпорядкованості списку і максимально, коли елементи списку розташовані в зворотньому порядку. Обсяг роботи алгоритму оцінюється кількістю вироблених порівнянь і обмінів.
Щоб зрозуміти, чому переупорядковування елементів з однаковими ключами має визначене значення, уявіть собі базу даних поштового розсилання, упорядковану по головному ключі і підключу. Головним ключем є поштовий індекс, а в межах одного поштового індексу записи упорядковані на прізвище. При додаванні в список нової адреси і пересортовуванню списку порядок подключей (тобто прізвищ усередині поштових індексів) не повинний мінятися. Для гарантії, що це не відбудеться, алгоритм сортування не повинний обмінювати ключі з однаковим значенням , тобто повинний бути стійким.
Далі будуть представлені характерні для кожної групи алгоритми сортування з аналізом ефективності. Після них будуть продемонстровані більш досконаліші методи сортування.
Оцінки часу виконання. Символ O().
Для оцінки продуктивності алгоритмів можна використовувати різні підходи. Самий нехитрий - просто запустити кожен алгоритм на декількох завданнях і порівняти час виконання. Інший спосіб - математично оцінити час виконання підрахунком операцій.
Розглянемо алгоритм обчислення значення багаточлена ступеня n у заданій крапці x. Pn(x) = anxn + an-1xn-1 + ... + aixi + ... + a1x1 + a0
Алгоритм 1 - для кожного доданка, крім a0 звести x у заданий ступінь послідовним множенням і потім домножить на коефіцієнт. Потім доданки скласти.
Обчислення i-го доданка(i=1..n) вимагає і множень. Отже, усього 1 + 2 + 3 + ... + n = n(n+1)/2 множень. Крім того, потрібно n+1 додаваннь. Усього n(n+1)/2 + n + 1= n2/2 + 3n/2 + 1 операцій.
Алгоритм 2 - винесемо x-и за дужки і перепишемо багаточлен у вигляді Pn(x) = a0 + x(a1 + x(a2 + ... ( ai + .. x(an-1 + anx))).
Наприклад, P3(x) = a3x3 + a2x2 + a1x1 + a0 = a0 + x(a1 + x(a2 + a3x))
Будемо обчислювати вираз зсередини. Сама внутрішня дужка вимагає 1 множення і 1 додавання. Її значення використовується для наступної дужки... І так, 1 множення і 1 додавання на кожну дужку, яких.. n-1 штука. І ще після обчислення самої зовнішньої дужки помножити на x і додати a0. Усього n множень + n додавань = 2n операцій.
Найчастіше така докладна оцінка не потрібно. Замість неї приводять лише асимптотичну швидкість зростання кількості операцій при збільшенні n.
Функція f(n) = n2
/2 + 3n/2 + 1 зростає приблизно як n2
/2 (відкидаємо порівняно повільно зростаючий доданок 3n/2+1). Константний множник 1/2 також забираємо й одержуємо асимптотическую оцінку для алгоритму 1, що позначається спеціальним символом O(n2
) [читається як "Об велике від эн квадрат"].
Це - верхня оцінка, тобто кількість операцій(а виходить, і час роботи) росте не швидше, ніж квадрат кількості елементів. Щоб відчути, що це таке, подивитеся на таблицю, де приведені числа, що ілюструють швидкість росту для декількох різних функцій.
| n | log n | n*log n | n2 |
| 1 | 0 | 0 | 1 |
| 16 | 4 | 64 | 256 |
| 256 | 8 | 2,048 | 65,536 |
| 4,096 | 12 | 49,152 | 16,777,216 |
| 65,536 | 16 | 1,048,565 | 4,294,967,296 |
| 1,048,576 | 20 | 20,969,520 | 1,099,301,922,576 |
| 16,775,616 | 24 | 402,614,784 | 281,421,292,179,456 |
Якщо вважати, що числа в таблиці відповідають мікросекундам, то для задачі з n=1048576 елементами алгоритмові з часом роботи O(log n) буде потрібно 20 мікросекунд, алгоритмові згодом O(n) - 17 хвилин, а алгоритмові з часом роботи O( n2 ) - більш 12 днів... Тепер перевага алгоритму 2 з оцінкою O(n) перед алгоритмом 1 досить переконлива.
Найкращою є оцінка O(1)... У цьому випадку час узагалі не залежить від n, тобто постійно при будь-якій кількості елементів.
Таким чином, O() - "урізана" оцінка часу роботи алгоритму, що найчастіше набагато простіше одержати, чим точну формулу для кількості операцій.
Отже, сформулюємо два правила формування оцінки O().
При оцінці за функцію береться кількість операцій, що зростає швидше всього, тобто, якщо в програмі одна функція, наприклад, множення, виконується O(n) раз, а додавання - O(n2
) раз, те загальна складність програми - O(n2
), тому що зрештою при збільшенні n більш швидкі ( у визначене, константне число раз ) додавання стануть виконаються настільки часто, що будуть впливати на швидкодію куди більше, ніж повільні, але рідкі множення. Символ O() показує винятково асимптотику!
При оцінці O() константи не враховуються. Нехай один алгоритм робить 2500n + 1000 операцій, а іншої - 2n+1. Обоє вони мають оцінку O(n), тому що їхній час виконання росте лінійно.
Зокрема, якщо обидва алгоритми, наприклад, O( n*log n ), те це аж ніяк не виходить, що вони однаково ефективні. Перший може бути, скажемо, у 1000 разів ефективніше. O() значить лише те, що їхній час зростає приблизно як функція n*log n.
Інший наслідок опускання константи - алгоритм згодом O(n2
) може працювати значно швидше алгоритму O(n) при малих n... За рахунок того, що реальна кількість операцій першого алгоритму може бути n2
+ 10n + 6, а другого - 1000000n + 5. Утім, другий алгоритм рано або пізно обжене перший... n2
росте куди швидше 1000000n.
Основа логарифма усередині символу O() не пишеться. Причина цього досить проста. Нехай у нас є O( log2
n). Але log2
n=log3
n/log3
2, а log3
2, як і будь-яку константу, асимптотика - символ О() не враховує. Таким чином, O( log2
n) = O( log3
n).
До будь-якої підстави ми можемо перейти аналогічно, а відповідно і писати його не має сенсу.
Математичне тлумачення символу O().
Визначення: O(g) - безліч функцій f, для яких існують такі константи C і N, що |f(x)| <= C|g(x)| для всіх x>N. Запис f = O(g) дослівно позначає, що f належить безлічі O(g). При цьому зворотне вираження O(g) = f не має змісту.
Зокрема, можна сказати, що f(n) = 50n належить O(n2
). Тут ми маємо справу з неточною оцінкою. Зрозуміло, f(n) <= 50n2
при n>1, однак більш сильним твердженням було б f(n) = O(n), тому що для C=50 і N=1 вірно f(n) <= Cn, n>N.
Інші види оцінок.
Поряд з оцінкою O(n) використовується оцінка Ώ(n) [читається як "Омега більше від эн"]. Вона позначає нижню оцінку росту функції. Наприклад, нехай кількість операцій алгоритму описує функція f(n) = Ώ(n2
). Це значить, що навіть у самому вдалому випадку буде зроблено не менш порядку n2
дій. ...У той час як оцінка f(n) = O(n3
) гарантує, що в самому гіршому випадку дій буде порядку n3
, не більше.
Також використовується оцінка Θ(n) ["Тэта від эн"], що є гібридом O() і Ώ(). Та (n2
) є і верхньою і нижньої асимптотической оцінкою одночасно - завжди буде виконуватися порядку n2
операцій. Оцінка Θ() існує тільки тоді, коли O() і Ώ() збігаються і дорівнює їм.
Як правило, основна увага все-таки звертається на верхню оцінку O(), тому, незважаючи на "поліпшення", алгоритм 2 залишається переважніше.
Отже, O() - асимптотическая оцінка алгоритму на гірших вхідних даних, Ώ() - на кращих вхідних даних, Θ() - скорочений запис однакових O() і Ώ().
1.3 Класифікація алгоритмів сортування
Стабільність (stability) — стійке сортування не міняє взаємного розташування рівних елементів.
Природність поводження — ефективність методу при обробці вже упорядкованих, або частково упорядкованих даних. Алгоритм поводиться природно, якщо враховує цю характеристику вхідної послідовності і працює краще.
Для значної кількості алгоритмів середній і найгірший час впорядкування n-елементного масиву є , це пов'язано з тим, що в них передбачені перестановки елементів, що стоять поряд (різниця між індексами елементів не перевищує деякого заданого числа). Такі алгоритми зазвичай є стабільними, хоча і не ефективними для великих масивів.
Інший клас алгоритмів здійснює впорядкування за час . В цих алгоритмах використовується можливість обміну елементів, що знаходяться на будь-якій відстані один від одного.
Ці швидкі алгоритми використовуються в реальних задачах. Проте більшість з них нестабільні. Стабільні алгоритми, що працюють за час , потребують додаткової пам'яті.
Відомий стабільний алгоритм сортування, що не вимагає додаткової пам’яті, працює за час
Ще один клас алгоритмів використовує в своїй роботі деяку додаткову інформацію про елементи, що впорядковуються (наприклад, те що вони є різними числами в деякому діапазоні). Завдяки цьому, вони працюють за час .
Ще одною важливою властивістю алгоритму є його сфера застосування. Тут основних типів упорядкування два:
Внутрішнє сортування оперує з масивами, що цілком поміщаються в оперативній пам'яті з довільним доступом до будь-якого осередку. Дані зазвичай упорядковуються на тому ж місці, без додаткових витрат.У сучасних архитектурах персональних комп'ютерів широко застосовується подкачка і кэширование пам'яті. Алгоритм сортування повинен добре поєднуватися із вживаними алгоритмами кешування і підкачування.
Зовнішнє сортування оперує з пристроями великого об'єму, що запам'ятовують, але з доступом не довільним, а послідовним (впорядкування файлів), тобто в даний момент ми 'бачимо' тільки один елемент, а витрати на перемотування в порівнянні з пам'яттю невиправдано великі. Це накладає деякі додаткові обмеження на алгоритм і приводить до спеціальних методів упорядкування, що звичайно використовує додатковий дисковий простір. Крім того, доступ до даних на носієві проводиться набагато повільніше, ніж операції з оперативною пам'яттю. Доступ до носія здійснюється послідовним образом: у кожен момент часу можна вважати або записати тільки елемент, що випливає за поточним. Обсяг даних не дозволяє їм розміститися в ОЗУ.
Також алгоритми класифікуються по:
1. потреби в додатковій пам'яті або її відсутності
2. потреби в знаннях про структуру даних, що виходять за рамки операції порівняння, або відсутності таких
Відомі алгоритми сортування:
За час
сортування вибором
сортування включенням
сортування обміном
За час
пірамідальне сортування
швидке сортування
сортування злиттям
За час з використанням додаткової інформації про елементи
сортування підрахунком
сортування за розрядами
сортування комірками
За час
сортування злиттям модифіковане
сортування Шелла
1.4 Постановка задачі сортування і методи її рішення.
Задачу сортування даних можна сформулювати для інформаційної сукупності всілякої природи - для числової інформації, для слів і символів тексту. Для цього, потрібно визначити поняття порядку для елементів масиву, визначити поняття "більше" і "менше" для кожної пари елементів. Відсортувати послідовність чисел можна точно таким же способом, як і послідовність рядків тексту. Необхідно тільки визначити який з елементів пари "більше" іншого.
Більш важливим для вибору алгоритму є місце розташування даних - в оперативній пам'яті комп'ютера або на зовнішньому пристрої.
Тут відіграє роль розходження в основних критеріях якості - для даних в оперативній пам'яті основними позитивними властивостями методу є швидкодія і потреби в додатковій пам'яті. Для дискових файлів дуже важливим показником є кількість звертань до пристрою для виконання операцій уведення-висновку - воно повиннео бути мінімальним.
Традиційно розрізняють внутрішнє сортування, у якій передбачається, що дані знаходяться в оперативній пам'яті, і важливо оптимизировать число дій програми (для методів, заснованих на порівнянні, число порівнянь, обмінів елементів і ін.), і зовнішню, у якій дані зберігаються на зовнішньому пристрої з повільним доступом (магнітні стрічка, барабан, диск, флешка) і насамперед треба знизити число звертань до цьому пристрою.
У цій роботі розглянемо алгоритми внутрішнього сортування масивів елементів, тому що вони більш важливі більшості програмістів у повсякденній практиці.
Варто помітити, що алгоритм сортування злиттям зручно застосовувати і при сортуванні зовнішніх даних. При цьому мова буде йти про злиття файлів.
Сформулюємо постановку задачі сортування даних для внутрішнього сортування одномірного числового масиву по зростанню.
Мається одномірний масив чисел, що складає з n елементів: X[n]. Переставити елементи масиву так, щоб їхні значення розташовувалися в порядку зростання. Іншими словами, для будь-якої пари елементів X[і] і X[і+1] виконується нерівність виду:
X[і] <= X[і+1].
У цій задачі однозначно визначається структура даних для внутрішнього сортування (одномірний масив) і порядок упорядкування елементів. Ключем для визначення порядку елементів є саме числове значення елемента масиву. Результатом рішення задачі повинна бути програма сортування масиву одним або декількома методами.
При розробці програми можна скористатися різними алгоритмами. Найбільш відомими є наступні:
- метод сортування обмінами ("бульбашкове" сортування);
- метод сортування включенням;
- метод сортування вибором елемента;
- метод поділу (алгоритм "швидкої" сортування метод Хоара);
- метод Шелла;
- метод злиття.
1.5 Сортування бульбашковим методом
Найбільш відомим (і найбільше "безславним") є сортування бульбашковим методом. Його популярність пояснюється назвою, що запам'ятовується, і простотою алгоритму. Однак, це сортування є одним із самих гірших серед усіх коли-небудь, придуманих сортувань.
Сортування бульбашковим методом використовує метод обмінного сортування. Вон заснован на виконанні в циклі операцій порівняння і при необхідності обміну сусідніх елементів. Його назва відбувається через подобу процесові руху бульбашок у резервуарі з водою, коли кожна бульбашка знаходить свій власний рівень. Нижче показана найпростіша форма програми сортування бульбашковим методом:
{ сортування бульбашковим методом}
procedure Bubble(var item: DataArray; count:integer);
var
i,j : integer;
x : DataItem;
begin
for i := 2 to count do
begin
for j := count downto i do
if item[j-1]>item[j] then
begin
x := item[j-1];
item[j-1] := item[j];
item[j] := x;
end;
end;
end; {кінець сортування бульбашковим методом}
У цьому випадку дане "item" є масивом елементів "DataItem", що сортується, а дане "count" містить число елементів у масиві.
Сортування бульбашковим методом мають два цикли. Оскільки число елементів масиву задається перемінної "count", зовнішній цикл викликає перегляд масиву count - 1 раз. Це забезпечує перебування кожного елемента у своєї позицій після завершення процедури. Внутрішній цикл призначений для фактичного виконання операцій порівняння й обміну.
Для ілюстрації роботи сортування бульбашковим методом нижче подані результати кожного етапу сортування масиву "dcab":
вихідне положення: d c a b;
перший прохід: a d c b;
другий прохід: a b d c;
третій прохід: a b c d.
При аналізі всякого сортування визначається число операцій порівняння й обміну, виконаних у кращому, середньому і гіршому випадках. Для сортування бульбашковим методом число порівнянь залишається незмінним, оскільки два цикли завжди виконуються задане число раз поза залежністю від упорядкованості вихідного масиву. Це означає, що при сортуванні бульбашковим методом завжди виконується 1/2 (n2
-n) операцій порівняння, де "n" задає число сортируемых елементів масиву. Ця формула виводиться на тій підставі, що зовнішній цикл сортування бульбашковим методом виконується n-1 раз, а внутрішній цикл виконується n/2 разів. Їхнє перемножування дасть зазначену формулу. Число операцій обміну буде нульовим для найкращого випадку, коли вихідний масив уже є відсортованим. Число операцій обміну для середнього випадку буде дорівнює 3/4 (n2
-n), а для найгіршого випадку буде дорівнює 3/2 (n2
-n) раз. Можна помітити, що в міру погіршення упорядкованості вихідного масиву число неупорядкованих елементів наближається до числа порівнянь (кожен неупорядкований елемент вимагає три операції обміну). Сортування бульбашковим методом називають квадратичним алгоритмом, оскільки час його виконання пропорційно квадратові числа сортуємих елементів. Сортування великого числа елементів бульбашковим методом вимогає дуже багато часу, тому що час виконання сортування знаходиться в квадратичній залежності від числа елементів масиву. Наприклад, якщо не враховувати час операцій обміну, виконуваних для перестановки неупорядкованих елементів, то тоді при виконанні однієї операції порівняння протягом 0,001 секунд сортування десяти елементів займе 0,05 секунд, сортування ста елементів займе 5 секунд, а сортування 1000 елементів займе 500 секунд. Сортування 100 000 елементів (такий розмір має невеликий телефонний довідник) вимогала б 5 000 000 секунд або близько 1400 годин (тобто два місяці безперервної роботи)! Сортування бульбашковим методом можна до деякої міри поліпшити і тим самим небагато поліпшити її тимчасові характеристики. Можна, наприклад, помітити, що сортування бульбашковим методом володіє одною особливістю: розташований не на своєму місці (наприкінці) масиву елемент (наприклад, елемент "а" у масиві "dcab") досягає свого місця за один прохід, а елемент, розташований на початку масиву (наприклад, елемент "d"), дуже повільно досягає свого місця. Необов'язково всі перегляди робити в одному напрямку. Замість цього всякий наступний перегляд можна робити в протилежному напрямку. В цьому випадку сильно віддалені від свого місця елементи швидко переміщатимуться у відповідне місце. Нижче показана поліпшена версія сортування бульбашковим методом, що одержав назву "човникового сортування" через відповідний характер рухів по масиву.
Хоча це сортування є поліпшенням бульбашковим методом, його не можна рекомендувати для використання, оскільки час виконання як і раніше залежить квадратично від числа елементі
{човникове сортування є поліпшеною версією сортування бульбашковим методом}
procedure Shaker(var item: DataArray; count:integer);
var
j, k, l, r: integer;
x: DataItem;
begin
l := 2; r := count; k := count;
repeat
for j := r downto l do
if item[j-1] then
begin { обмін }
x := item[j-1];
item[j-1] := item[j];
item[j] := x;
k := j;
end;
l := k+1;
for j := l to r do
if item[j-1]>item[j] then
begin { обмін }
x := item[j-1];
item[j-1] := item[j];
item[j] := x;
k := j;
end;
r := k-1;
until l>r
end; {кінець човникового сортування}
1.6
Сортування вибором елемента
При сортуванні вибором вибирається елемент із найменшим значенням і робиться його обмін з першим елементом масиву. Потім знаходиться елемент із найменшим значенням із що залишилися n-1 елементів і робиться його обмін із другим елементом і т.д. до обміну двох останніх елементів. Наприклад, якщо сортування вибором застосувати для масиву "bdac", те будуть отримані наступні проходи:
вихідне положення: b d a c;
перший прохід: a d b c;
другий прохід: a b b c;
третій прохід: a b c d.
На жаль як і в сортуванні бульбашковим методом зовнішній цикл виконується n-1 раз, а внутрішній цикл виконується n/2 разів. Це значить, що число порівнянь для сортування вибором дорівнює 1/2 (n2
-n) і це сортування буде виконуватися занадто повільно для великого числа елементів. Число операцій обміну в найкращому випадку дорівнює 3(n-1), а в гіршому випадку дорівнює n2
/4+3(n-1). У кращому випадку (коли вихідний масив вже упорядкований) буде потрібно поміняти місцями тільки n-1 елементів, а кожна операція обміну вимагає три операції пересилання.
{сортування вибором}
procedure Selekt(var item: DataArray; count:integer);
var
i, j, k: integer;
x: DataItem;
begin
for i := i to count-1 do
begin
k := i;
x := item[i];
for j := і+1 to count do {знайти елемент із найменшим значенням}
if item[j]<x then
begin
k := j;
x := item[j];
end;
item[k] := item[і]; {обмін}
item[і] := x;
end;
end; {кінець сортування вибором}
У середньому число операцій обміну дорівнює n(ln+y), де "y" є константою Эйлера, приблизно рівної 0,577216. Це значить, що незважаючи на однакове число операцій порівнянь для сортувань бульбашковим методом і сортувань вибором, число операцій обміну для середнього випадку буде значно меншим для сортування вибором.
1.7 Сортування включенням
Сортування включенням є останньою з класу простих алгоритмів сортування. При сортуванні включенням спочатку упорядковуються два елементи масиву. Потім робиться включення третього елемента у відповідне місце стосовно перших двох елементів.
Цей процес повторюється доти, поки всі елементи не будуть упорядковані. Наприклад, для масиву "dcab" сортування включенням буде проходити в такий спосіб:
вихідне положення: d c a b;
перший прохід: c d a b;
другий прохід: a c d b;
третій прохід: a b c d.
Нижче приводиться алгоритм сортування включенням:
{ сортування включенням }
procedure Inser(var item: DataArray; count:integer);
var
i, l: integer;
x: DataItem;
begin
for i := 2 to count do
begin
x := item[i];
j := i-1;
while (x<item[j]) and (j>0) do
begin
item[j+1] := item[j];
j := j-1;
end;
item[j+1] := x;
end;
end; { кінець сортування включенням }
На відміну від сортування бульбашковим методом і сортування вибором число операцій порівняння для сортування включенням залежить від вихідної упорядкованості масиву елементів. Якщо вихідний масив вже упорядкований, то число операцій порівняння дорівнює n-1.
Якщо масив упорядкований у зворотному порядку, то число операцій порівняння дорівнює 1/2 (n2
+n)-1, даючи в середньому значення 1/4 (n2
+n-2).
Число операцій обміну буде наступним:
для кращого випадку: 2 (n-1);
у середньому: 1/4 (n2
+9n-10);
для гіршого випадку: 1/2 (n2
+3n-4).
Таким чином, число операцій обміну для гіршого випадку буде настільки ж великим, як і для сортувань бульбашковим методом і сортувань вибором. Число операцій обміну для середнього випадку буде лише на небагато менше. Однак сортування включенням має дві переваги. По-перше, вона має природне поводження, тобто вона виконується швидше для упорядкованого масиву і довше всего виконується, коли масив упорядкований у зворотному напрямку. Це робить сортування включенням корисної для упорядкування майже відсортованих масивів. По-друге, елементи з однаковими ключами не переставляються: якщо список елементів сортується з використанням двох ключів, те після завершення сортування включенням він як і раніше буде упорядкований по двох ключах.
Незважаючи на те, що число порівнянь може бути досить невеликим для визначених наборів даних, постійні зрушення масиву вимагають виконання великого числа операцій пересилань.
Однак, сортування включенням має природне поводження, вимагаючи найменше число операцій обміну для майже упорядкованого списку і найбільше число операцій обміну, коли масив упорядкований у зворотному напрямку.
1.8 Сортування злиттям
В основі цього способу сортування лежить злиття двох упорядкованих ділянок масиву в одну впорядковану ділянку іншого масиву.
Злиття двох упорядкованих послідовностей можна порівняти з перебудовою двох колон солдатів, вишикуваних за зростом, в одну, де вони також розташовуються за зростом. Якщо цим процесом керує офіцер, то він порівнює зріст солдатів, перших у своїх колонах і вказує, якому з них треба ставати останнім у нову колону, а кому залишатися першим у своїй. Так він вчиняє, поки одна з колон не вичерпається – тоді решта іншої колони додається до нової.
Нехай у масиві 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=nmod4 – довжина залишку масиву після останньої повної четвірки елементів. При 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
lp := 1;
while lp < n do
begin
B := A; { копіювання }
npp := n div (2*lp); { кількість пар ділянок }
tl := n mod (2*lp); { довжина залишку }
for cpp := 1 to npp do { cpp – номер пари }
begin
bpp := (cpp - 1)*2*lp + 1;
{ індекс першого елемента лівої ділянки пари}
mrg ( B, bpp, lp, lp, A );
end;
{ обробка залишку }
if tl > lp then
mrg ( B, n - tl + 1, lp, tl - lp, A );
{ за tl <= lp залишок був упорядкований }
{ на попередньому кроці }
lp := lp*2
end
{ lp >= n : масив упорядковано на останньому кроці }
end
Очевидно, що після k-го кроку впорядковані ділянки мають довжину lp=2k. Якщо 2k=n, то масив упорядковано. Якщо 2k>n, але 2k-1<n, то при виконанні останнього кроку мають місце співвідношення
lp = 2k-1 = 2k / 2 > n/2, npp = 0, tl = n > lp,
і злиття ділянки довжиною lp та залишку довжиною n-lp дає впорядкований масив.
Оцінимо складність наведеного алгоритму. При кожному виконанні тіла циклу while значення всіх елементів масиву копіюються в допоміжний масив і назад по одному разу, тобто виконується O(n) елементарних дій. Після останнього k-го кроку 2k<2n, тобто k<1+logn, і це означає, що тіло циклу while виконується 1+ log2n =O(logn) разів. Отже, складність алгоритму оцінюється як O(nlogn).
Запишемо в таблицю значення виразів n, n(n-1)/2, n(1+log2
n ) та округлене відношення r двох останніх:
| n | n(n-1)/2 | n(1+ log2
n ) |
r |
| 10 | 45 | 40 | 1 |
| 100 | 4950 | 700 | 7 |
| 1000 | 499500 | 10000 | 50 |
| 10000 | 49995000 | 140000 | 350 |
Як бачимо, кожне зростання n у 10 разів веде до зростання n(n-1)/2 та n(1+log2
n) приблизно в 100 й 14 разів відповідно, і за n=10000 сортування злиттям виконується в сотні разів скоріше, ніж бульбашкове!
Зауважимо, що в наведеному алгоритмі сортування злиттям копіювання масиву в допоміжний указано лише для того, щоб ідею алгоритму було простіше сприйняти. Цей алгоритм нескладно переробити так, щоб замість копіювання в додатковий масив відбувалося злиття в нього упорядкованих ділянок. Отже, на кроках з номерами 1, 3, 5, … має відбуватися злиття в допоміжний масив, а на кроках 2, 4, 6, … – злиття в протилежному напрямку. Переробка алгоритму залишається вправою.
Сортування злиттям можна задати рекурсивно: масив поділяється на дві приблизно рівні частини, які після сортування (тим самим способом – ось рекурсія!) зливаються. Коли ж довжина частини масиву зменшується до 1, відбувається просто повернення з рекурсії. Цей алгоритм уточнюється наступною процедурою Mrgrec. На відміну від процедури Merges, вона має два параметри-масиви (той, що сортується, та допоміжний), а також два числові параметри (початок і кінець частини масиву, яка сортується). Крім того, спочатку відбувається злиття ділянок основного масиву в допоміжний, а потім копіювання в основний:
procedure Mrgrec(var A, B : ArT; l, r : integer);
var m, k : integer;
begin
if l>=r then exit;
m:=(l+r) div 2;
Mrgrec(A, B, l, m); Mrgrec(A, B, m+1,r);
mrg(A, l, m-l+1, r-m, B);
for k:=l to r do A[k]:=B[k];
end;
Ця процедура набагато коротше нерекурсивної процедури Merges, але виконання її довше. Власне сортування починається лише після повернення з викликів, у яких l=r, а це практично "середина дистанції".
Завершуючи описання сортування злиттям, скажемо, що цей алгоритм є першим із ефективних алгоритмів сортування. У 1945 році його винайшов Джон фон Нейман, один із піонерів програмування.
Серйозним недоліком цього алгоритму є необхідність додаткового масиву такої ж довжини, як і в основного. За великих довжин можлива ситуація, коли на один масив пам'яті вистачає, а на два – ні.
1.9 Удосконалені алгоритми сортування. Сортування Шелла
Усі розглянуті дотепер алгоритми сортування мають дуже серйозний недолік, а саме, час їхнього виконання пропорційно квадратові числа елементів.
Для великих обсягів даних ці сортування будуть повільними, а починаючи з деякої величини, вони будуть занадто повільними, щоб їх можна було використовувати на практиці. Кожен програміст чув або розповідав "страшні" історії про "сортування, що виконувалася три дні". На жаль, ці історії часто не були вигадкою.
Якщо сортування виконується занадто довго, то причиною цього може бути використовуваний алгоритм. Розглянемо два дуже гарні сортування. Перше зветься сортування Шелла, а друге називається швидким сортуванням, алгоритм якого визнаний найкращим. Ці сортування виконуються дуже швидко.
Сортування Шелла одержав свою назву по імені його творця Д.Л.Шелла. Однак, цю назву можна вважати вдалою, тому що виконувані при сортуванні дії нагадують укладення морських черепашок одну на одну.
Загальний метод, що використовує сортування включенням, застосовує принцип зменшення відстані між порівнюваними елементами. Нижче показана схема виконання сортування Шелла для масиву "f d a c b e". Спочатку сортуються всі елементи, що зміщені друг від друга на три позиції. Потім сортуються всі елементи, що зміщені на двох позицій. І, нарешті, упорядковуються всі сусідні елементи:
прохід 1 f d a c b e
прохід 2 c b a f d e
прохід 3 a b c e d f
отриманий результат a b c d e f
Алгоритм:
{ сортування Шелла }
procedure Shell(var item: DataArray; count:integer);
const
t = 5;
var
i, j, k, s, m: integer;
h: array[1..t] of integer;
x: DataItem;
begin
h[1]:=9; h[2]:=5; h[3]:=3; h[4]:=2; h[5]:=1;
for m := 1 to t do
begin
k:=h[m];
s:=-k;
for i := k+1 to count do
begin
x := item[i];
j := i-k;
if s=0 then
begin
s := -k;
s := s+1;
item[s] := x;
end;
while (x<item[j]) and (j<count) do
begin
item[j+k] := item[j];
j := j-k;
end;
item[j+k] := x;
end;
end;
end; { кінець сортування Шелла }
При поверхневому погляді на алгоритм не можна сказати, що він дає гарний результат і навіть те, що в результаті вийде відсортований масив. Однак, він дає і те й інше. Ефективність цього алгоритму пояснюється тим, що при кожному проході використовується відносно невелике число елементів або елементи масиву вже знаходяться у відносному порядку, а упорядкованість збільшується при кожному новому перегляді даних.
Відстані між порівнюваними елементами можуть змінюватися по-різному. Обов'язковим є лише те, що останній крок повинний дорівнювати одиниці. Наприклад, гарні результати дає послідовність кроків 9, 5, 3, 2, 1, що використана в показаному вище прикладі. Варто уникати послідовностей ступеня двійки, що, як показують складні математичні викладення, знижують ефективність алгоритму сортування. (Однак, при використанні таких послідовностей кроків між порівнюваними елементами це сортування буде як і раніше працювати правильно).
Внутрішній цикл має дві умови перевірки. Умова "х<item[j]" необхідна для упорядкування елементів. Умови "j>0" і "j<=count" необхідні для того, щоб запобігти вихід за межі масиву "item". Ця додаткова перевірка до деякої міри погіршує сортування Шелла. Злегка змінені версії сортування Шелла використовують спеціальні керуючі елементи, що не є в дійсності частиною тієї інформації, що повинна сортуватися. Елементи, що управляють, мають граничні для масиву даних значення, тобто найменше і найбільше значення. У цьому випадку не обов'язково виконувати перевірку на граничні значення. Однак, застосування таких керуючих елементів вимагає спеціальних знань про ту інформацію, що сортується, і це знижує універсальність процедури сортування.
Аналіз сортування Шелла вимагає рішення деяких складних математичних задач. Час виконання сортування Шелла пропорційно n. Ця залежність значно краще квадратичної залежності, який підкоряються розглянуті раніше алгоритми сортування. Однак, перш ніж ви вирішите використовувати сортування Шелла, варто мати на увазі, що швидке сортування дає навіть ще кращі результати.
1.10 Метод поділу (алгоритм "швидкого" сортування, метод Хоара)
Метод швидкого сортування був розроблений Ч. Ф. Р. Хоаром і він же дав йому цю назву. В даний час цей метод сортування вважається найкращим. Він заснований на використанні обмінного методу сортування. Це тим більше дивно, якщо врахувати дуже низьку швидкодію сортування бульбашковим методом, що являє собою найпростішу версію обмінного сортування.
В основі швидкого сортування лежить принцип розбивки. Спочатку вибирається деяке значення в якості "основи" і потім весь масив розбивається на дві частини. Одну частину складають всі елементи, рівні або більше "основи", а іншу частину складають всі елементи меншого значення, по якому робиться розбивка. Цей процес продовжується для частин, що залишилися, доти, поки весь масив не буде відсортований. Наприклад, для масиву "fedacb" при використанні як значення розбивки "d" будуть отримані наступні проходи при виконанні швидкого сортування:
вихідний стан: f e d a c b;
перший прохід: d c a d e f;
другий прохід: a b c d e f.
Цей процес продовжується для кожної частини "abc" і "def". Фактично цей процес має рекурсивну природу. І дійсно, найбільше "акуратно" швидке сортування реалізується за допомогою рекурсивного алгоритму. Вибір значення розбивки можна зробити двома способами. Це значення можна вибирати випадковим образом або шляхом усереднення невеликого числа значень, обраних з масиву. Для оптимального сортування потрібно вибрати значення, що буде знаходитися в точності посередині всіх елементів.
Однак, для більшості наборів даних це зробити нелегко. Однак, навіть у гіршому випадку, коли вибирається одне з екстремальних значень, швидке сортування працює досить добре.
В алгоритмі швидкого сортування, що приводиться нижче, як значення розбивки використовується середнє значення. Хоча такий підхід не завжди є найкращим, він досить простий і сортування буде виконуватися правильно.
{ швидке сортування }
procedure QuickSort(var item: DataArray; count:integer);
procedure qs(l, r: integer; var it: DataArray);
var
i, j: integer;
x, y: DataItem;
begin
i:=l; j:=r;
x:=it[(l+r) div 2];
repeat
while it[i]<x do i := i+1;
while x<it[j] do j := j-1;
if y<=j then
begin
y := it[i];
it[i] := it[j];
it[j] := y;
i := i+1; j := j-1;
end;
until i>j;
if l<j then qs(l, j, it);
if l<r then qs(i, r, it)
end;
begin
qs(1, count, item);
end; { кінець швидкого сортування }
У даному прикладі процедура швидкого сортування звертається до основної процедури сортування з ім'ям "qs". Це забезпечує доступ до даних "item" і "count" при усіх викликах "qs".
Можна вважати, що число операцій порівняння дорівнює n*log2
n, а число операцій обміну дорівнює приблизно n/6*log2
n. Ці характеристики значно краще характеристик розглянутих раніше сортувань.
Однак, варто мати на увазі одна неприємна властивість швидкого сортування. Якщо обиране для розбивки значення виявляється співпадаючої з максимальним значенням, то швидке сортування перетворюється в саму повільну з часом виконання n. Однак на практиці цей випадок не зустрічається.
1.11 Порівняльний аналіз методів сортування
Отже, який же метод є кращим? І від чого залежить вибір того або іншого методу при рішенні задач на сортування?
Виходячи з того, що основним критерієм ефективності алгоритму сортування є швидкість, можна зробити висновок, що методи Шелла і Хоара є найбільш оптимальними.
Недоліком "швидкої" сортування є можливість різкого збільшення трудомісткості при "несприятливому" вихідному порядку елементів у масиві. З іншого боку, метод "Шелла" у цілому відстає по швидкості від "швидкої" сортування.
Однак у деяких програмах сортування краще використовувати прості алгоритми. Програми сортування часто використовуються тільки один раз (або кілька разів). Якщо кількість елементів, який потрібно відсортувати не велике (скажемо менше ніж 500 елементів), то може виявитися, що використання простого алгоритму буде більш ефективно, чим розробка і налагодження складного алгоритму. Елементарні методи завжди придатні для маленьких файлів (скажемо менших, чим 50 елементів); малоймовірно, що складний алгоритм було б розумно використовувати для таких файлів, якщо звичайно не потрібно сортувати велику кількість таких файлів.
Як правило, елементарні методи, що були мною розглянуті, роблять біля N2
операцій для сортування N довільно узятих елементів. Якщо N досить мало, то це може і не бути проблемою, і якщо елементи розподілені не довільним образом, те ці алгоритми можуть працювати навіть швидше, ніж складні. Однак варто запам'ятати те, що ці алгоритми не слід використовувати для великих, довільно упорядкованих файлів.
У такий спосіб вибір на користь того або іншого алгоритму може бути зроблений за умови ретельного статистичного аналізу реальної задачі.
ВИСНОВОК
Задача сортування в програмуванні не вирішена цілком. Хоч і існує велика кількість алгоритмів сортувань, усе-таки таки метою програмування є не тільки розробка алгоритмів сортування елементів, але і розробка найефективніших алгоритмів сортування.
Розглянуті в даній роботі методи сортування мають як переваги, так і недоліки. Вибір того або іншого алгоритму сортування залежить від конкретної задачі.
Так, сортування великого числа елементів бульбашковим методом, методом вставки або вибору вимогає багато часу, тому що час виконання сортування знаходиться в квадратичній залежності від числа елементів масиву. Для великих обсягів даних ці сортування будуть повільними, а починаючи з деякої величини, вони будуть занадто повільними, щоб їх можна було використовувати на практиці. Однак, вони ідеально підходять для сортування невеликої кількості елементів. Крім цього, сортування включенням має дві переваги. По-перше, воно має природне поводження, тобто воно виконується швидше для упорядкованого масиву і довше всего виконується, коли масив упорядкований у зворотному напрямку. Це робить сортування включенням корисним для упорядкування майже відсортованих масивів. По-друге, елементи з однаковими ключами не переставляються: якщо список елементів сортується з використанням двох ключів, то після завершення сортування включенням він як і раніше буде упорядкований по двох ключах.
І, нарешті, деякі з простих методів можна розширити до більш хороших методів або використовувати їх для поліпшення складніших. Наприклад, таких як метод Хоара і метод Шелла.
СПИСОК ВИКОРИСТАНИХ
ДЖЕРЕЛ
1. Глушков, В.Н. Основи безпаперової інформатики Изд. 2-і, испр./Н. В. Глушков - М: Наука, 1987.
- 232с.
2.
Джордейн, Р. Довідник програміста персональних комп'ютерів типу IBM PC, XT і AT: Пер. с англ./ Предисл.
Н.В. Гайского, 2001 – 116с.
3. Довгаль, С.И. Персональні ЕОМ: Турбо-Паскаль V6.0, Об'єктне програмування, Локальні мережі. (навчальний посібник)/, С.И. Довгаль, Б.Ю. Литвинов, А.И. Сбитнєв , - Київ: Информсистема сервіс, 1993.
- 210с.
4. Зубків, С.В. Assembler, DOS, Windows і Unix./С.В. Зубків - М.: ДМК, 1999.
-640с.
5. Корнеев, В.В. Сучасні мікропроцесори. /В.В. Корнеев, А.В. Кисельов - М.: Нолидж, 1998.
-376с.
6.
Гук, М.А. Процесори Pentium II, Pentium Pro і просто Pentium./ М.А. Гук - С-Пб: Питер, 1999.
- 183с.
7.
Офіцерів, Д.В. Програмування в інтегрованому середовищі Турбо-Паскаль: Справ. посібник. /Д.В. Офіцерів, В.А. Старих - Мн.: Бєларусь, 1992.
- 240с.
8. Павловская, Т.А. Паскаль. Програмування мовою високого рівня: Підручник для вузів/ Т.А. Павловская – Спб.: Питер, 2006.
- 123 с.
9. Перминов, О.Н. Програмування мовою Паскаль. / О.Н. Перминов - М.: Радіо і зв'язок, 1988.
- 156с.
10.
Прайс, Д. Програмування мовою Паскаль: Практичне керівництво. Пер. с англ./Д. Прайс - М.: Світ, 1987.
- 232с.