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

Демонстрація сортування методом спливаючих бульбашок

Зміст

TOC \o «1-3» \h \z \u HYPERLINK \l «_Toc153205445» Вступ PAGEREF
_Toc153205445 \h 2

HYPERLINK \l «_Toc153205446» I Теоритичні відомості PAGEREF
_Toc153205446 \h 4

HYPERLINK \l «_Toc153205447» 1.1 Необхідність вивчення методів
сортування даних. PAGEREF _Toc153205447 \h 4

HYPERLINK \l «_Toc153205448» 1.2 Підготовча робота. PAGEREF
_Toc153205448 \h 5

HYPERLINK \l «_Toc153205449» 1.3.Найпростіші методи сортування.
PAGEREF _Toc153205449 \h 6

HYPERLINK \l «_Toc153205450» 1.4. Складніші і більш ефективні методи
сортування. PAGEREF _Toc153205450 \h 11

HYPERLINK \l «_Toc153205451» 1.5. Порівняльна характеристика методів
сортування. PAGEREF _Toc153205451 \h 18

HYPERLINK \l «_Toc153205452» II Алгоритм реалізації проекту PAGEREF
_Toc153205452 \h 20

HYPERLINK \l «_Toc153205453» 2.1.Підготовча робота PAGEREF
_Toc153205453 \h 20

HYPERLINK \l «_Toc153205454» 2.2.Розробка частини про принцип
сортування. PAGEREF _Toc153205454 \h 20

HYPERLINK \l «_Toc153205455» 2.3.Розробка частини для виконання
сортування. PAGEREF _Toc153205455 \h 22

HYPERLINK \l «_Toc153205456» III Лістинг програмного коду. PAGEREF
_Toc153205456 \h 25

HYPERLINK \l «_Toc153205457» 3.1.Головний модуль PAGEREF
_Toc153205457 \h 25

HYPERLINK \l «_Toc153205458» 3.2.Модуль програми PAGEREF
_Toc153205458 \h 25

HYPERLINK \l «_Toc153205459» Висновок PAGEREF _Toc153205459 \h 32

HYPERLINK \l «_Toc153205460» Список використаних джерел та програмних
засобів PAGEREF _Toc153205460 \h 33

Вступ

Важко собі уявити, як користуватися списками об’єктів, якщо інформація в
них би не була відсортована. Процесом сортування називають дії по
впорядкуванню деяких даних (таблицю) по ключу. Ключі можуть бути
різними. Наприклад, перетворити:

Таблицю чисел за збільшенням;

Таблицю прізвищ — за абеткою, причому тільки по першій букві

Елементи, що стоять тільки на парних місцях таблиці в убуваючому
порядку.

Очевидно, що з «відсортованими даними» працювати легше і швидше, ніж з
довільно розташованими. Коли елементи «відсортовані», простіше знайти,
наприклад, телефон товариша в телефонній книзі на 500 сторінок, швидше
знайти слово в словнику на 700 сторінок.

Всі ЕОМ засновані на здібності до швидкої і точної обробки великих
об’ємів інформації, а це можливо тільки коли інформація однорідна і
відсортована. Таким чином, таблиці як основний засіб представлення
однорідної інформації неминуче використовуються у всіх реальних
комп’ютерних програмах. На табличному принципі заснована і архітектура
сучасних ЕОМ: пам’ять машини можна розглядати як великий масив байтів,
адреси яких розташовуються за збільшенням. Отже, без розуміння
інформаційної сутності таблиць і основних алгоритмів їх обробки
неможливе формування повноцінних уявлень про можливості ЕОМ і принципи
їх роботи.

Для побудови скільки-небудь складних і змістовних програм необхідне
упевнене володіння загальними принципами застосування таблиць і базовими
прийомами їх обробки.

Тому темою даної роботи є демонстрація сортування методом «бульбашки».

Метою створити програму для ефективного подання принципів роботи
алгоритму сортування.

Перед розробкою роботи були поставленні завдання:

Створити програму для демонстрації сортування методом «бульбашки».

Розглянути існючі методи сортування.

I Теоритичні відомості

1.1 Необхідність вивчення методів сортування даних.

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

Очевидно, що відсортованими даними легше користуватися, ніж довільно
розташованими даними. Коли елементи відсортовані, їх простіше
відшукати, простіше проводити з ними різні операції. У відсортованих
даних легше визначити, чи є пропущені елементи. Для двох відсортованих
таблиць легше знайти загальні елементи. Сортування також є могутнім
засобом прискорення роботи практично будь-якого алгоритму, в якому
виникає необхідність частого звернення до певних елементів. Як пише один
з класиків теорії програмування Д. Кнут «Навіть якщо б сортування було
майже даремне, знайшлася б маса причин зайнятися нею! Винахідливі
методи сортування говорять про те, що вона і сама по собі цікава як
об’єкт дослідження». Аналіз цих методів дуже корисний і з погляду
навчання, оскільки з їх допомогою можна наочно проілюструвати самі різні
ситуації. За словами творця мови Паскаль, Н. Вірта, «створюється
враження, що можна побудувати цілий курс програмування, вибираючи
приклади тільки із задач сортування». Цікавий цей клас алгоритмів ще і
тим, що на ньому наочно демонструються багатющі можливості
програмування: наскільки різними шляхами можна прийти до однієї мети —
отримання впорядкованого масиву! На безлічі алгоритмів сортування стає
зрозумілою необхідність порівняльного аналізу алгоритмів і оцінки їх
якості, критеріями якого є збільшення швидкодії і економії пам’яті.

