8

8. ПОШУК ТА СОРТУВАННЯ

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

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

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

8.1. Пошук

Пошук є однією знайбільш поширених у програмуванні дій. У подальшому розгляді ми будемо виходити з принципового допущення, що група даних, в якій треба шукати заданий елемент, є фіксованою. Будемо вважати, що множина з n елементів задана у вигляді масиву a типу t, де масив a та тип t описано наступним чином:

тип t = масив [1..n] із t;

змін a: t;

де для типу елементів масиву t визначені стандартні відношення: {=, <>, <, >, >=, <=}.

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

функція LinSearch (a: t; x: t): нат це

змін i: нат; b: бул;

поч

i <- 0; b <- Хиб;

поки (i<n) & Øb повт

i <- i+1;

b <- a[i] = x

кц;

якщо b то LinSearch <- i

інакше LinSearch <- 0 кр

кф;

Функція LinSearch повертає значення номера елемента масива, який дорівнює x, якщо такий елемент знайдено, та 0, якщо такого елемента не існує. Якщо оцінювати необхідну кількість кроків для отримання результату, то в загальному випадку вона пропорційна значенню n, що ми будемо позначати O(n).

Виникає питання: чи можна знайти у масиві потрібний елемент за меншу кількість кроків? Відповідь є ствердною в тому випадку, коли елементи масива впорядковані. Без обмеження загальності можна вважати, що елементи впорядковані за зростанням, тобто a[1] <= a[2] <= ... <= a[n]. Ідея методу пошуку, який називають бінарним, полягає у наступному:

На кожному кроці алгоритма шукаємо x серед елементів масиву від нижньої до верхньої границі. Спочатку нижня границя індексів – 1, а верхня – n.

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

Отримуємо алгоритм бінарного пошуку:

функція BinSearch (a: t; x: t): нат це

змін l, r, m: нат; b: бул;

поч

l <- 1; r <- n; b <- Хиб;

поки (l<=r) & Øb повт

m <- (l+r) div 2; {вибираємо середній елемент}

якщо a[m]=x то b < Іст

інякщо a[m]<x то l <- m+1 {змінюємо нижню границю}

інакше r <- m-1 кр {змінюємо верхню границю}

кц;

якщо b то BinSearch <- m

інакше BinSearch <- 0 кр

кф;

У цьому алгоритмі l – індекс нижньої границі, r – індекс верхньої границі. Оцінимо кільксть кроків, яка необхідна для знайдення потрібного елемента. Оскільки на кожному кроці кілкість елементів масиву, серед яких шукаємо x, зменшується у 2 рази, то загальна кількість кроків буде не більше log₂n, отже буде мати порядок O(log₂n).

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

функція BinSearch2 (a: t; x: t): нат це

змін l, r, m: нат;

поч

l <- 1; r <- n;

поки l<r повт

m <- (l+r) div 2;

якщо a[m]<x то l <- m+1

інакше r <- m кр

кц;

якщо a[l]=x то BinSearch2 <- l

інакше BinSearch2 <- 0 кр

кф;

Звичайно, функція log₂n зростає набагато повільніше за n, і якщо пошук треба здійснювати часто, то бінарний пошук є набагато більш ефективним, ніж лінійний. Але для бінарного пошуку елементи масиву треба спочатку відсортувати. Отже, перейдемо до методів сортування.

8.2. Сортування

Серед розглянутих раніше структур даних необхідність у сортуванні виникає для масивів та файлів. Розглянемо методи сортування для цих структур.

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

Нехай a₁, a₂, ..., a_n – елементи деякої структури даних. Позначимо k(a_i) – ключ елемента a_i, i=1, 2, ..., n. Під сортуванням елементів a₁, a₂, ..., a_n розуміють їх переставлення у таку послідовність a_i₁, a_i₂, ..., a_in, що їх ключі задовольняють відношенням:

k(a_i1)<=k(a_i2)<=...<=k(a_in)

Часто буває так, що елементи a_i та a_j мають однакове значення ключа. Тоді метод сортування називається стійким, якщо в процесі переставлення відносне розташування елементів з рівними ключами не змінюється, тобто для всіх елементів a_i та a_j таких, що k(a_i)=k(a_j) та i<j, у відсортованій послідовності a_i передує a_j.

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

