Зубенко, Омельчук - Програмування. Поглиблений курс

Розділ IV. АЛГОРИТМИ

4.1.6. ШВИДКЕ СОРТУВАННЯ

Алгоритм швидкого сортування був розроблений Ч. Хоаром. Цей алгоритм, як і попередній, базується на принципі "розділяй і володій". Його трьома етапами є: 1) вибір деякого елемента, що називається опорним; 2) поділ масиву на два підмасиви шляхом перестановки йо- го елементів так, щоб усі елементи, менші чи рівні опорному, вияви- лися ліворуч від нього, а всі елементи, більші за нього – праворуч; 3) рекурсивне впорядкування вибраних підмасивів. Базою рекурсії є підмасиви, що складаються з одного чи двох елементів. Алгоритм зав- жди завершується, оскільки за кожну ітерацію він ставить принаймні один елемент на його остаточне місце.

Приклад 4.6. Швидке сортування:

Лістинг. QSort.c

/*Швидке упорядкування за зростанням масиву a від елемента left до елемента right*/

void qSort(float a[], int left, int right)

/*масив a, left – початок ділянки, що сортується, right – кінець ділянки, що сортується*/

{

if(first<last)

{

int i=left; /*змінна для перегляду масиву ліворуч*/ int j=right; /*змінна для перегляду масиву праворуч*/ float point=a[left]; /*опорний елемент*/

while(i<j) {

/*Шукаємо ліворуч елемент, який >= опорної точки*/ while(a[i]<=point && i<right)

i++;

/*Шукаємо праворуч елемент, який <= опорної точки*/ while(a[j] >= point && j>left)

j--;

if(i<j)

swap(a[i], a[j]); /*обмін елементами*/

}

swap(a[left], a[j]); /*обмін елементами*/

/*Сортуємо лівий і правий підмасиви*/

481

ПРОГРАМУВАННЯ

qSort(a, left, j-1); qSort(a, j+1, right);

}

}

Швидке сортування вхідного масиву [4.0, 5.0, 3.0, 10.0, 1.0]:

[1.0]

[5.0]

■

Обґрунтування часових оцінок швидкого сортування можна знайти в [8, 60, 65]. Швидке сортування дає в середньому O (n log2 n ) порів-

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

цей алгоритм вимагає O(n2 ) порівнянь. Тому слід уважно обирати ме-

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

із найкращих серед алгоритмів з оцінкою O(n log2 n ). Швидке сорту-

вання, на відміну від сортування злиттям, не вимагає додаткової па- м'яті та зберігає ефективність для систем із віртуальною пам'яттю.

4.1.7. ВИБІР МЕТОДУ СОРТУВАННЯ

Для швидкого сортування даних можна скористатися стандартною функцією qsort(), що входить до стандартної бібліотеки С (див. під- розд. 3.6.6). Однак різні підходи до сортування мають різні характе- ристики. Незважаючи на те, що деякі способи сортування можуть бути в середньому кращими за інші, жоден алгоритм не є ідеальним для всіх випадків. Тому широкий набір алгоритмів сортування – ко- рисний додаток у інструментарії будь-якого програміста.

482

Розділ IV. АЛГОРИТМИ

Пояснимо коротко, чому та сама функція qsort() не забезпечує універсального розв'язку всіх завдань сортування. По-перше, функ- цію qsort() неможливо застосувати в усіх ситуаціях – вона сортує лише масиви в пам'яті, але не може сортувати дані, що зберігаються, наприклад, у зв'язаних списках. По-друге, qsort() – параметризована функція, завдяки чому вона може обробляти широкий набір типів даних, але робить це повільніше, ніж еквівалентна функція, розрахо- вана на якийсь один фіксований тип даних. Незважаючи на те, що зазвичай оптимальним є швидке сортування, воно не є кращим у всіх випадках. Наприклад, при сортуванні дуже малих списків (менше 100 елементів) додатковий обсяг роботи, пов'язаний із рекурсивними викликами швидкого сортування, може нівелювати його переваги. У таких рідких випадках один із простих методів сортування (навіть метод бульбашки) може працювати швидше. До того ж, якщо відомо, що список уже майже впорядкований або є вимоги щодо стійкості алгоритму, то якийсь інший алгоритм може виявитися прийнятнішим за швидке сортування.