1.2 Підготовча робота.

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

Важливе питання, на яке треба відповідати при рішенні реальних задач, —
коли слідує і коли не слід об’єднувати прості змінні в таблиці. Ключ до
відповіді — розуміння таблиці як складової величини, що містить
однорідну інформацію. Однорідність означає, що всі елементи таблиці
равноправні: мають однаковий зміст, сенс, при обробці виконуються
однакові операції.

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

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

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

Реальний інтерес представляють задачі перестановки, в яких необхідно
переставити елементи заданої таблиці відповідно до якихось вимог. Ці
задачі не зводяться до інших і можуть розглядатися як самостійна група.
Головна задача перестановки — це сортування елементів масиву, тобто
елементи масиву необхідно переставити так, щоб вони розташовувалися,
наприклад, за збільшенням. Задача сортування масивів не виникає ні
звідки , а відноситься до однієї з груп задач на табличні величини.
Остаточно одержуємо такі групи задач:

1. Заповнення

2. Аналіз

3. Пошук

4. Перестановка.

Фактично всі основні прийоми побудови алгоритмів формуються на лінійних
таблицях. Обробка прямокутних таблиць приводить до кількісного, але не
якісному ускладнення. Лінійна таблиця — це основне, первинне поняття, а
прямокутна таблиця може бути побудований як лінійна таблиця, що
складається з лінійних таблиць. Тому достатньо розглянути згадуючи, але
не розбираючи детально, прямокутні. тільки лінійні таблиці, мабуть,

1.3.Найпростіші методи сортування.

Для вирішення багатьох задач із пошуку потрібного елемента, складання
словників, довідників, складання лотерейних таблиць, списку учнів в
журналі, зручно спочатку упорядкувати дані по певній ознаці.

Дані, наприклад, елементи масиву, можна відсортувати:

за збільшенням — кожний наступний елемент більше попереднього:
а[1]< а[2]< а[n]; по неспаданню - кожний наступний елемент не менше попереднього: а [1] <= а[2]<=. . .<= а[n]; по спаданню - кожний наступний елемент менше попереднього: а [1]> а[2]> … >а[n]

по незростанню — кожний наступний елемент не більше попереднього:
а [1] >= а [2]>= … >=a[n].

Існує досить багато різних методів сортування, відмінних один від одного
ступенем ефективності, під якою розуміється кількість порівнянь і
кількість обмінів, проведених в процесі сортування, час виконання і
об’єм займаний в оперативні й пам’яті. Розглянемо детально деякі з
вказаних методів. Проте, перш ніж розглядати будь-якій з методів
сортування необхідно повторити окремі вже вивчені алгоритми, на які ці
методи спираються. Спочатку розглянемо два методи сортування:

сортування вибором і сортування обміном.

Обидва методи не дуже ефективні і на практиці використовуються украй
рідко. Але тоді чому ними потрібно взагалі займатися?

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

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

Розглянемо сортування вибором.

Сортування вибором полягає в тому, що спочатку в невпорядкованій
послідовності вибирається мінімальний елемент. Цей елемент виключається
з подальшої обробки, а послідовність елементів, що залишилася,
приймається за початкову і процес повторюється до тих пір, поки всі
елементи не будуть вибрані. Очевидно, що вибрані елементи утворюють
впорядковану послідовність. Вибраний в початковій послідовності
мінімальний елемент розміщується на призначеному йому місці
впорядкованої послідовності декількома способами:

1. Мінімальний елемент після i-го перегляду переміщається на i-е місце (
i=1, 2, 3 . . .) іншого масиву, а в старому, початковому, на місці
вибраного розміщується дуже велике число ,яке перевищує по величині
будь-який елемент сортованого масиву. Змінений таким чином масив
приймається за початковий, і здійснюється наступний перегляд. Очевидно,
що при цьому розмір оброблюваного масиву на 1 менше розміру
попереднього.

2. Мінімальний елемент після i-го перегляду переміщається на i-е місце (
i=1, 2, 3 . . . ) заданого масиву, а елемент з i-го місця — на місце
вибраного. Після кожного перегляду впорядковані елементи ( від першого
до елемента з індексом i ) виключаються з подальшої обробки, тобто
розмір кожного подальшого оброблюваного масиву на 1 менше розміру
попереднього.

Цей метод сортування звичайно застосовується для масивів, що не містять
, елементів що повторюються . Для досягнення поставленої мети можна
діяти таким чином:

1) вибрати максимальний елемент масиву;

2) поміняти його місцями з останнім елементом (після цього найбільший
елемент стоятиме на своєму місці);

