Види алгоритмів сортування: вставкою, вибором, бульбашкове

Тема: Алгоритми впорядкування, пошуку та злиття.

Лекція №4

1. Види алгоритмів впорядкування: вставкою, вибором, бульбашкове.

2. Види алгоритмів пошуку: послідовний, бінарний, ітераційний.

3. Алгоритм злиття.

Час: 2 год.

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

Д. Кнут в третьому томі „Сортировка и поиск” своєї монографії „Искусство программирования для ЭВМ” наводить наступний факт: „Постачальники обчислювальних машин вважають, що в середньому більше 25% машинного часу систематично витрачається на впорядкування. В багатьох обчислювальних системах на неї (операцію впорядкування) припадає більше половини машинного часу. Виходячи з цієї статистики, можна стверджувати, що або (1) впорядкування має багато важливих галузей застосування, або (2) нею користуються без потреби, або (3) використовуються неефективні алгоритми впорядкування”. Як зазначає Д. Кнут, в кожному із вказаних тверджень є доля істини. І якщо в першому і другому випадках вплинути на ситуацію складно (сфера застосування алгоритмів, що в якості проміжного етапу використовують принцип впорядкування, об’єктивно значна, а необхідність використання того чи іншого алгоритму суб’єктивна і залежить від „людського фактору”), то виправданим буде зосередження уваги на ефективності цих алгоритмів.

Існують декілька алгоритмів впорядкування (саме такий термін для позначення процедури ранжування використовує Д. Кнут, хоча і визнає, що термін „сортування” набув більшого розповсюдження серед програмістів), зокрема: впорядкування обміном („бульбашкове” впорядкування), впорядкування вибором, впорядкування вставками, швидке впорядкування, шейкер-впорядкування, впорядкування Шелла, пірамідальне і порозрядне впорядкування.

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

Дана послідовність A, що складається із n елементів:

a[1], a[2],.., a[n]

Впорядкування передбачає розміщення цих елементів у порядку зростання (спадання) відповідно до лінійного відношення порядку, такому як „≤” („≥”) для чисел.

Звичайно, впорядкування може застосовуватися не лише до елементів з „чисельною” природою. Так, в узагальненому випадку операцію впорядкування можна сформулювати наступним чином: „Впорядкувати послідовність записів таким чином, щоб значення ключових полей цих записів складали зростаючу (спадаючу) послідовність”. Іншими словами, записи a[1], a[2],..,a[n] зі значеннями ключів k[1], k[2],.., k [n] необхідно розташувати у такому порядку, щоб k[1]≤ k[2] ≤..≤ k [n].

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

Для пояснення методики оцінки часової складності алгоритмів T(n) скористаємося так званими „простими” алгоритмами. До цієї групи відносять алгоритми впорядкування обміном, упорядкування вибором та впорядкування вставками. Для демонстрації методів удосконалення „простих” алгоритмів з метою зниження їх часової складності можна скористатися алгоритмами швидкого впорякування, шейкер-впорядкування та алгоритмом впорядкування Шелла.

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

Впорядкування обміном

Алгоритм впорядкування обміном базується на принципі порівняння пари сусідніх елементів до тих пір, доки не будуть впорядковані всі елементи.

Щоб описати основну ідею цього методу, який іноді називають методом „бульбашки”, уявимо, що елементи зберігаються в послідовності (масиві), розташованому вертикально. Елементи, що мають малі значення, є більш „легкішими” і „спливають” нагору подібно бульбашкам. При першому проході уздовж масиву (перегляд починається знизу), береться перший елемент послідовності і його значення по черзі порівнюється зі значеннями наступних елементів. Якщо зустрічається елемент з більш „важким” значенням, то ці елементи міняються місцями. При зустрічі з елементом, що має більш „легше” значення, цей елемент стає „еталоном” для порівняння, і всі наступні елементи порівнюються з цим новим, більш „легшим” елементом. У результаті елемент з найменшим значенням опиниться вгорі послідовності. Під час другого проходу уздовж масиву знаходиться елемент із другим по величині значенням, що міститься під елементом, який було знайдено при першому перегляді послідовності. Процес повторюється до тих пір, доки не будуть впорядковані всі елементи послідовності. Відзначимо, що під час другого і наступних переглядів послідовності немає необхідності переглядати елементи, знайдені за попередні перегляди, адже вони мають значення менші за значення елементів, що залишилися. Іншими словами, під час і -го перегляду не перевіряються елементи, що знаходяться на позиціях вище i.

Проілюструємо роботу алгоритму впорядкування обміном наступним прикладом, що записаний на псевдокоді.

(1) for i←n-1 step -1 until 1 do

(2) for j←1 step 1 until і do

(3) if a[j] > a[j+1] then

begin

(4) swap (a[j], a[j+1])

Дата добавления: 2014-01-07