*Література для CР: алгоритми сортування й пошуку – [8, 60, 65, 77, 95, 125].

Контрольні запитання та вправи

1.Сформулювати задачі пошуку й сортування кортежів.

2.Що таке ключі елементів і яка їхня роль у задачах пошуку й сортування?

3 Що таке таблиця й рядок таблиці?

4.Що таке ключове поле рядка?

5.Сформулювати алгоритм послідовного пошуку.

6.Що таке бінарний пошук?

7.Порівняти часову складність послідовного й бінарного пошуків.

8.Що таке бульбашкове сортування?

9.Що таке сортування вставленням?

10.Порівняти часову складність бульбашкового сортування й сортування вставленням.

11.Що таке злиття двох послідовностей?

12.Сформулювати алгоритм сортування злиттям. Яка його ча- сова складність?

13.Сформулювати алгоритм швидкого сортування.

14.Які переваги й недоліки застосування функція qsort()?

15.Порівняти часову складність сортування злиттям і швидкого сортування.

483

ПРОГРАМУВАННЯ

16. Дано послідовність цілих чисел a1,..,an . Упорядкувати її за зростанням удосконаленим методом вставлення. Перегля- дати послідовно a2,..,an і кожний новий елемент вставляти на відповідне місце в уже впорядковану сукупність a1,..,ai .

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

17. Дано послідовність цілих чисел a1,..,an . Упорядкувати за

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

18.Замінимо лінійний порядок на ключах частковим. Як відсо- ртувати масив із такими ключами?

19.Дано послідовність a1,..,an : 1) цілих чисел; 2) раціональних

4.2. Лінійна алгебра

¾Прямий алгоритм множення матриць

¾Алгоритм Винограда для множення матриць

¾Алгоритм Штрассена для множення матриць

¾Системи лінійних рівнянь. Метод Гаусса – Жордана

¾Розріджені матриці

Ключові слова: додавання й віднімання матриць, прямий алгоритм множення матриць, алгоритм Винограда, алгоритм Штрассена, метод Гаусса – Жордана, розрі-

джена матриця, спискове й повне рядкове зображення RR(C) розрідженої матриці.

Матриці означені в підрозд. 1.4.4 як кортежі фіксованої довжини з однотипними елементами – теж кортежами фіксованої довжини. Ма- триці й операції з ними застосовуються в різноманітних задачах, та- ких як моделювання фізичних об'єктів, наукові та економічні розра-

484

Розділ IV. АЛГОРИТМИ

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

Найпростіший спосіб подання матриці – у вигляді двовимірного масиву. Числа розміщуються в матриці в рядках і стовпчиках:

int matrInt[4] [3]; float matrFloat [4] [3];

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

Приклад 4.7. Додавання й віднімання матриць:

Лістинг.

/*додавання й віднімання матриць*/ #define Size1 5

#define Size2 5

… … …

double MatrA[Size1][Size2]; double MatrB[Size1][Size2];

double MatrSum[Size1][Size2]; /*сума матриць*/

double MatrRemainder[Size1][Size2]; /*різниця матриць*/ int i,j,k;

for (i=0; i<Size1; i++){

for (j=0; j<Size2; j++){

MatrSum[i][j] = MatrA[i][j]+ MatrB[i][j]; MatrRemainder[i][j] = MatrA[i][j]- MatrB[i][j];

}

}

■

4.2.1. ПРЯМИЙ АЛГОРИТМ МНОЖЕННЯ МАТРИЦЬ

Якщо кількість стовпчиків у першій матриці збігається з кількістю рядків у другій, то ці матриці можна перемножити (див. підрозд. 1.4.4).

Прямий алгоритм множення матриць реалізується трьома вкладе- ними циклами.