3) повторити пункти. 1-2 з N-1 елементами, що залишилися, тобто
розглянути частину масиву, починаючи з першим елементом до
передостаннього, знайти в ній максимальний елемент і поміняти його
місцями з передостаннім ; (N-1)-м елементом масиву і так далі поки не
залишиться один елемент, вже що стоїть на своєму місці.

Всього буде потрібно N-1 раз виконати цю послідовність дій. В процесі
сортування збільшуватиметься відсортована частина масиву, а не
відсортована, відповідно, зменшуватися. Отже цей метод грунтується на
знаходженні максимального (мінімального) значення і перестановках.

Хід сортування масиву 30, 17, 73, 47, 22, 11, 65, 54 відобразимо в
таблиці

К Массив

1 30 17 73 47 22 11 65 54

2 11 17 73 47 22 30 65 54

3 11 17 73 47 22 30 65 54

4 11 17 22 47 73 30 65 54

5 11 17 22 30 73 47 65 54

6 11 17 22 30 47 73 65 54

7 11 17 22 30 47 54 65 73

8 11 17 22 30 47 54 65 73

Повертаючись ще раз до питання про ефективність алгоритмів сортування
вибором, встановимо, що якнайменша кількість дій виконуватиметься для
початкового масиву, вже відсортованого вже в потрібному порядку.
Найбільша кількість дій виконуватиметься для початкового масиву,
відсортованого в «протилежному значенні».

Розглянемо сортування обміном (метод «Бульбашки»).

Сортування обміном — метод, при якому всі сусідні елементи масиву
попарно порівнюються один з одним і міняються місцями в тому випадку,
якщо попередній елемент більше подальшого. В результаті цього
максимальний елемент поступово зміщується вправо і, врешті-решт, займає
праве місце в масиві, після чого він виключається з подальшої обробки.
Потім процес повторюється і своє місце займає другий за величиною
елемент, який також виключається з подальшого розгляду. Так
продовжується до тих пір, поки вся послідовність не буде впорядкована.
Якщо послідовність сортованих чисел розташувати вертикально ( перший
елемент — внизу ) і прослідити за переміщеннями елементів , то можна
побачити, що великі елементи, подібно бульбашкам повітря у воді,
«впливають» на відповідну позицію. Тому «сортування» таким чином
називають ще сортуванням методом «бульбашки», або «бульбашковим
сортуванням».

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

Отже, в сортуванні «обміном» всі сусідні елементи попарно порівнюються
один з одним і міняються місцями, якщо попередній елемент більше
наступного. Тобто ми знову грунтуємося на вже відпрацьованих алгоритмах
перестановки елементів.

Вдосконалене «сортування методом бульбашки».

Ясно, що N-1 проходження через масив завжди дає відсортований масив, але
можна скоротити кількість операцій (або проходжень через масив).
Залежно від початкових даних масив може бути вже відсортований вже при
K-му проходженні. Варто розглянути ще однин варіант поліпшення методу
«сортуванням методом бульбашки» — поперемінні проходи масиву в обох
напрямах, а не тільки від початку до кінця. Час сортування скорочується.
Такий метод сортування називається «шейкер» — сортуванням (від
англійського слова shake- трясти, струшувати). Не дивлячись на всі
зроблені вище удосконалення, «бульбашкове сортування» наступного (
майже впорядкованого! ) масиву 5, 7, 12, 28, 36, 85 ,2 буде проведений
за сім проходів. Це зв’язано з тим, що при сортуванні, даним методом, за
один прохід елемент не може переміститися вліво більш ніж на одну
позицію. Отже якщо мінімальний елемент масиву знаходиться в його правому
кінці (як в даному прикладі), то доведеться виконати максимальне число
проходів.

Сортування підрахунком.

Цей простий і легкий для розуміння метод полягає в тому, що кожний
елемент масиву порівнюється зі всіма іншими. Місце кожного елемента у
відсортованому масиві залежить від числа елементів, менших його. Іншими
словами, якщо деякий елемент перевищує 13 інших, то його місце у
впорядкованій послідовності — 14. Отже, для сортування необхідно
порівняти попарно всі елементи і підрахувати, скільки з них менше
кожного окремого елемента. Після цього всі елементи початкового масиву
можна розмістити на відповідних їм місцях в новому, спеціально
створеному масиві.

Сортування вставками (методом прямого включення).

