WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаІнформатика, Компютерні науки → Демонстрація сортування методом спливаючих бульбашок - Курсова робота

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

упорядкувати дані по певній ознаці.
Дані, наприклад, елементи масиву, можна відсортувати:
" за збільшенням - кожний наступний елемент більше попереднього: а[1]< а[2]< а[n];
" по неспаданню - кожний наступний елемент не менше попереднього: а [1] <= а[2]<=. . . а[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. Отже, для сортування необхідно порівняти попарно всі елементи і підрахувати, скільки з них менше кожного окремого елемента. Після цього всі елементи початкового масиву можна розмістити на відповідних їм місцях в новому, спеціально створеному масиві.
Сортування вставками (методом прямого включення).
Сортування вставками, так само як і сортування методом простого вибору, звичайно застосовується для масивів, що не містять повторюваних елементів. Сортування
Loading...

 
 

Цікаве