Методи сортування масивів класифікують за часом їх роботи, який залежить від числа необхідних порівнянь ключів та числа пересилок елементів. У найбільш простих методах сортування потрібно порядку O(n²) операцій, а у найкращих – порядку O(n·log₂n).

Як і для пошуку, будемо вважати, що маємо тип даних масив та змінну цього типу:

тип t = масив [1..n] із t;

змін a: t;

де для типу елементів масиву t визначені стандартні відношення: {=, <>, <, >, >=, <=}.

Покладемо тепер k(a[i])=a[i], i=1, 2, ..., n. Для демонстрації виконання сортування будемо вважати, що n=8, а масив складається з елементів (23,55,47,35,10,90,84,30).

8.2.1.1. Сортування включенням

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

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

для i <- 2 до n повт

x <- a[i];

вставити x на відповідне місце серед a[1] ... a[i]

кц

Дія “вставити x на відповідне місце серед a[1] ... a[i]” може виконуватись по-різному. Для сортування прямим включенням вона полягає у послідовному порівнянні x з елементами масиву a[j] до виконання умови x>=a[j] та зсуві елементів масиву на одну позицію праворуч. Остаточно отримуємо:

процедура StraightInsertion (мод a: t) це

змін i, j: нат; x: t; b: бул;

поч

для i <- 2 до n повт

x <- a[i]; j <- i; b <- Хиб;

поки (j > 1) & Øb повт

b <- x>=a[j-1];

якщо Øb то a[j] <- a[j-1]; j <- j-1 кр

кц;

a[j] <- x

кц

кп

Даний алгоритм є прикладом стійкого сортування.

Якщо розглянути необхідну кількість дій, то вона має порядок O(n²). Дійсно, зовнішній цикл виконується (n-1) раз, а на кожному його кроці внутрішній цикл виконується, в середньому, n div 2 раз.

Розглянемо тепер порядок сортування масива по кроках:

23 55 47 35 10 90 84 30

i=2 23 55 47 35 10 90 84 30

i=3 23 47 55 35 10 90 84 30

i=4 23 35 47 55 10 90 84 30

i=5 10 23 35 47 55 90 84 30

i=6 10 23 35 47 55 90 84 30

i=7 10 23 35 47 55 84 90 30

i=8 10 23 30 35 47 55 84 90

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

процедура BinaryInsertion (мод a: t) це

змін i, j, l, r, m: нат; x: t;

поч

для i <- 2 до n повт

x <- a[i]; l <- 1; r <- i;

поки l<r повт

m <- (l+r) div 2;

якщо a[m]<=x то l <- m+1

інакше r <- m кр

кц;

для j <- i до r+1 через -1 повт

a[j] <- a[j-1]

кц;

a[r] <- x

кц

кп

Цей алгоритм має менше число порівнянь (O(n·log₂n)), але кількість перестановок залищається незмінною. На відміну від сортування прямим включенням, сортування бінарним включенням не є стійким. Послідовність значень елементів масиву по кроках у нашому прикладі буде співпадати з отриманою за методом сортування прямим включенням через те, що, всі значення елементів масиву (які є також ключами) різні, отже нестійкість алгоритму не проявляється.

8.2.1.2. Сортування вибором

При сортуванні вибором на кожному кроці, для i від 1 до (n-1), знаходимо найменший елемент серед a[i], a[i+1], ..., a[n] з номером k, після чого міняемо місцями елементи a[i] та a[k].

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

для i <- 1 до n-1 повт

k <- індекс мінімального елемента серед a[i] ... a[n];

обміняти значення a[i] та a[k]

кц

Визначивши дії “k <- індекс мінімального елемента серед a[i] ... a[n]” та “обміняти значення a[i] та a[k]”, отримуємо остаточний варіант алгоритма:

процедура Selection (мод a: t) це

змін i, j, k: нат; x: t;

поч

для i <- 1 до n-1 повт

k <- i;

для j <- i+1 до n повт

