Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
PAGE 20
Міністерство освіти І науки України
національний університет “Львівська політехніка”
Кафедра ЕОМ
Дослідження ефективності методів сортування
Методичні вказівки
з дисципліни
" AЛГОРИТМИ ТА МЕТОДИ ОБЧИСЛЕНЬ"
для студентів напряму
6.050102 “Комп’ютерна інженерія”
Методичні вказівки до комплексу лабораторних робіт з дисципліни "AЛГОРИТМИ ТА МЕТОДИ ОБЧИСЛЕНЬ" для підготовки студентів напряму 6.050102 “Комп’ютерна інженерія” / Укл. Т.А.Матвейчук – Львів: Видавництво НУ “Львівська політехніка”, 2011 – 12 с.
Укладач: Матвейчук Т.А., ст. викладач каф.ЕОМ
Відповідальний
за випуск: Мельник А.О., д-р техн. наук, проф.
Рецензенти: Мороз І.В., ст. викладач каф.ЕОМ
Юрчак І.Ю., доцент кафедри САПР, к.т.н.
1. МЕТА РОБОТИ
Вивчення і програмна реалізація методів сортування даних та дослідження їх ефективності.
2. ТЕОРЕТИЧНІ ВІДОМОСТІ
2.1. Задача сортування
Задача сортування в програмуванні не вирішена повністю. Адже, хоча й існує велика кількість алгоритмів сортування, все ж таки метою програмування є не лише розробка алгоритмів сортування елементів, але й розробка саме ефективних алгоритмів сортування.
Ми знаємо, що одну й ту саму задачу можна вирішити за допомогою різних алгоритмів і кожен раз зміна алгоритму приводить до нових, більш або менш ефективних розв'язків задачі. Основними вимогами до ефективності алгоритмів сортування є перш за все ефективність за часом та економне використання пам'яті. Згідно цих вимог, прості алгоритми сортування (такі, як сортування вибором і сортування включенням) не є дуже ефективними.
Алгоритм сортування обмінами, хоча і завершує свою роботу (оскільки він використовує лише цикли з параметром і в тілі циклів параметри примусово не змінюються) і не використовує допоміжної пам'яті, але займає багато часу. Навіть, якщо внутрішній цикл не містить жодної перестановки, то дії будуть повторюватись до тих пір, поки не завершиться зовнішній цикл.
Алгоритм сортування вибором ефективніше сортування обмінами за критерієм М(n), тобто за кількістю пересилань, але також є не дуже ефективним. З цих причин було розроблено деякі нові алгоритми сортування, що отримали назву швидких алгоритмів сортування. Це такі алгоритми, як сортування деревом, пірамідальне сортування, швидке сортування Хоара та метод цифрового сортування.
Метою роботи є ознайомлення з цими швидкими алгоритмами сортування, спроба проаналізувати їх і висвітлити кожен з них і написати програму, яка б виконувала сортування деякої послідовності за допомогою різних швидких алгоритмів сортування.
Необхідність відсортувати які-небудь величини виникає в програмуванні дуже часто. Існують ситуації, коли попереднє сортування даних дозволяє скоротити змістовну частину алгоритму в декілька разів, а час його роботи - у десятки разів.
Однак справедливе й зворотне. Яким би гарним і ефективним не був обраний алгоритм, але якщо в якості підзадачі він використовує "поганє" сортування, то вся робота з його оптимізації виявляється марною. Невдало реалізоване сортування вхідних даних здатне помітно знизити ефективність алгоритму в цілому.
2.2. Класифікація методів сортування
Методи впорядкування розділяються на внутрішні (які обробляють масиви) і зовнішні (що працюють тільки з файлами). Ми будемо розглядати тільки внутрішні методи сортування. Їхня важлива особливість полягає в тому, що ці алгоритми не вимагають додаткової пам'яті: вся робота з впорядкування виконується всередині того самого масиву.
|
Методи. сортування |
|
Внутрішнє сортування |
Зовнішнє сортування |
|
Прості методи |
Покращені методи |
Просте злиття |
Природнє злиття |
Збалансо-ване злиття |
Багато-фазне сор-тування |
|
Метод простої вставки |
Метод простого вибору |
Метод простого обміну |
Сортування Шелла. |
Пірамідальне сортування. |
Швидке сортування .
|
|
Шейкер- сортування |
Метод бінарного включення |
рис.1. Класифікація методів сортування
2. 3. Бульбашкове сортування
Розглянемо найпростіший (і найгірший з точки зору витрат часу) спосіб сортування масиву. Нехай A[1], A[2], . , A[n] – масив із довільними значеннями елементів. Порівняємо A[1] і A[2]: якщо A[1]>A[2], то поміняємо їхні значення місцями. Потім порівняємо A[2] і A[3] та за необхідності обміняємо їхні значення. В результаті A[3] має найбільше значення серед A[1], A[2], A[3]. Продовжимо такі порівняння та обміни до кінця масиву: для всіх i від 1 до n-1 виконати якщо A[i]>A[i+1], то значення A[i] та A[i+1] обмінюються.
Якщо значення елементів розглядати як розміри бульбашок, то ці порівняння та обміни схожі на те, як більші бульбашки відтісняють менших униз і спливають нагору. Тому цей метод називається бульбашковим сортуванням. У результаті найбільша бульбашка стає верхньою, тобто останній елемент A[n] має найбільше значення.
Наприклад, послідовність значень <3, 4, 2, 1> перетвориться на <3, 2, 1, 4>. Далі почнемо все спочатку і перемістимо друге за величиною значення до передостаннього елемента A[n-1], перетворивши, наприклад, <3, 2, 1, 4> на <2, 1, 3, 4>. Потім третє за величиною значення перемістимо до A[n-2] тощо. Останній крок складається лише з порівняння A[1]<A[2] (та обміну значень за потреби). Опишемо бульбашкове сортування такою процедурою (bubble – це англійське "бульбашка"): procedure Bubbles1 (var A: ArT; n: Indx); var i, k: Indx; begin for k := n downto 2 do { k – права границя в черговому проході } for i := 1 to k - 1 do if A[i] > A[i+1] then swap (A[i], A[i+1]) end Тут і далі процедура swap задає обмін значень своїх параметрів. Як бачимо, разом виконується (n-1)+(n-2)+…+1= n× (n-1)/2 порівнянь.
Очевидно, що найбільше можливе число елементарних дій за цим способом прямо пропорційне кількості порівнянь. Тому час сортування масиву з n елементів у такий спосіб прямо пропорційний n× (n-1). Якщо при черговому виконанні циклу із заголовком for i:=1 to k-1 do процедури Bubbles1 не було жодного обміну, то масив уже відсортовано. Тому подальші проходи масивом зайві. Переробити процедуру сортування так, щоб її виконання закінчувалося за відсортованого масиву.
2.4. Сортування вибором
Сортування вибором здійснюється здійснюється так. Проглянемо елементи масиву від першого до останнього, визначимо елемент із найменшим значенням, та обміняємо це значення з першим. Потім так само виберемо найменше значення серед A[2] .A[n] і обміняємо його зі значенням A[2], потім виберемо наступне найменше та обміняємо з A[3] тощо.
2.5. Сортування простими вставками
Сортування простими вставками дозволяє створити відсортований масив із значень, що читаються, наприклад, із клавіатури. Перше значення записується на перше місце, тобто присвоюється першому елементу масиву. Друге значення порівнюється з першим і, якщо перше менше, то воно "витісняється" на друге місце. Інакше нове значення йде на друге місце.
Потім третє порівнюється з другим та записується або на третє місце, або витісняє значення з другого місця на третє та порівнюється з тим, що на першому місці.
Наприклад, за читання послідовності значень 3, 1, 2 створюються послідовності значень у масиві <3>, <1, 3>, <1, 2, 3>. Узагалі, після читання k-1 елемента маємо відсортовану частину масиву A[1]A[2] .A[k-1]. Нове значення v порівнюємо зі значенням A[k-1]. Якщо A[k-1]>v, то значення A[k-1] зсуваємо на k-е місце. Після цього порівнюємо v зі значенням A[k-1]: якщо A[k-2]>v, то A[k-2] зсуваємо на (k-1)-е місце тощо. Коли за чергового порівняння A[i]<=v, то v записується на (i+1)-е місце.
Якщо всі значення в масиві більші v, то вони зсуваються, а v записується на перше місце. Уточнити наведений алгоритм процедурою.
2.6. Ефективні алгоритми сортування. Сортування злиттям
В основі цього способу сортування лежить злиття двох упорядкованих ділянок масиву в одну впорядковану ділянку іншого масиву. Злиття двох упорядкованих послідовностей можна порівняти з перебудовою двох колон солдатів, вишикуваних за зростом, в одну, де вони також розташовуються за зростом. Якщо цим процесом керує офіцер, то він порівнює зріст солдатів, перших у своїх колонах і вказує, якому з них треба ставати останнім у нову колону, а кому залишатися першим у своїй. Так він вчиняє, поки одна з колон не вичерпається – тоді решта іншої колони додається до нової.
Нехай у масиві 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 |
За дії означень (17.1) таке злиття двох ділянок у масиві 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 кроки злиття для того, щоб одержати впорядований масив. За дії означень (17.1) такий спосіб сортування описується процедурою 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+ë log2nû ) та округлене відношення r двох останніх:
|
n |
n(n-1)/2 |
n(1+ë log2nû) |
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+ë log2nû ) приблизно в 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 році його винайшов Джон фон Нейман, один із піонерів програмування.
Серйозним недоліком цього алгоритму є необхідність додаткового масиву такої ж довжини, як і в основного. За великих довжин можлива ситуація, коли на один масив пам'яті вистачає, а на два – ні. Розглянемо два алгоритми, позбавлені цього недоліку.
2.7. Пірамідальне сортування
Піраміда, вона ж дерево Уявіть собі, що ми розташували елементи масиву рядками, щоразу подвоюючи їх кількість: у першому рядку – перший елемент, у другому – елементи з індексами 2, 3, у наступному – 4, 5, 6, 7, далі 8, 9, 10, 11, 12, 13, 14, 15 тощо. Останній рядок може виявитися неповним.
Наприклад, за кількості елементів n=12 маємо таку піраміду індексів:
1
2 3
4 5 6 7
8 9 10 11 12
Елементи цієї піраміди будемо називати вузлами. Між вузлами проведемо стрілки: від 1 – до 2 та 3, від 2 – до 4 та 5, від 3 – до 6 та 7 тощо, тобто від кожного вузла k до 2k та 2k+1, де k<n div 2 (рис.17.1). За парного n від вузла (n div 2) проводиться стрілка лише до вузла n. Вузли 2k та 2k+1 називаються синами вузла k, який називається їхнім батьком. Вузол 1 називається вершиною піраміди. Кожний вузол також можна вважати вершиною піраміди, складеної ним, його синами, їх синами тощо.
Наприклад, вузол 2 є вершиною піраміди, складеної з 2, 4, 5, 8, 9, 10, 11, вузол 3 – піраміди з 3, 6, 7, 12. Піраміду можна розглядати як дерево, гілки якого – стрілки від батьків до синів. Вершина піраміди називається коренем дерева. Припустимо тепер, що значення елементів масиву розташовано так, що значення кожного елемента-батька не менше значень його синів:
A[1] ³ A[2] та A[1] ³ A[3], A[2] ³ A[4] та A[2] ³ A[5] тощо.
Отже, за кожного k=1, 2, … , n div 2 A[k] ³ A[2*k] та A[k] ³ A[2*k+1] (за парного n елемент A[n div 2] має лише одного сина A[n]).
Наприклад,
30
12 30
12 5 29 2
11 10 3 2 28 27
Цій піраміді відповідає послідовне розташування <30, 12, 30, 12, 5, 29, 2, 11, 10, 3, 2, 28, 27>. Очевидно, що кожний елемент має значення, найбільше в тій піраміді, де він є вершиною. Наприклад, A[2] має значення, найбільше серед елементів із індексами 2, 4, 5, 8, 9, 10, 11. Зокрема, A[1] має значення, найбільше серед усіх елементів.
Якщо поміняти місцями значення A[1] і A[n], то елемент A[n] матиме найбільше значення. Про нього "можна забути" та зосередитися на сортуванні A[1], A[2], . , A[n-1]. Зрозуміло, що умова A[1]³ A[2], A[1]³ A[3] після обміну може виявитися порушеною. Для її відновлення треба обміняти місцями значення A[1] та того з A[2], A[3], чиє значення максимальне.
Нехай це буде A[3]. В останньому прикладі після обміну значень A[1] і A[12] на вершині піраміди значення 27, і 27<30, тобто A[1]<A[3]. Після обміну їх значень умова може порушитися в піраміді з вершиною A[3]. Відновимо цю умову так само, як і для вершини A[1], опустившися при цьому до вузла A[6] чи A[7]. І так далі. Після відновлення умови можна буде обміняти значення першого елемента з передостаннім, "забути" про нього, знову відновити умову, знову загнати перше значення в кінець тощо.
Нехай процедура bld(A, n) задає початкову перестановку значень масиву таким чином, що виконується умова , а процедура reorg(A, i, k) – її відновлення у частині масиву A[i], … , A[k]. Тоді за дії означень сортування задається процедурою Treesort: procedure Treesort ( var a : ArT; n : Indx ); var j : Indx; begin bld (A, n); for j := n downto 3 do begin swap (A[1], A[j]); reorg (A, 1, j-1) end end Властивість відновлюється в частині масиву A[1], … , A[n-1] таким чином. Обмінюються значення A[1] та того з A[2] або A[3] (позначимо його A[k]), чиє значення максимальне. У результаті властивість може порушитися в частині масиву A[k], … , A[n-1]. У ній відновлення відбувається так само, як і серед A[1], … , A[n-1]. Опишемо відновлення частини масиву A[i], … , A[j] у загальному випадку значень i, j.
Нехай у частині масиву A[i], … , A[j], де 2*i+1£ j, треба відновити властивість , можливо, порушену з початку: A[i]<max{A[2*i], A[2*i+1]}. За умови A[2*i]>A[2*i+1] покладемо k=2*i, у противному разі – k=2*i+1. Обміняємо значення A[i] та A[k]; після цього, якщо необхідно, властивість відновлюється в частині масиву A[k], … , A[j]. Коли 2*i=j, то лише порівнюються й, можливо, обмінюються значеннями A[i] та A[j], причому k=j. Коли 2*i>j, то властивість не може бути порушеною в частині масиву A[i], … , A[j]. За дії означень відновлення задається рекурсивною процедурою reorg: procedure reorg ( var A : ArT; i, j : Indx ); var k : Indx; begin if 2*i = j then if A[i] < A[j] then swap ( A[i], A[j] ); if 2*i < j then begin if A[2*i] > A[2*i+1] then k := 2*i else k := 2*i + 1; if A[i] < A[k] then begin swap ( A[i], A[k] ); reorg ( A, k, j ) end end end
Після виконання виклику reorg( A, i, j ) за будь-якого i<jdiv2 елемент A[i] має максимальне значення серед A[i], A[2*i], A[2*i+1]. Цим можна скористатися для побудови початкового масиву з властивістю : спочатку "відновлюється" частина масиву A[ndiv2], … , A[n], потім частина A[ndiv2-1], … , A[n] тощо. Звідси процедура bld: procedure bld (var A : ArT; n : Indx ); var i : Indx; begin for i := n div 2 downto 1 do reorg ( A, i, n ) end Оцінимо складність алгоритму.
За наведеними процедурами очевидно, що складність алгоритму прямо пропорційна загальній кількості викликів процедури reorg. При виконанні процедури bld процедура reorg викликається ndiv2 разів, а при виконанні циклу for процедури Treesort – ще n-2 рази.
Отже, загальна кількість викликів процедури reorg з інших процедур є O(n). Кількість елементарних дій при виконанні операторів її тіла оцінюється сталою, тобто O(1). У кожному рекурсивному виклику процедури reorg значення її другого параметра не менше ніж подвоюється, тому кожний виклик reorg з інших процедур породжує не більше O(logn) рекурсивних викликів. Звідси випливає, що загальна кількість елементарних дій є O(nlogn).
2.8. Швидке сортування
Ідея швидкого сортування така. Певним чином вибирається значення v. Значення елементів масиву A обмінюються так, що елементи на його початку мають менші від v значення, а від деякого місця k значення елементів більші або рівні v. Це значення називається відокремлюючим; воно знаходиться на своєму місці, якщо A[k]=v. Після розміщення відокремлюючого значення на потрібному місці достатньо окремо відсортувати частини масиву від A[1] до A[k-1] та від A[k+1] до кінця.
Сортування частини масиву A[lo] … A[hi] з відокремлюючим значенням A[lo] задається такою процедурою: procedure quicksort ( A : ArT; lo, hi : Indx ) ; var k, j : Indx; v : T; label 1; begin if lo >= hi then goto 1; if (lo = hi - 1) and (A[lo] > A[hi]) then begin swap ( A[lo], A[hi] ); goto 1 end; k := lo + 1; j := hi; v := A[lo]; {?!} while ( k < j ) do if A[k] < v then k := k + 1 else begin if A[j] < v then swap ( A[k], A[j] ); j := j - 1 end; { k = j } if A[k] >= v then k := k - 1; { A[k] є останнім від початку елементом, } { значення якого менше v } swap ( A[lo], A[k] ); { A[k] = v } quicksort ( A , lo, k - 1 ); quicksort ( A , k + 1, hi ); 1: end
Якщо за виконання кожного виклику після циклу while значення змінної k приблизно рівне (lo+hi)/2, то складність швидкого сортування масиву з n елементів можна оцінити як O(nlogn). Середня кількість порівнянь елементів усіх можливих числових послідовностей довжини n також має оцінку O(nlogn); доведення є, наприклад, у книзі [Аху]. Емпіричні дослідження свідчать, що швидке сортування вимагає в середньому елементарних дій приблизно вдвічі менше, ніж сортування деревом, і вчетверо менше, ніж сортування злиттям. Але якщо початковий масив близький до відсортованого, то його сортування за наведеним алгоритмом вимагає вже O(n2) порівнянь. У такому випадку відокремлюючим елементом не можна вибирати значення A[lo].
Існує багато способів вибору іншого відокремлюючого значення.
Наприклад, можна вибрати значення елемента з випадковим номером серед номерів lo, … , hi, або середнє із значень A[lo], A[hi], та A[(lo+hi)div2]. У такому разі перед оператором процедури v := A[lo]; {?!} треба задати обмін значень A[lo] та відповідного елемента, чиє значення вибирається відокремлюючим. За масивом із N рядків визначається додатковий індексовий масив: попаpно pізні значення його елементів належать діапазону 1 N і є індексами в масиві рядків.
3. ПОРЯДОК ВИКОНАННЯ РОБОТИ
1. При підготовці до лабораторної роботи, необхідно засвоїти теоретичний матеріал по темі і підготуватись до контрольного опитування по розумінню питань даної тематики.
2. Згідно з індивідуальним завданням розробити алгоритм розв’язання задачі.
3. Підготувати програмну реалізацію розробленого алгоритму. Засобами вбудованого тексто-вого редактора інтегрованого середовища набрати текст підготовленої програми. Відкомпілювати, налагодити та виконати програму.
4. Протестувати програму згідно зі складеною системою тестів і, при потребі, відкоректувати текст програми. Проаналізувати отримані результати.
5. Написати контрольне опитування по темі.
6. Оформити звіт по роботі.
Без підготовкі до лабораторної роботи (програмної реалізації розробленого алгоритму) студент до роботи не допускається.
4. ЗАВДАННЯ НА ЛАБОРАТОРНУ РОБОТУ
4.1. Вибір варіанта індивідуального завдання
Введемо позначення: DN – день народження
MN – місяць народження
А1 – ASCII-код першої літери прізвища – велика латинська літера
№ варіанта = ( DN + MN + А1 ) % 25+ 1
4.2. Варіанти завдань
Загальна частина:
Задати послідовність цілих чисел довільної довжини і представити її у пам’яті комп’ютера у вигляді масиву або лінійного зв’язаного списку. Програмно реалізувати один із вказаних нижче методів сортування згідно з варіантом. Під час виконання програми обов’язково виводити на екран монітора всі проміжні кроки процесу сортування.
Провести дослідження побудованого методу за схемою:
1) Обґрунтувати вибір структури даних, в якій має зберігатись інформація (масив чи список; якщо список, то однозв’язаний чи двозв’язаний).
2) Намалювати схему алгоритму на прикладі послідовності з десяти (або більше при необхідності) цілих чисел, показуючи всі проміжні кроки процесу сортування.
3) Дослідити метод cортування на стійкість.
4) Дослідити метод cортування на економність використання пам’яті.
5) Дослідити метод на можливу специфіку вхідної послідовності (чи може послідовність містити елементи з однаковими ключами, чи має бути вхідна послідовність частково відсортована, чи мають елементи послідовності знаходитись у певному діапазоні і т.п.).
6) Дослідити ефективність методу. Для цього програмно визначити значення кількості порівнянь (С) і кількості перестановок (М) в найкращому () і в найгіршому () випадках. Середні значення кількості порівнянь () і кількості перестановок () визначити, як середнє арифметичне для кожної величини від великої кількості спроб сортування випадкових послідовностей. Побудувати графіки залежностей , , , від кількості елементів n, де n змінюється від 1 до 100 000.
7) Визначити до якого класу (підкласу) належить досліджуваний метод. Використовуючи методику аналізу основних алгоритмічних конструкцій та визначення набору "елементарних" операцій, обчислити складність методу, що характеризується функцією трудомісткості.
Індивідуальні завдання:
5. ВИМОГИ ДО ОФОРМЛЕННЯ ЗВІТУ
I. Оформити титульну сторінку звіту стандартного зразка, на якій обов’язково вказати номер лабораторної роботи, її назву та вибір номера варіанта.
II. В звіті мають бути відображені наступні пункти:
2.1. Загальна частина
2.2. Індивідуальне завдання
1) Програмні дослідження.
а) Кількість порівнянь в найкращому, в найгіршому та в середньому випадках.
б) Кількість перестановок в найкращому, в найгіршому та в середньому випадках.
2) Чисельні дослідження.
а) Визначення класу (підкласу) алгоритму по його трудомісткості.
б) Обчислення функції трудомісткості алгоритму.
3) Асимптотичні дослідження.
а) Знаходження часової складності алгоритму ( за нотацією Ландау).
б) Визначення назви асимптотичного класу ефективності алгоритму.
Висновки.
Додатки (тексти програм з коментарями).
6. КОНТРОЛЬНІ ЗАВДАННЯ
|
1. |
Промоделюйте вручну, показуючи всі проміжні результати, роботу алгоритму сортування методом простої вставки наступної послідовності: 55 , 3 , 20 , 88 , 1 , 66 , 9 . |
|
2. |
Промоделювати вручну, показуючи всі проміжні кроки, роботу алгоритму швидкого сортування наступної послідовності: 15 , 23 , 47 , 54 , 10 , 5 , 19 . |
|
3. |
Дослідити на стійкість метод cортування простим вибором, програмна реалізація якого має такий вигляд: procedure SelectionSort(var a:VectType); var i,j,k : integer; min : KeyType; Begin for i:=1 to n-1 do begin k:=i; min:=a[i]; for j:=i+1 to n do if a[j] < = min then begin k:=j; min:=a[k]; end; a[k]:=a[i]; a[i]:=min; end; End; |
СПИСОК ЛІТЕРАТУРИ