485

ПРОГРАМУВАННЯ

Приклад 4.8. Прямий алгоритм множення матриць:

Лістинг.

/*множення матриць*/ #define count1 5 #define count2 5 #define count3 5

double a[count1][count2]; double b[count2][count3];

double matrMult [count1][count3];

…

int i,j,k;

for(int i=0; i<count1; i++){ for(int j=0; j<count3; j++){

matrMult[i][j]=0;

for(int k=0; k<count2; k++){ matrMult[i][j]+=a[i][k]*b[k][j];

}

}

}

Зазначимо, що присвоювання matrMult[i][j]+=a[i][k]*b[k][j]

реалізується ефективніше, ніж звичайне

MatrMult[i][j]=MatrMult[i][j]+ a[i][k]*b[k][j].

Часова складність (за кількістю операцій) даного алгоритму стано-

вить count1×count2×count3 ■

При множенні квадратних матриць розміром n ×n кількість вико- наних операцій має порядок O(n3 )= O(nlog2 8 ).

Перевагою запропонованого алгоритму є простота, але він повіль- ний. Розглянемо ефективніші алгоритми.

4.2.2. АЛГОРИТМ ВИНОГРАДА ДЛЯ МНОЖЕННЯ МАТРИЦЬ

Кожен елемент добутку двох матриць є скалярним добутком відпові- дних рядка і стовпчика. Розглянемо скалярний добуток двох векторів –

V = (v0,v1,v2,v3 ) та W = (w0,w1,w2,w3 ): V oW = v0w0 +v1w1 + +v2w2 +v3w3 = (v0 + w1 )(v1 + w0 )+ (v2 + w3 )(v3 + w2 )− v0v1 −v2v3 − w0w1 −

−w2w3 . Праву частину останнього виразу можна попередньо вирахува- ти й запам'ятати для кожного рядка першої матриці й кожного стовп-

486

Розділ IV. АЛГОРИТМИ

чика другої. Це дозволяє виконувати для кожного елемента лише перші два множення та п'ять додавань, а також наступні два додавання.

Ш. Виноград для множення матриці G розміром n ×m на матрицю H розміром m ×k запропонував алгоритм, названий його іменем. Ре- зультат записується в матрицю R розміром n ×k :

Приклад 4.9. Алгоритм Винограда:

Лістинг.

/*множення матриць методом Винограда*/ #define count1 5

#define count2 5 #define count3 5

double a[count1][count2]; double b[count2][count3];

double matrMult [count1][count3]; //результуюча матриця double rowFactor[count1]; //сума добутків у кожному рядку

double columnFactors[count3]; //сума добутків у кожному стовпчику //...

int i, j, k, d=(count2)/2;

//обчислення columnFactors для a void calcRowFactors()

{

for(i=0; i<count1; i++){ rowFactor[i]=a[i][0] * a[i][1];

for(j=1; j<d; j++){

rowFactor[i]+=a[i][2*j] * a[i][2*j+1];

}

}

}

//обчислення columnFactors для b void calcColumnFactors()

{

for(i=0; i<count3; i++){ columnFactors[i]=b[0][i] * b[1][i]; for(j=1; j<d; j++){

columnFactors[i]+=b[2*j][i]* b[2*j+1][i];

}

487

ПРОГРАМУВАННЯ

}

}

//обчислення матриці matrMult void mullMatr()

{

for (i=0; i<count1; i++){ for(j=0; j<count3; j++){

matrMult[i][j]=-rowFactor[i] – columnFactors[j]; for (k=0; k<d; k++){ matrMult[i][j]+=(a[i][2*k+1]+b[2*k][j])*(a[i][2*k]+

b[2*k+1][j]);

}

}

}

}

//обчислення матриці matrMult для випадку непарної розмірності void mullMatr_1()

{

if ((2 *((count2)/2))!=count2) { for(i=0; i<count1; i++){

for(j=0; j<count3; j++){ matrMult[i][j]+=a[i][count2-1] * b[count2-1][j];

}

}

}

}