якщо a[j]<a[k] то k <- j кр

кц;

x <- a[i]; a[i] <- a[k]; a[k] <- x

кц

кп

Послідовність сортування масива по кроках:

23 55 47 35 10 90 84 30

i=1 10 55 47 35 23 90 84 30

i=2 10 23 47 35 55 90 84 30

i=3 10 23 30 35 55 90 84 47

i=4 10 23 30 35 55 90 84 47

i=5 10 23 30 35 47 90 84 55

i=6 10 23 30 35 47 55 84 90

i=7 10 23 30 35 47 55 84 90

Даний алгоритм також є прикладом стійкого сортування.

8.2.1.3. Обмінне сортування

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

Алгоритм для обмінного сортування має вигляд:

процедура BubbleSort (мод a: t) це

змін i, j: нат; x: t;

поч

для i <- 2 до n повт

для j <- n до i через -1 повт

якщо a[j-1]>a[j] то

x <- a[j-1]; a[j-1] <- a[j]; a[j] <- x

кр

кц;

кц

кп

Послідовність сортування масива по кроках:

23 55 47 35 10 90 84 30

i=2 10 23 55 47 35 30 90 84

i=3 10 23 30 55 47 35 84 90

i=4 10 23 30 35 55 47 84 90

i=5 10 23 30 35 47 55 84 90

i=6 10 23 30 35 47 55 84 90

i=7 10 23 30 35 47 55 84 90

i=8 10 23 30 35 47 55 84 90

Даний алгоритм сортування є стійким.

Якщо розглянути необхідну кількість дій, то вона має порядок O(n²). Зовнішній цикл виконується (n-1) раз, а на кожному його кроці внутрішній цикл виконується, в середньому, n div 2 раз. Взагалі, „бульбашкове” сортування відноситься до найменш ефективних методів. Дещо покращати його можна, чергуючи порядок проходу масива та зупиняючись, коли всі елементи відсортовано (дійсно, на кроках 6, 7 та 8 обмінного сортування наш масив вже відсортований та не змінюється). Такий модифікований алгоритм дістав назву „шейкерного” сортування.

процедура ShakerSort (мод a: t) це

змін j, k, l, r: нат; x: t;

поч

l <- 2; r <- n; k <- n;

повт

для j <- r до l через -1 повт

якщо a[j-1]>a[j] то

x <- a[j-1]; a[j-1] <- a[j]; a[j] <- x;

k <- j

кр

кц;

l <- k+1;

для j <- l до r повт

якщо a[j-1]>a[j] то

x <- a[j-1]; a[j-1] <- a[j]; a[j] <- x;

k <- j

кр

кц;

r <- k-1

до l>r

кп

Змінна k у цьому алгоритмі використовується для запам’ятовування індекса останньої пари, для якої було здійснено перестановку.

Послідовність сортування масива по кроках (значення i взато умовно та відмічає кроки зовнішнього циклу за умовою):

23 55 47 35 10 90 84 30 l=2, r=8

i=1 10 23 47 35 30 55 84 90 l=3, r=7

i=2 10 23 30 35 47 55 84 90 l=5, r=4

Хоча шейкерне сортування дещо ефективніше за “бульбашкове”, воно відноситься до простих методів сортування та вимагає порядку O(n²) операцій.

Розглянемо тепер швидкі методи сортування.

8.2.1.4. Сортування злиттям

Спочатку розглянемо задачу злиття двох впорядкованих масивів a та b з m та n елементів у впорядкований масив c з (m+n) елементів, що вміщує всі елементи масивів a та b. Цю задачу розв’язує фрагмент алгоритма:

i <- 1; j <- 1; k <- 1;

поки i<=n & j<=m повт

якщо a[i]<b[j] то

c[k] <- a[i]; i <- i+1

інакше

c[k] <- b[j]; j <- j+1

кр;

k <- k+1

кц;

поки i<=n повт

c[k] <- a[i]; i <- i+1;

k <- k+1

кц;

поки j<=m повт

c[k] <- b[j]; j <- j+1;

k <- k+1

кц;