Сортування вставками, так само як і сортування методом простого вибору,
звичайно застосовується для масивів, що не містять повторюваних
елементів. Сортування методом прямого включення, як і всі описані вище,
проводиться по кроках. На к-м кроці вважається, що частина масиву, що
містить перші k-1 елементів, вже впорядкована, тобто а[1]< а[2]< . . . < а[к-l]. Далі необхідно узяти k-й елемент і підібрати для нього таке місце у відсортованій частині масиву, щоб після його вставки впорядкованість не порушилася, тобто треба знайти таке j (1<=j<=k-1), що а[j ]<=a[k] . 1.4. Складніші і більш ефективні методи сортування. При рішенні складніших задач доводиться обробляти великі набори даних. Застосування простих для розуміння, але повільно працюючих методів сортування, висловлених в попередньому розділі, стає недоцільно. Обмінне сортування з розділенням (сортування Хоара) . Сортування методом простого обміну (методом "бульбашки") є в середньому найефективнішим. Це обумовлено самою ідеєю методу, який вимагає в процесі сортування порівнювати і обмінювати між собою тільки сусідні елементи. Можна істотно поліпшити метод сортування, заснований на обміні. Це поліпшення приводить до найкращому методу сортування масивів, який можна назвати обмінним сортуванням з розділенням. Він заснований на порівняннях і обмінах елементів, що стоять на можливо великих відстанях один від одного. Запропонував цей метод Ч. А. Р. Хоар в 1962 році. Оскільки продуктивність цього методу вражаюча, автор назвав його "швидким сортуванням". Сортування методом злиття. Існує ще один метод сортування елементів масиву, ефективність якого порівняно велика, - метод злиття. Метод сортування "злиттям" полягає в розбитті даного масиву на декілька частин, які сортуються по окремості і згодом "зливаються" в одну. Хай масив а [1..n] розбивається на частини завдовжки k, тоді перша частина - а[I], а [2] . . ., а [k], друга [k+l], а[k+2]..., а[2k] і так далі. Якщо n не ділиться на k, то в останній частині буде менш k елементів. Після того, як масиви-частини впорядковані, можна об'єднати їх у впорядковані масиви-частини, які складаються з не більше ніж з 2k елементів, які далі об’єднуються у впорядковані масиви завдовжки не більш 4k,і так далі поки не вийде один впорядкований масив. Так, щоб отримати відсортований масив цим методом, потрібно багато разів " зливати" два впорядковані відрізки масиву в один впорядкований відрізок. При цьому інші частини масиву не зачіпаються. Сортування методом Шелла Ідея алгоритму полягає в обміні елементів, розташованих не тільки поряд, як в сортуванні методом вставок, але і далеко один від одного, що значно скорочує загальне число операцій переміщення елементів. Для прикладу візьмемо масив з 16 елементів. Спочатку продивляються пари з кроком 8. Це пари елементів 1-9, 2-10, 3-11,4-12, 5-13, 6-14, 7-15, 8-16. Якщо значення елементів в парі не впорядковані за збільшенням, то елементи міняються місцями. Назвемо цей етап 8-сортуванням. Наступний етап — 4-сортування, на якому елементи у масиві діляться на четвірки: 1-5-9-13, 2-6-10-14, 3-7-11-15,4-8-12-16. Виконується сортування в кожній четвірці. Наступний етап — 2-сортування, коли елементи у масиві діляться на 2 групи по 8: 1-3-5-7-9-11-13-15 і 2-4-6-8-10-12-14-16. Виконується сортування в кожній вісімці. Нарешті весь масив упорядковується методом вставок. Оскільки дальні елементи вже перемістилися на своє місце або знаходяться поблизу від нього, цей етап буде значний менш трудомістким, ніж при сортуванні вставками без попередніх «дальніх обмінів». Багатофазне сортування Ідея багатофазного сортування полягає в тому, що з наявних m допоміжних масивів (m-1) масив служить для введення зливаних послідовностей, а один - для виведення утворюваних серій. Як тільки один з масивів введення стає порожнім, його починають використовувати для виведення серій, одержуваних при злитті серій нового набору (m-1) масиві. Таким чином, є перший крок, при якому серії початкового масиву розподіляються по m-1 допоміжному масиву, а потім виконується багатопутнє злиття серій з (m-1) масиву, поки в одному з них не утворюється одна серія. Очевидно, що при довільному початковому розподілі серій по допоміжних масивах алгоритм може не зійтися, оскільки в єдиному непорожньому масиві існуватиме більш, ніж одна серія. Припустимо, наприклад, що використовується три масиви B1, B2 і B3, і при початковому розподілі у масив B1 поміщено 10 серій, а у масив B2 - 6. При злитті B1 і B2 до моменту, коли ми дійдемо до кінця B2, в B1 залишаться 4 серії, а в B3 потраплять 6 серій. Продовжиться злиття B1 і B3, і при завершенні перегляду B1 в B2 міститимуться 4 серії, а в B3 залишаться 2 серії. Після злиття B2 і B3 в кожному з масивів B1 і B2 міститиметься по 2 серії, які злитимуться і утворюють 2 серії в B3 при тому, що B1 і B2 - порожні. Тим самим, алгоритм не зійшовся (таблиця 3.2). Таблиця 3.2. Приклад початкового розподілу серій, при якому трифазне зовнішнє сортування не приводить до потрібного результату Число серій у масиві B1 Число серій у масиві B2 Число серій у масиві B3 10 6 0 4 0 6 0 4 2 2 2 0 0 0 2 Спробуємо зрозуміти, яким повинен бути початковий розподіл серій, щоб алгоритм трифазного сортування благополучно завершував роботу і виконувався максимально ефективно. Для цього розглянемо роботу алгоритму в зворотному порядку починаючи від бажаного кінцевого стану допоміжних масивів. Нас влаштовує будь-яка комбінація кінцевого числа серій у масивах B1, B2 і B3 з (1,0,0), (0,1,0) і (0,0,1). Для визначеності виберемо першу комбінацію. Для того, щоб вона склалася необхідно, щоб на безпосередньо попередньому етапі злиття існував розподіл серій (0,1,1). Щоб отримати такий розподіл, необхідно, щоб на безпосередньо попередньому етапі злиття розподіл виглядав як (1,2,0) або (1,0,2). Знову для визначеності зупинимося на першому варіанті. Щоб його отримати, на попередньому етапі годилися б наступні розподіли: (3,0,2) і (0,3,1). Але другий варіант гірше, оскільки він приводиться до злиття тільки однієї серії з файлів B2 і B3 тоді як за наявності першого варіанту розподілу злитимуться дві серії з файлів B1 і B3. Побажанням до попереднього етапу була б наявність розподілу (0,3,5), ще раніше - (5,0,8), ще раніше - (13,8,0) і т.д. Цей розгляд показує, що метод трифазного зовнішнього сортування дає бажаний результат і працює максимально ефективно (на кожному етапі зливається максимальне число серій) якщо початковий розподіл серій між допоміжними файлами описується сусідніми числами Фібоначчі. Нагадаємо, що послідовність чисел Фібоначчі починається з 0, 1, а кожне наступне число утворюється як сума двох попередніх: (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ....) Аналогічні (хоча і більш громіздкі) міркування показують, що в загальному вигляді при використовуванні m допоміжних файлів умовою успішного завершення і ефективної роботи методу багатофазного зовнішнього сортування є те щоб початковий розподіл серій між m-1 файлами описувався сумами сусідніх (m-1), (m-2) ..., 1 чисел Фібоначчі порядку m-2. Послідовність чисел Фібоначчі порядку p починається з p нулів, (p+1)-й елемент рівний 1 а кожний наступний дорівнює сумі попередніх p+1 елементів. Нижче показано початок послідовності чисел Фібоначчі порядка 4: (0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 31, 61 ...) При використовуванні шести допоміжних файлів ідеальними розподілами серій є наступні: 1 0 0 0 0 1 1 1 1 1 2 2 2 2 1 4 4 4 3 2 8 8 7 6 4 16 15 14 12 8 ........ Зрозуміло, що якщо розподіл заснований на числі Фібоначчі fi, то мінімальне число серій в допоміжних файлах буде рівне fi, а максимальне - f(i+1). Тому після виконання злиття ми отримаємо максимальне число серій - fi, а мінімальне - f(i-1). На кожному етапі виконуватиметься максимально можливе число злиття, і процес зійдеться до наявності всього однієї серії. Оскільки число серій в початковому файлі може не забезпечувати можливість такого розподілу серій, застосовується метод додавання порожніх серій, які надалі якомога більш рівномірного розподіляються між проміжними файлами і пізнаються при подальшому злитті. Зрозуміло, що ніж менше таких порожніх серій, тобто чим ближче число початкових серій до вимог Фібоначчі, тим більше ефективно працює алгоритм. Сортування за допомогою дерева Почнемо з простого методу сортування за допомогою дерева, при використовуванні якого будується двійкове дерево порівняння ключів. Побудова дерева починається з листків, яке містить всі елементи масиву. З кожної сусідньої пари вибирається найменший елемент, і ці елементи утворюють наступний (ближче до кореня рівень дерева). З кожної сусідньої пари вибирається якнайменший елемент і т.д., поки не буде побудований корінь, якнайменший елемент масиву, що містить. Отже, ми вже маємо якнайменше значення елементів масиву. Для того, щоб отримати наступний по величині елемент, спустимося від кореня по шляху, що веде до листа з якнайменшим значенням. В цій листовій вершині проставляється фіктивний ключ з "нескінченно великим значенням", а у все проміжні вузли, що займалися якнайменшим елементом, заноситься якнайменше значення з вузлів - безпосередніх нащадків . Процес продовжується до тих пір, поки всі вузли дерева не будуть заповнені фіктивними ключами . На кожному з n кроків, що вимагаються для сортування масиву, потрібно log n (двійковий) порівнянь. Отже, всього буде потрібно log n порівнянь, але для представлення дерева знадобиться 2n - 1 додаткових одиниць пам'яті. Є досконаліший алгоритм, який прийнято називати пірамідальним сортуванням . Його ідея полягає в тому, що замість повного дерева порівняння початковий масив а[1], а[2] ..., а[n] перетвориться в піраміду, що володіє тією властивістю що для кожного а[i] виконуються умови а[i]<= а[2i] і а[i]<= а[2i+1]. Потім піраміда використовується для сортування. Масив представляється у вигляді двійкового дерева, корінь якого відповідає елементу масиву а[1]. На другому ярусі знаходяться елементи а[2] і а[3]. На третьому - а[4], а[5], а[6], а[7] і т.д. Як видно, для масиву з непарною кількістю елементів відповідне дерево буде збалансованим, а для масиву з парною кількістю елементів n елемент a[n] буде єдиним (найлівішим) листом "майже збалансованого дерева". Очевидно, що при побудові піраміди нас цікавитимуть елементи а[n/2], а[n/2-1] ..., а[1] для масивів з парним числом елементів і елементи а[(n-1)/2], а[(n-1)/2-1] ..., а[1] для масивів з непарним числом елементів (оскільки тільки для таких елементів істотні обмеження піраміди). Хай i - найбільший індекс з числа індексів елементів, для яких істотні обмеження піраміди. Тоді береться елемент а[i] в побудованому дереві і для нього виконується процедура просівання, що полягає в тому, що вибирається гілка дерева, відповідна min(а[2 або i], а[2 або i+1]), і значення а[i] міняється місцями із значенням відповідного елемента. Якщо цей елемент не є листом дерева, для нього виконується аналогічна процедура і т.д. Такі дії виконуються послідовно для а[i], а[i-1] ..., а[1]. Легко побачити що в результаті ми отримаємо деревоподібне представлення піраміди для початкового масиву . В 1964 р. Флойд запропонував метод побудови піраміди без явної побудови дерева (хоча метод заснований на тих же ідеях). Побудова піраміди методом Флойда для нашого стандартного масиву показана в таблиці Приклад побудови піраміди Початковий стан масиву 8 23 5 |65| 44 33 1 6 Крок 1 8 23 |5| 6 44 33 1 65 Крок 2 8 |23| 1 6 44 33 5 65 Крок 3 |8| 6 1 23 44 33 5 65 Крок 4 1 6 8 23 44 33 5 65 1 6 5 23 44 33 8 65 В наступній таблиці показано, як проводиться сортування з використанням побудованої піраміди. Суть алгоритму полягає в наступному. Хай i - найбільший індекс масиву, для якого істотні умови піраміди. Тоді починаючи з а[1] до а[i] виконуються наступні дії. На кожному кроці вибирається останній елемент піраміди (в нашому випадку першим буде вибраний елемент а[8]). Його значення міняється із значенням а[1], після чого для а[1] виконується просівання. При цьому на кожному кроці число елементів в піраміді зменшується на 1 (після першого кроку як елементи піраміди розглядаються а[1], а[2] ..., а[n-1]; після другого - а[1], а[2] ..., а[n-2] і т.д., поки в піраміді не залишиться один елемент). Легко бачити , що в результаті ми отримаємо масив, впорядкований в порядку убування. Можна модифікувати метод побудови піраміди і сортування, щоб отримати впорядкування в порядку зростання якщо змінити умову піраміди на а[i]>= а[2?i] і а[1]>= а[2?i+1] для всіх осмислених
значень індексу i.

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

