 |
|
Рекурсивне сортування масиву методом вибору
Питання для вивчення:
1. Сортування методом простого обміну.
2. Сортування масиву за допомогою рекурсії.
3. Сортування методом злиття.
4. Рекурсивне сортування злиттям
Сортування методом простого обміну. Рекурсивне сортування. Принцип методу: Зліва направо по черзі порівнюються два сусідні елементи, і якщо їх взаємне розташування не відповідає заданій умові впорядкованості, то вони міняються місцями. Далі беруться два наступних сусідніх елемента і так далі до кінця масиву. Після одного такого проходу на останній n-ій позиції масиву буде стояти максимальний (або мінімальний) елемент ("сплив" перший "бульбашка"). Оскільки максимальний (або мінімальний) елемент вже стоїть на своїй останній позиції, то другий прохід обмінів виконується до (n-1)-го елемента. І так далі. Всього потрібно (n-1) прохід.
Процедура, що реалізовує вище розглянутий алгоритм:
Procedure Obmen (Var a: Array1);
Var
i, j, f, g: integer;
Begin
for i: = n downto 2 do
for j: = 1 to i-1 do
if a [j]> a [j +1]
then
begin
f: = a [j];
a [j]: = a [j +1];
a [j +1]: = f;
end;
End;
Сортування масиву за допомогою рекурсії. Алгоритм реалізується наступним чином: в деякому відрізку масиву вибирається центральне (серединне) значення; всі елементи з лівої частини відрізка, що перевершують центральне значення, переміщуються в праву частину, і навпаки. На наступному кроці (для якого використовуються рекурсивні виклики цієї ж процедури) алгоритм повторюється для обох частин відрізка.
Процедура, яка впорядковує по зростанню значення з масиву Massiv в діапазоні індексів Left .. Right.
Procedure QuickSort (Left, Right: integer; Massiv: Array1);
Var
i, j, x, y: integer;
Begin
i: = Left;
j: = Right;
x: = Massiv [(Left + Right) div 2]; {}
repeat
while Massiv [i]
Inc (i);
while Massiv [j]> x do
Dec (j);
if i <= j
then
begin
y: = Massiv [i];
Massiv [i]: = Massiv [j];
Massiv [j]: = y;
Inc (i);
Dec (j);
end;
until i> j;
if Left
then
QuickSort (Left, j);
if i
then
QuickSort (i, Right);
End;
Сортування методом злиття. Цілочисельний масив з розташованими по не зменшенню або по не збільшенню значеннями елементів називається впорядкованим. Використання впорядкованості дозволяє створювати ефективні алгоритми для вирішення багатьох цікавих завдань. Завдання злиття двох вхідних впорядкованих масивів А і В полягає у формуванні упорядкованого вихідного масиву С, містить усі елементи з вхідних масивів. Алгоритм злиття для упорядкованих за не зменшенню масивів. Спочатку елемент А [1] порівнюється з елементом В [1] і найменший з них записується в масив С. Якщо найменшим був А [1], то на наступному кроці порівнюються А [2] і B [1], а якщо найменшим був B [1], то будуть порівнюватися A [1] і B [2] і т.д. Якщо на черговому кроці виявиться, що з одного вхідного масиву всі елементи переписані в С, то переписується елемент з іншого масиву.
Приклад роботи алгоритму злиття. Нехай у масиві А містяться 3 елементи: {5, 13, 14}, а в масиві В - 4 елементи: {7, 9, 10, 12}.Фрагмент рішення задачі на злиття двох масивів А і В, які містять відповідно n1 та n2 елементів. Результуючий масив С буде містити n1 + n2 елементів.
. . .
i1: = 1;
i2: = 1;
for i: = 1 to n1 + n2 do
if i1> n1
then
begin
C [i]: = B [i2];
i2: = i2 +1;
end
else
if i2> n2
then
begin
C [i]: = A [i1];
i1: = i1 +1;
end
else
if A [i1] <= B [i2]
then
begin
C [i]: = A [i1];
i1: = i1 +1;
end
else
begin
C [i]: = B [i2];
i2: = i2 +1;
end;
. . .
Рекурсивне сортування злиттям. Написати програму, що містить алгоритм злиття в процедурі Sort (A, B, b1, e1, e2). Алгоритм повинен копіювати зі злиттям два впорядковані шматка з масиву А з номерами від b1 до e1 і від e1 +1 до e2 відповідно в масив В з номерами елементів від b1 до e2. Алгоритм сортування можна визначити дуже просто:
1) якщо довжина сортованого масиву 1, то нічого не робиться;
2) 2) в іншому випадку масив ділиться на дві однакові (або майже однакові) частини, до кожної частини застосовується алгоритм сортування, після чого ці впорядковані частині зливаються в один впорядкований шматок.
Процедура сортування злиттям. На вхід процедури сортування надходить неупорядкований шматок масиву А з номерами елементів від b до e, на виході - той же шматок, але впорядкований. Масив С — допоміжний.
Procedure Sort2 (Var A, C: Array1; b, e: integer);
Var
i, d: integer;
Begin
if b
then
begin
d: = (b + e) div 2;
Sort2 (A, C, b, d);
Sort2 (A, C, d +1, e);
Sort (A, C, b, d, e);
for i: = b to e do
A [i]: = C [i]
end;
End
Питання для контролю вивченого матеріалу:
1. Яким чином відбувається рекурсивне сортування масиву?
2. Які ще існують методи сортування?
3. Опрацюйте приклади. Розробіть власну програму сортування масивів.
Література:
Фаронов В.В. Турбо Паскаль 7.0. Начальный курстор. – М: Диалектика, 1997. – 487 стор. 190-193
Урок № 21
(згідно робочої навчальної програми)
Алгоритми роботи з двомірними таблицями на мові програмування Pascal
Питання для вивчення:
1. Поняття двовимірного масиву.
2. Порядок роботи з масивом.
Поняття двовимірного масиву. Двовимірний масив- це масив, де кожному елементу ставиться у відповідність два індекси.
Рисунок 1 — Схема двовимірного масиву
Для початку роботи з масивом потрібно підготувати місце в пам'яті у вигляді прямокутника, що має задану кількість рядків і стовпчиків. Для цього описати його в розділі оголошень, використовуючи зарезервоване слово Аrray, після якого в квадратних дужках вказується розмірність масиву, причому враховується, що на першому місці вказуються індекси рядків, а на другому - стовпчиків, і обов'язково тип елементів.
Порядок роботи з масивом. Опис двовимірного масиву
<Ім'я_масиву> : array[<поч_інд_рядків>..<кін_інд_рядків>,
<поч_інд_стовп>. .<кін_інд_стовп>] of <базовий_тип_елементів>;
Приклад опису:
Const n:=100;
m:=100;
Var A:array[1..n,1..m] of real;
D:array[1..10,1.100] of integer;
Зверніть увагу на те, що значень у рядках або стовпчиках масиву не обов'язково буде стільки, скільки ми оголосили, але не більше. Звертання до елементу двовимірного масиву:
Ім'я_масиву[<індекс_рядка>, <інд_стовпчика>]
Заповнення масиву:
- з клавіатури:
for і:=1 to n do
for j:=1 to m do
begin
write ('введіть А[',i,',',j,']: ');
readln (А[i,j]);
end;
- за формулою:
for і:=1 to n do
for j:=1 to m do
А[і,j]:=i*i-10 {або будь-яка формула};
- випадковим чином із проміжку [K,L]:
for і:=1 to n do
for j:=1 to m do
А[і,j]:=random(L-K)+K;
Виведення двовимірного масиву на екран
for і:=1 to n do
begin
for j:=1 to m do
write(A[i,j]:8); {виведення в рядок}
writeln; {перехід на новий рядок}
end;
Виведення в рядку необхідно обов'язково форматувати, щоб не трапилось "злипання" елементів (дивись приклад вище). Як було зазначено вище, для роботи з масивом потрібен будь-який оператор повторення. Вочевидь, що у двовимірному масиві необхідно використовувати їх два: один цикл, внутрішній, потрібен для переходу між елементами рядка (тобто, по стовпчиках), а другий, зовнішній, - для переміщення між рядками. Якщо в матриці кількість рядків і стовпчиків однакова, то таку матрицю називають квадратною (на відміну від звичайної прямокутної таблиці). Тільки в квадратних матрицях існують головна та бічна діагоналі.
Елементи, що стоять на головній діагоналі, мають індекси (1, 1), (2, 2), (3, 3), ... (і, і). ..., (n, n), тобто номер рядка дорівнює номеру стовпчика! Елементи, що стоять на бічній діагоналі, мають такі індекси (1, n), (2, n-1), (3, n-2), ..., (і, n+1-і), (n,1), тобто індекси елементів взаємозалежні за формулою j= n+1 - i.
Далі рекомендується розглянути методи розв'язку деяких типових задач по обробці двовимірних таблиць.
Питання для контролю вивченого матеріалу:
1. Що називається двовимірним масивом?
2. Особливості роботи з двовимірним масивом?
2. Який існує порядок роботи з масивами?
Література:
1. Меженний О.А.Turbo Pascal: М: Издательский дом «Вильямс», 2006. – 336 с., стор. 94 — 95
Урок № 25
(згідно робочої навчальної програми)