Для кожного конкретного випадку другий або третій цикл поки не виконується жодного разу в залежності від того, який масив вичерпується раніше: a або b. Зазначимо, що злиття вимагає O(n+m) операцій.

При сортуванні злиттям на i-му кроці масив a розбивається на впорядковані підмасиви (послідовності елементів масиву, що йдуть підряд) довжини Size=2ⁱ^-1. Пари сусідніх підмасивів зливаються у впорядковані підмасиви довжини Size*2 у допоміжному масиві b. Після присвоєння a значення b та збільшення Size вдвічі злиття повторюється для підмасивів більшого розміру. Процес завершується, коли Size стає більшим або рівним n. Оскільки при i=1 підмасиви з 1 елемента впорядковані за означенням, в результаті отримуємо впорядкований масив a.

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

Size <- 1;

повт

злити пари впорядкованих підмасивів довжини Size з a у b;

a <- b;

Size <- Size*2;

до Size > n;

Для злиття пар впорядкованих підмасивів довжини Size з a у b визначимо процедуру Merge. В ній r1 – права границя індексів першого підмасиву пари, r2 – права границя індексів другого підмасиву пари. Оскільки Size приймає значення степені 2, а n може не бути кратним степені 2, довжина підмасивів останньої пари може бути менше Size.

процедура Merge(арг a: t; Size: нат; рез b: t) це

змін i, j, k, r1, r2: нат;

поч

k <- 1;

поки k<=n повт

{визначення границь підмасивів}

i <- k; r1 <- i+Size-1;

якщо r1>n то r1 <- n кр;

j <- r1+1; r2 <- j+Size-1;

якщо r2>n то r2 <- n кр;

{злиття пари підмасивів}

поки i<=r1 & j<=r2 повт

якщо a[i]<a[j] то

b[k] <- a[i]; i <- i+1

інакше

b[k] <- a[j]; j <- j+1

кр;

k <- k+1

кц;

поки i<=r1 повт

b[k] <- a[i]; i <- i+1;

k <- k+1

кц;

поки j<=r2 повт

b[k] <- a[j]; j <- j+1;

k <- k+1

кц;

кп;

Переприсвоєння a <- b можна зробити тільки один раз, якщо на непарних кроках циклу повт ... до виконувати злиття з a у b, а на парних - з b в a.

Остаточно отримуємо:

процедура MergeSort (мод a: t) це

процедура Merge(арг a: t; Size: нат; рез b: t) це

змін i, j, k, r1, r2: нат;

поч

k <- 1;

поки k<=n повт

{визначення границь підмасивів}

i <- k; r1 <- i+Size-1;

якщо r1>n то r1 <- n кр;

j <- r1+1; r2 <- j+Size-1;

якщо r2>n то r2 <- n кр;

{злиття пари підмасивів}

поки i<=r1 & j<=r2 повт

якщо a[i]<a[j] то

b[k] <- a[i]; i <- i+1

інакше

b[k] <- a[j]; j <- j+1

кр;

k <- k+1

кц;

поки i<=r1 повт

b[k] <- a[i]; i <- i+1;

k <- k+1

кц;

поки j<=r2 повт

b[k] <- a[j]; j <- j+1;

k <- k+1

кц;

кп;

змін i, Size: нат; b: t;

поч

i <- 0; Size <- 1;

повт

i <- i+1

якщо i mod 2 = 1 то Merge(a, Size, b)

інакше Merge(b, Size, a) кр;

Size <- Size*2;

до Size >= n;

якщо i mod 2 = 1 то a <- b кр

кп;

Послідовність сортування масива по кроках:

23 55 47 35 10 90 84 30

i=1 23 55 35 47 10 90 30 84

i=2 23 35 47 55 10 30 84 90

i=3 10 23 30 35 47 55 84 90

Якщо розглянути необхідну кількість дій, то вона має порядок O(n·log₂n). Дійсно, цикл повт ... до виконується log₂n раз, а на кожному його кроці виконання злиття вимагає O(n) операцій. Отже, сортування злиттям є більш швидким у порівнянні з розглянутими раніше методами, але вимагає додаткової пам’яті порядку n.

8.2.1.5. Швидке сортування