Початкова піраміда 1 6 5 23 44 33 8 65

Крок 1 65 6 5 23 44 33 8 1

5 6 65 23 44 33 8 1

5 6 8 23 44 33 65 1

Крок 2 65 6 8 23 44 33 5 1

6 65 8 23 44 33 5 1

6 23 8 65 44 33 5 1

Крок 3 33 23 8 65 44 6 5 1

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

1.5. Порівняльна характеристика методів сортування.

Пригадаємо один з простих методів — метод підрахунку. Оскільки цей
метод, не дивлячись на удосконалення, вимагає порівняння всіх пар
елементів, то тривалість сортування масиву з n елементів буде
пропорційна n2. Дещо кращі показники мають методи сортування вставками,
обміном і вибором, проте і в них тривалість роботи процедур також
пропорційна n2. Разом з тим можна показати, що час, затрачуваний на
впорядковування масиву такими методами, як, наприклад, швидке сортування
або пірамідальне сортування, пропорційно n log2n, тобто значно менше.
Тому всі розглянуті методи сортування розділяють на прості (n2) і
вдосконалені, або «логарифмічні» (n log2n) .

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

Н.Вірт відзначає також наступне:

— «сортування методом бульбашки» є найгіршим серед всіх порівнюваних
методів. Її поліпшений варіант — «шейкер» – сортування.

