Урок 55-56. Алгоритми впорядкування одновимірних масивів: сортування методом обміну

Перегляньте презентацію

Практичне завдання

Увага! Під час роботи з комп'ютером дотримуйтеся правил безпеки та санітарно-гігієнічних норм.

Повторіть правила безпечної роботи за комп’ютером.

Завантажте і встановіть: Середовище програмування Лазарус (для тих, хто не завантажив)

Завдання. Складемо фрагмент проєкту для впорядкування за зростанням одновимірного масиву з 6 дійсних чисел, що вводяться з багаторядкового текстового поля, методом обміну. Впорядкований масив виводиться в інше багаторядкове поле.

    var a: array [0..5] of real; i, j: integer; x:real;
begin
    for i := 0 to 5 do a[i] := StrToFloat(Memo1.Lines[i]); // уведення значень елементів масиву з 6 дійсних чисел
    for i := 0 to 4 do // 5 разів повторюємо прохід по масиву
        for j := 0 to 4-i do // порівнюємо кожну пару сусідніх елементів від першого елементу масиву
                                        до останнього у невпорядкованій частині масиву
        if a[j]>a[j+1] then // якщо лівий з двох сусідніх елементів більше правого з них
            begin
            x := a[j]; a[j] := a[j+1]; a[j+1] := x; // обмінюємо два сусідні елементи місцями, використовуючи допоміжну змінну х
            end;
    Memo2.Clear;
    for i := 0 to 5 do Memo2.Lines.Append(floattostr(a[i])); // виведення значень упорядкованого масиву
end;

Звертаємо вашу увагу:

1. Щоб впорядкувати одновимірний масив за спаданням, потрібно при порівнянні двох сусідніх елементів обмінювати їх місцями у тому випадку, якщо лівий з них менше правого. Для цього необхідно внести певні зміни у фрагмент проєкту. 

2. Якщо в одновимірному масиві є рівні між собою елементи, то наведений алгоритм впорядкує його за неспаданням. Переконайтеся в цьому на прикладі масиву: 12; 4; 6; 2; 6; 4.

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

4. Метод обміну інколи називають методом «бульбашки». За аналогією з тим, як бульбашки в газованій воді спливають на поверхню, елементи одновимірного масиву «спливають» в його кінці: спочатку найбільший, потім найбільший серед тих, що залишилися і т.д.

5. Можна подивитися візуалізацію методу обміну, наприклад:

   • Бульбашка з угорським народним танцем, 

   • Анімований приклад алгоритму бульбашкового сортування,

   • Алгоритми сортування. Анімація.

За підручником

"Інформатика, 9 клас" (Й.Я. Ривкінд та їнші):

• • Прочитайте та розберіть теоретичний матеріал пункту 5.3 (стор. 262).

  • Виконайте вправи 3, 4 (стор. 268).

Для моніторингу засвоєння знань пройдіть тестування

• 9 кл ІНФ Сортування