Задача 16. Змінити алгоритм GivenItemOrd3 таким чином, щоб він шукав те місце в множині A = {a1, a2, a3} , куди потрібно вставити елемент b так, щоб вона залишилася упорядкованою: A1 = A È {b} .
Задача 17. Скласти алгоритм вибору елемента, рівного даному, в упорядкованій множині з 7-и елементів. Скільки кроків порівняння виконує Ваш алгоритм?
6.6. Задачі упорядкування
6.6.1. Упорядкування елементів
Задача 18. Дано два елементи a і b. У задачі потрібно упорядкувати їх за зростанням, тобто скласти алгоритм, що виконує «одночасно» дві дії: a := Min(a, b), b := Max(a, b).
Розв’язання оформимо у вигляді процедури
Procedure OrdPair(var a, b : Real);
Var
temp : Real;
Begin
If a > b
Then begin
temp := a;
a := b;
b := temp
end
End;
Змінна temp у цьому алгоритмі відіграє роль тимчасового сховища для значення змінної a. Перестановка двох елементів часто використовується в алгоритмах сортування. Для позначення відповідної процедури використовується ім'я Swap.
Procedure Swap(var a, b : Real);
Var
temp : Real;
Begin
temp := a;
a := b;
b := temp
End;
Процедура OrdPair тепер може бути записана більш компактно
Procedure OrdPair(var a, b : Real);
Begin
If a > b
Then Swap(a, b)
End;
Задача 19. Упорядкувати три елементи a, b, c за зростанням.
Розв’язання . Використовуємо алгоритм упорядкування двох елементів.
Procedure OrdTriple(var a, b, c : Real);
Begin
{1} OrdPair(a, b); {2} OrdPair(b, c);
{3} OrdPair(a, b);
End;
Аналіз алгоритму
Після виконання першого оператора OrdPair(a, b) a <= b. Після виконання другого оператора OrdPair(b, c) b <= c. Тому с – максимальний з трьох елементів. Ці два оператори «виштовхують» найбільший елемент у змінну с.
У результаті виконання третього оператора OrdPair(a, b) a <= b. Тому b – максимальний з елементів a, b. Цей оператор «виштовхує» другий по величині елемент у змінну b. Найменший з трьох елементів став значенням a.
Задача 20. Упорядкувати чотири елементи a1, a2, a3, a4 за зростанням.
Розв’язання. Використовуємо той самий метод, що і при упорядкуванні трьох елементів.
Procedure OrdQuadriple(var a1, a2, a3, a4 : Real);
Begin
{1} OrdPair(a1, a2); OrdPair(a2, a3); OrdPair(a3, a4);
{2} OrdPair(a1, a2); OrdPair(a2, a3);
{3} OrdPair(a1, a2);
End;
Питання для аналізу алгоритму
Що відбудеться в результаті виконання дій, записаних у першому рядку алгоритму?
Що відбудеться в результаті виконання дій, записаних у другому рядку алгоритму?
Що відбудеться в результаті виконання дії, яка записана в третьому рядку алгоритму?
Скільки порівнянь виконує алгоритм?
Скільки перестановок виконує алгоритм?
Якими повинні бути вихідні значення змінних а1, а2, а3, а4 для того, щоб кількість перестановок була максимальною?
Як змінити алгоритм для того, щоб він упорядковував 5 елементів?
6.6.2. Порівняння, перестановки і пересилання
Кількість порівнянь, які виконує алгоритм у гіршому випадку, позначається функцією С(n). Аргументом цієї функції є кількість вихідних даних, що оброблюються алгоритмом.
Так, в алгоритмі OrdQuadriple n = 4, a C(4) = 6.
В алгоритмі Middle пошуку середнього за величиною з трьох елементів n = 3. Величина С залежить від варіанта взаємного розташування даних: у варіантах 3 і 5 потрібні 2 порівняння а в інших – 3. Таким чином, С(3) = 3.
У задачах упорядкування (сортування) ефективність алгоритмів за часом оцінюється не тільки за кількістю порівнянь, але і за кількістю пересилань. Пересиланням називають дію, яка виконується оператором присвоювання a := b. Так, процедура Swap виконує три пересилання. Оскільки алгоритм упорядкування трьох елементів OrdTriple у гіршому випадку виконує три перестановки, у цьому випадку виконується 9 пересилань. Кількість пересилань, що виконує алгоритм у гіршому випадку, позначається функцією М(n). Аргументом цієї функції також є кількість вихідних даних, які оброблюються алгоритмом.
Звичайно в алгоритмах упорядкування всі дії виконуються «на місці». Це означає, що допоміжні змінні алгоритму відіграють роль тимчасового сховища (як змінна Temp в алгоритмі Swap). У цьому випадку функція М(n) може позначати кількість перестановок.