— все-таки гірше, ніж сортування простими вставками і сортування
вибором;

— особливістю швидкого сортування є те, що вона сортує масив з
елементами, розташованими в зворотному порядку практично так само, як і
відсортований в прямому порядку. Слід додати, що приведені результати
були отримані при сортуванні числових масивів. Якщо ж значенням
елементів масиву є дані типу «запис», в яких супутні поля (компоненти)
займають в 7 разів більше пам’яті, ніж числове поле, по якому
проводиться сортування, то картина зміниться.

II Алгоритм реалізації проекту

2.1.Підготовча робота

Вікно програми умовно розділимо на дві частини:

Частина де буде виводитись інформація про принцип сортування методом
«бульбашки»;

Частина буде виконуватися сортування даних які ввів користувач.

Інформація про принцип сортування буде знаходитись в текстовому файлі
під назвою “text.txt”.

2.2.Розробка частини про принцип сортування.

Виведення інформації про сортування буде отримуватися з текстового
файлу за допомогою даних операторів:

AssignFile(f,’text.txt’);

Reset(f);

Які розміщенні в обробнику події onCreate форми програми, та

Readln(f,s)- який в змінні s присвоює наступну стрічку тексту.

Виведення на екран буде виконуватися таймером , текст із змінної s буде
поміщатися в компоненти Label, при чому значення властивості Caption
наступного компонента Label буде присвоюватися занченню попереднього
компонента що створить ефект титрів:

procedure TForm1.Timer1Timer(Sender: TObject);

var

s:string;

begin

Readln(f,s);

if s=» then Timer1.Enabled:=False;

Label1.Caption:=Label2.Caption;

Label2.Caption:=Label3.Caption;

Label3.Caption:=Label4.Caption;

Label4.Caption:=Label5.Caption;

Label5.Caption:=Label6.Caption;

Label6.Caption:=Label7.Caption;

Label7.Caption:=Label8.Caption;

Label8.Caption:=s;

end;

Для більш ефектнішого подання теорії в програмі реалізуємо ефект
появлення і зникнення з форми, тобто колір тексту трьох перши і троьох
останіх компонентів Label будуть розміщені в кольоровій гамі між
кольором форми та чорним кольором.

Label1.Font.Color:=rgb(200,190,198);

Label2.Font.Color:=rgb(120,110,96);

Label3.Font.Color:=rgb(45,54,50);

Label6.Font.Color:=rgb(45,54,50);

Label7.Font.Color:=rgb(120,110,96);

Label8.Font.Color:=rgb(200,190,198);

Можливий варіант коли користувач не повністю зрозумів, а бо просто
пропустив теоретичні частину, для цього реалізуємо можливість ще раз
продивитись текст:

var

i:integer;

Com:TComponent;

begin

Reset(f);

for i:=1 to 8 do

begin

Com:=FindComponent(‘Label’+inttostr(i));

(Com as TLabel).Caption:=»;

end;

Timer1.Enabled:=True;

Спочатку перейдемо на початок файлу, щоб виводити інформацію спочатку.

В наступних операторах очистимо всі компоненти Label,запустивши цикл
будемо шукати компоненти з назвою, яка складається з Label та номеру
який генерується циклом , знайдений компонент буде розглядатися як
компонент типу TLabel та властивість Caption буде ощищуватися, та
запустимо таймер для виводу тексту.

Для зупинки виведення тексту просо зупинимо таймер:

Timer1.Enabled:=False;

Тепер перейдемо до розробки безпосередньо частини де виконуватиметься
сортування даних .

2.3.Розробка частини для виконання сортування.

Частина буде містити сім компонентів Edit для введення даних для
сортування.В кожного компонента максимальну кількіст символів які будть
введені обмеженні до двох, шляхом вказання значення 2 в властивості
MaxLength.Для авоматичного переходу на наступий компонент в обробниках
події onChange кожного компонента помістимо код:

if Length((Sender as TEdit).Text)=2 then

keybd_event(VK_TAB,0,0,0);

Тобто компонент який викликав даний код буде розглядатися як компонент
TEdit.При введенні більш ніж двох елементів фокус введнення буде
автоматично переходити на наступний компонент.

Приступимо до занесення даних в масив який буде сортуватися.

Запустивши цикл обробки даних будемо перевіряти коректність введених
даних користувачем в захищеному блоці:

for i:=1 to 7 do

try

b[i]:=StrToInt((FindComponent(‘Edit’+IntToStr(i)) as TEdit).Text);

Flag:=True;

except

ShowMessage(‘Перевірте дані в полі № ‘+IntToStr(i));

Flag:=False;

end;

В разі коректності введених даних значення змінять тип з String на
Integer та занесуться в масив,коли ж дані не правильні виведеться
повідомлення в якому полі введені не правильні дані.Змінна Flag буде
визначати чи правильно введені дані в масив.При умові коректної обробки
даних змінна міститиме значення True і далі розпочнеться сорутвання
масиву.

for k:=1 to 6 do

for i:=1 to 7-k do

if b[i]>b[i+1] then

begin

Application.ProcessMessages;

if E then Exit;

d:=b[i+1];

b[i+1]:=b[i];

b[i]:=d;

Label9.Caption:=»;

for j:=1 to 7 do

begin

Label9.Caption:=Label9.Caption+IntToStr(b[j])+’ ‘;

sleep(200);

end;

end;

Перший цикл буде переглядати масив ,другий цикл буде розміщувати кожен
наступний елемент на відповідну позицію шляхом порівняння з
наступим.Перед порівнянням обробляться всі повідомлення які передались
програмі та перевіриться необхіність виходу з програми в залежкності від
значення Е.

Після переміщення кожного елементу буде виводиться поточне положення
елементів в масиві для візуалізації переміщень значень в масиві.

for j:=1 to 7 do

begin

Label9.Caption:=Label9.Caption+IntToStr(b[j])+’ ‘;

sleep(200);

end;

Після остаточного розміщення всіх елементів виведеться відсортований
масив на екран.

III Лістинг програмного коду.

3.1.Головний модуль

program Project1;

uses

Forms,

Unit1 in ‘Unit1.pas’ {Form1};

{$R *.res}

begin

Application.Initialize;

Application.CreateForm(TForm1, Form1);

Application.Run;

end.

3.2.Модуль програми

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls,
Forms,

Dialogs, StdCtrls, XPMan, ExtCtrls, Mask, jpeg;

