Алгоритм задачі інвертування масиву

1. Ввести n — розмір масиву та згенерувати значення його елементів.
2. Починаючи з першого елемента і до середини масиву виконувати обмін значеннями між i-м та (n-i+1)-м елементами масиву.
3. Вивести масив.

Program EX7_7;
var mas: array [1..10] of integer;
i, n: integer;
tmp: integer;
begin
writeln('Array inversion');
writeln('enter number of elements');
readln(n);
writeln('Generated array: ');
randomize;
for I: =1 to n do
mas[i]: =random(30);
for i: =1 to n do
write(mas[i], ' ');
writeln;
for i: =1 to n div 2 do
begin
tmp: =mas[i];
mas[i]: =mas[n-i+1];
mas[n-i+1]: =tmp;
end;
writeln('Inverted array: ');
for i: =1 to n do
write(mas[i], ' ');
end.

Рис. 7.7. Результати роботи програми ех7_7. Інвертування масиву

Демонстрація прикладу

Вставка та видалення елемента, циклічний зсув елементів масиву

Під час розв'язання багатьох задач виникає необхідність вставити новий елемент на задану позицію в масиві (рис. 7.8, а), видалити заданий елемент масиву (рис. 7.8, 6) або циклічно зсунути елементи масиву на одну позицію (рис. 7.9). На рис. 7.8 та 7.9 елементи, що зсуваються, оточені жирною межею, а елементи, що видаляються або додаються, пофарбовані сірим.

Рис. 7.8. Вставка (а) та видалення (б) елементів масиву

Перед тим як вставляти до масиву новий елемент, для нього слід звільнити місце. Це можна зробити шляхом переміщення на одну позицію вправо підма-сиву, що починається з позиції, у яку буде вставлено новий елемент. Так, якщо необхідно вставити новий елемент tmp на позицію 3 в (n-1)-вимірний масив а, то підмасив а[3],..., а[n-1] треба зсунути вправо на одну позицію. Переміщення підмасиву слід здійснювати поелементно, починаючи від його правого елемента і рухаючись до лівого (якщо зсув здійснювати зліва направо, то весь підмасив буде заповнений значенням елемента а[3]).

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

writeln('enter value and position');
readln(tmp, j);
for I: =n downto j do
mas[i+1]: =mas[i];
mas[j]: =tmp;
n: =n+1;
for i: =1 to n do
write(mas[i], ' ');

Під час видалення певного елемента з масиву слід зсунути на одну позицію вліво частину масиву, що розташована праворуч від цього елемента. Так, якщо необхідно видалити третій елемент и-вимірного масиву, то підмасив а[4],..., а[n] треба зсунути вліво на одну позицію. Переміщення підмасиву слід здійснювати поелементно, починаючи від його лівого елемента і рухаючись до правого (якщо зсув здійснювати справа наліво, то весь підмасив буде заповнений значенням останнього елемента масиву). Після видалення кількість елементів масиву необхідно зменшити на одиницю. Наведемо фрагмент програми, який демонструє видалення j-гo елемента масиву.

writeln('enter position for delete');
readln(j);
for I: =j to n-1 do
mas[i]: =mas[i+1];
n: =n-1;
for i: =1 to n do
write(mas[i], ' ');

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

Рис. 7.9. Циклічний зсув елементів масиву вправо (а) та вліво (б)

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

writeln('rigth shift');
tmp: =mas[n];
for I: =n-1 downto 1 do
mas[i+1]: =mas[i];
mas[1]: =tmp;
writeln('left shift');
tmp: =mas[1];
for i: =1 to n-1 do
mas[i]: =mas[i+1];
mas[n]: =tmp;

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

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

Найбільш відомими елементарними методами сортування масиву є:

• сортування вставкою (включенням);
• сортування вибором;
• сортування обміном (бульбашкове сортування).

З удосконалених методів сортування найчастіше використовуються такі:

• швидке сортування, або метод Хоара;
• сортування включенням зі спадним приростом, або метод Шелла;
• сортування за допомогою дерева, або пірамідальне сортування;
• сортування методом злиття.

Нижче буде розглянуто всі три вищезгаданих елементарних методи сортування та два удосконалених — метод Хоара й метод злиття.