Перш ніж розглядати сортування, розглянемо процес поділу масива. Вибрають деякий елемент масива x та знаходять ліворуч від нього елемент a[i]>x, а праворуч – a[j]<x. Далі продовжують перегляд та обмін значень елементів, поки нарешті у лівій частині масива опиняться всі елементи, менші за x, а у правій частині – більші за x.

Швидке сортування полягає у застосуванні поділу спочатку до всього масива, потім до лівої та правої частин масива, потім для частин цих частин і так далі, поки кожна з частин не буде складатись тільки з одного елемента (отже буде відсортованою). Цей процес описується з використанням рекурсії підпрограмою:

процедура QuickSort (мод a: t) це

процедура Sort(арг l, r: нат) це

змін i, j: нат; x, y: t;

поч

i <- l; j <- r;

x <- a[(l+r) div 2];

цикл

поки a[i]<x повт

i <- i+1

кц;

поки a[j]>x повт

j <- j-1;

кц;

якщо i>j то вихід;

y <- a[i]; a[i] <- a[j]; a[j] <- y;

i <- i+1; j <- j-1

кц;

якщо l<j то Sort(l,j) кр;

якщо i<r то Sort(i,r) кр;

кп;

поч

Sort(1,n)

кп;

Послідовність сортування масива по кроках:

23 55 47 35 10 90 84 30

l=1 r=8 x=35 k=1 23 30 10 35 47 90 84 55

l=1 r=3 x=30 k=2 23 10 30 35 47 90 84 55

l=1 r=2 x=23 k=3 10 23 30 35 47 90 84 55

l=5 r=8 x=90 k=4 10 23 30 35 47 55 84 90

l=5 r=7 x=55 k=5 10 23 30 35 47 55 84 90

Тут k – не номер кроку, як це було для інших алгоритмів, а номер рекурсивного виклику підпрограми Sort. Виклик Sort при l=1, r=8 породжує два виклики (k=2 та k=4), які в свою чергу породжують ще два виклики (k=3 та k=5 відповідно).

Кількість дій, необхідна для сортування, має порядок O(n·log₂n). Дійсно, цикл кількість рекурсивних викликів процедури має порядок O(n), а середня довжина частини масиву при сортуванні - log₂n. Цей алгоритм, як і сортування злиттям, вимагає додаткової пам’яті порядку n за рахунок рекурсивних викликів процедури Sort.

8.2.1.6. Порівняння методів сортування масивів

З метою порівняння методів сортування масивів було виконано тестування. Для кожного методу за алгоритмом було написано підпрограму на Паскалі, після чого виконано тестування для масивів цілих чисел розміром 1024, 4096 та 16384. Результати тестування (кількість секунд з точністю до сотих) на комп’ютері Pentium-II/450 наведено у таблиці. Для кожного розміру масиву використовувалось 3 способи його побудови:

1) вже впорядкований за зростанням масив;

2) масив, впорядкований за спаданням;

3) масив з випадкових чисел.

1024 4096 16384

StraightInsertion 0.00 0.05 0.00 0.00 0.88 0.44 0.00 14.01 6.98

BinaryInsertion 0.00 0.06 0.06 0.00 0.61 0.28 0.05 9.67 4.83

Selection 0.06 0.05 0.00 0.50 0.49 0.49 8.30 8.46 8.29

BubbleSort 0.00 0.11 0.11 0.54 1.70 1.21 8.73 27.79 19.45

ShakerSort 0.00 0.11 0.05 0.00 1.71 0.99 0.00 27.30 15.82

MergeSort 0.00 0.00 0.00 0.00 0.00 0.00 0.05 0.05 0.00

QuickSort 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.05

Результати тестування показують, що дійсно найкращими є швидкі алгоритми сортування. В той же час, для вже відсортованого масиву хороші результати продемонстрували сортування включенням та шейкерне сортування, у яких кількість операцій суттєво залежить від вигляду масиву. Отже, ці прості алгоритми сортування можна використовувати для „майже” відсортованих масивів, тобто, коли до відсортованого масиву додають m елементів (m<<n).

[ЗМІСТ] [Далі] [Назад]