type

TForm1 = class(TForm)

Label1: TLabel;

Label2: TLabel;

Label3: TLabel;

Label4: TLabel;

Label5: TLabel;

Label6: TLabel;

Label7: TLabel;

Label8: TLabel;

XPManifest1: TXPManifest;

Timer1: TTimer;

Button1: TButton;

Button3: TButton;

Label9: TLabel;

Edit1: TEdit;

Edit2: TEdit;

Edit3: TEdit;

Edit4: TEdit;

Edit5: TEdit;

Edit6: TEdit;

Edit7: TEdit;

Button4: TButton;

Label10: TLabel;

procedure FormCreate(Sender: TObject);

procedure Timer1Timer(Sender: TObject);

procedure Button1Click(Sender: TObject);

procedure Button3Click(Sender: TObject);

procedure Edit2Change(Sender: TObject);

procedure Button4Click(Sender: TObject);

procedure FormClose(Sender: TObject; var Action: TCloseAction);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

implementation

{$R *.dfm}

Var

f:textfile;

E:Boolean;

k:integer;

procedure TForm1.FormCreate(Sender: TObject);

begin

Label1.Font.Color:=rgb(200,190,198);

Label2.Font.Color:=rgb(120,110,96);

Label3.Font.Color:=rgb(45,54,50);

Label6.Font.Color:=rgb(45,54,50);

Label7.Font.Color:=rgb(120,110,96);

Label8.Font.Color:=rgb(200,190,198);

AssignFile(f,’text.txt’);

Reset(f);

end;

procedure TForm1.Timer1Timer(Sender: TObject);

var

s:string;

begin

Readln(f,s);

if s=» then Timer1.Enabled:=False;

Label1.Caption:=Label2.Caption;

Label2.Caption:=Label3.Caption;

Label3.Caption:=Label4.Caption;

Label4.Caption:=Label5.Caption;

Label5.Caption:=Label6.Caption;

Label6.Caption:=Label7.Caption;

Label7.Caption:=Label8.Caption;

Label8.Caption:=s;

end;

procedure TForm1.Button1Click(Sender: TObject);

var

i:integer;

Com:TComponent;

begin

Reset(f);

for i:=1 to 8 do

begin

Com:=FindComponent(‘Label’+inttostr(i));

(Com as TLabel).Caption:=»;

end;

Timer1.Enabled:=True;

end;

procedure TForm1.Button3Click(Sender: TObject);

var

Flag:Boolean;

b:array[1..7] of integer;

i,d,j:integer;

begin

Label9.Caption:=»;

for i:=1 to 7 do

try

b[i]:=StrToInt((FindComponent(‘Edit’+IntToStr(i)) as TEdit).Text);

Flag:=True;

except

ShowMessage(‘Перевірте дані в полі № ‘+IntToStr(i));

Flag:=False;

end;

if not(Flag) then exit else

for k:=1 to 6 do

for i:=1 to 7-k do

if b[i]>b[i+1] then

begin

Application.ProcessMessages;

if E then Exit;

d:=b[i+1];

b[i+1]:=b[i];

b[i]:=d;

Label9.Caption:=»;

for j:=1 to 7 do

begin

Label9.Caption:=Label9.Caption+IntToStr(b[j])+’ ‘;

sleep(200);

end;

end;

Label9.Caption:=»;

for j:=1 to 7 do

Label9.Caption:=Label9.Caption+IntToStr(b[j])+’ ‘;

end;

procedure TForm1.Edit2Change(Sender: TObject);

begin

if Length((Sender as TEdit).Text)=2 then

keybd_event(VK_TAB,0,0,0);

end;

procedure TForm1.Button4Click(Sender: TObject);

begin

Timer1.Enabled:=False;

end;

procedure TForm1.FormClose(Sender: TObject; var Action: TCloseAction);

begin

E:=True;

end;

end.

Висновок

Результатом створення курсової роботи стала програма для демонстрації
сортування методом «бульбашок».Програма має простий інтерфейс
,зрозумілий кожному , та розриває як теоретичну так і практичну сторони
сортування.

Теоретична частина містить детальний опис методу сортування, а практична
дає можливість побачити на власні очі процес сорування масиву причому
ввівши власні дані для сортування.

До основни переваг програми можна віднести:

Простий та зручний інтерфейс;

Високу інформативність програми;

Реалізована можжливість змінити теоретичні частину виконашши зміни в
файлі text.txt

Можливість використання для навчання в школах та вищих навчальних
закладах.

Проте існують і недоліки:

Програма демонструє роботу не найефективнішого методу сортування;

Програму не можна використати для демонстрування роботи інших методів.

Список використаних джерел та програмних засобів

Інтернет сайти:

HYPERLINK «http://www.citforum.ru» www.citforum.ru

HYPERLINK «http://realcoding.net» http://realcoding.net

HYPERLINK «http://www.code.net» www.code.net

Delphi 7 EnterPrise Edition

Методи сортування та пошуку С.Д.Кузнецов, Центр Інофрмаційних технолгій
, 2001р.

PAGE

PAGE 34

Похожие записи