6.7. Операції реорганізації масивів і визначення їх параметрів

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

Характеристикою масиву є його розмір - загальна кількість елементів у масиві. Інша характеристика масиву - його розмірність, оскільки масиви можуть бути як одновимір-ні, так і багатовимірні, а також розміри в кожному з вимірів.

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

Алгоритм сортування - це алгоритм для впорядкування елементів масиву. До алго­ритмів сортування належать такі: сортування за методом бульбашки, сортування мето­дом вставок, сортування злиттям, цифрове сортування, порозрядне сортування, двій­кове дерево сортування, блокове сортування, сортування методом вибору, сортування методом Шелла та інші.

232

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

При виконанні сортування за методом бульбашки максимальні елементи ніби буль­башки спливають до початку масиву.

При сортуванні вставкою впорядкування елементів масиву здійснюється шляхом порівняння елемента масиву з усіма іншими та його розміщення відповідно до його зна­чення.

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

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

Завдання пошуку максимуму або мінімуму вирішується шляхом розбиття масиву на підмасиви, аж до масиву із двох елементів, та рекурсивного вибору з них більшого або меншого. На рис. 6.28 приведено приклад послідовності дій при знаходженні максимуму або мінімуму для масиву із 8 чисел.

Задачі зсуву елементів масиву по заданій координаті, транспонування масиву та ви­значення параметрів масиву, а також операція стиску (розширення) масиву по заданій координаті, вирішуються шляхом роботи з адресами його елементів у пам'яті.