int main()

{

//... ініціалізація матриць a та b

calcRowFactors();

calcColumnFactors();

mullMatr(); mullMatr_1(); // ...

system("PAUSE"); return 0;

}

■

Увага! Дана програма діє некоректно при count2=1 ►

Верхня оцінка часової складності алгоритму Винограда для квад- ратних матриць – O(n2.375477 ).

488

Розділ IV. АЛГОРИТМИ

4.2.3. АЛГОРИТМ ШТРАССЕНА ДЛЯ МНОЖЕННЯ МАТРИЦЬ

Розглянемо відкритий Штрассеном рекурсивний алгоритм, що множить дві (n ×n )-матриці за час O (nlog2 7 )= O (n2.81 ).

Алгоритм Штрассена діє за принципом "розділяй і володій". Він працює з квадратними матрицями, розмір яких є степенем двійки, але настільки ефективний, що іноді доцільно розширити матриці до квадратних (додаванням нульових рядків чи стовпчиків), і при цьому він все одно дає виграш.

Нехай потрібно обчислити добуток двох матриць (n ×n ): C = AB . Нехай n є точним степенем двійки, тоді розділимо кожну з матриць A , B та C на 4 блоки розміром (n /2×n /2 ). Перепишемо рівняння

C = AB таким чином:

де r = ae +bf , s = ag +bh , t = ce + df , u = cg + dh .

Тут відбувається вісім множень матриць розміром n /2, тому в та- кому вигляді алгоритм, як і послідовний алгоритм, працює за час

O(nlog2 8 ). Алгоритм Штрассена пропонує схему, за якої в рекурсив-

ному алгоритмі можна обійтися лише сімома множеннями матриць розміром n /2, тим самим скоротивши час до O(nlog2 7 )= O(n2.81 ).

Алгоритм Штрассена множить дві матриці (n ×n ) A та B таким чином:

x1 = ag −ah ; x2 = ah +bh ; x3 = ce + de ; x4 = df −de ;

x5 = ae +ah + de + dh ; x6 = bf +bh −df −dh ; x7 = ae +ag −ce −cg .

r= x5 + x4 − x2 + x6 = ae + de −d +bf ;

s= x1 + x2 = ag +bh ;

t= x3 + x4 = ce + df ;

u= x5 + x1 − x3 − x7 = cg + dh .

489

ПРОГРАМУВАННЯ

Отже, при множенні двох матриць 2×2 алгоритм виконує 7 мно- жень і 18 додавань. На практиці алгоритм Штрассена застосовується порівняно рідко через суттєву величину константи, що міститься в асимптотичному виразі для часу його роботи. Його застосування ви- правдане для великих матриць (від 45 × 45 ) з малою кількістю нулів.

4.2.4. СИСТЕМИ ЛІНІЙНИХ РІВНЯНЬ. МЕТОД ГАУССА – ЖОРДАНА

Системи лінійних рівнянь застосовуються в різноманітних задачах. Таку систему можна записати у вигляді матричного рівняння.

Система лінійних рівнянь із n рівнянь із n невідомими має вигляд

a0,0 x0 + a0,1x1 + a0,2 x2 +…+ a0,n −1xn −1 =b0 a1,0 x0 + a1,1x1 + a1,2 x2 +…+ a1,n −1xn −1 =b1

K

K

K

an −1,0 x0 + an −1,1x1 + an −1,2 x2 +…+ an −1,n −1xn −1 =bn −1 .

Розглянемо метод Гаусса – Жордана для розв'язання систем ліній- них рівнянь.

Систему лінійних рівнянь можна зобразити у вигляді матриці роз- міром n +1×n :

Алгоритм Гаусса – Жордана:

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

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

3.Усі елементи першого рядка ділимо на верхній елемент вибрано- го стовпчика.

4.Від усіх рядків, окрім першого, віднімаємо перший рядок, по- множений на перший елемент кожного рядка, щоб отримати в пер- шій позиції кожного з решти рядків нулі.

490