Метод вставок

Нехай у заданій послідовності А₁, А₂,..., А_і-1, А_і ,..., А_N перші і-і елементів вже відсортовані за зростан­ням. Знайдемо в цій частині послідов­ності місце для і-го елементу. Для цього будемо порівнювати його почергово з елементами, що стоять ліворуч від ньо­го, доки не виявиться, що для деякого А_к виконується умова А_к <= А_і.

Після цього зсунемо частину послі­довності А_к+1 А_к+2,... А_і-1 на один елемент праворуч і звільнимо таким чином (к+1) місце для елементу А_і, куди його і поставимо. Потім перейдемо до елементу А_і+1 і повторимо для нього попере­дню процедуру. Ці дії будемо повторювати, доки не дійдемо до кінця послі­довності. Реальні алгоритми починають сортування з другого елементу послідовності.

Метод вибору

Ідея його така. Знайдемо в послі­довності елемент з найменшим значен­ням і поміняємо його місцями з першим елементом. Після цього ті ж дії викона­ємо з іншими (без першого) N-1 еле­ментами послідовності, потім з N-2 елементами і т.д., поки не залишиться один елемент — останній. Він буде найбільшим.

Метод обміну («спливаючі бульбашки»).

Будь-який метод сортування пов'язаний з перестановкою елементів. Але якщо для інших методів ця дія є допоміжною, то для сортування обміном це основна характеристика процесу.

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

Сортування починається порівнянням двох останніх елементів по­слідовності: N і (N-1). Якщо А_N <A_N-1 виконуємо перестановку еле­ментів. Потім порівнюється пара елементів (N-1) і (N-2), потім (N-2) і (N-3) і т.д. до першого елементу. За цей прохід перше місце займе найменший елемент послідовності.

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

Третій прохід виконується без перших двох елементів і т.д. Остан­ній прохід виконується для двох N і (N-1) елементів, і останнє місце послідовності займе найбільший елемент.

Впорядкування послідовності чисел 4, 2, 3, 1 методом обміну пока­зано на рисунку. Числа розташовані вертикально і окреслені колом. Чим більше число, тим більше коло. Цей метод асоціюється зі спливанням бульбашок звідси і друга назва методу.

Перший прохід

Другий прохід

Третій прохід

Діалогові алгоритми.

Діалог – основна форма роботи з сучасними ЕОМ, які можуть подавати інформацію у вигляді текстів та графічних зображень.

Для написання будь-яких діалогових алгоритмів і програм необхідно знати певні правила ведення діалогу людей з ЕОМ.

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

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

Велике значення мають зручність та простота роботи з ЕОМ у діалозі. Повідомлення ЕОМ повинні бути чіткими та зрозумілими. Команди, які вводить людина, мають бути короткими.

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

У найпростіших випадках команди спілкування з діалоговими програмами складаються з окремих літер та інших символів, які є на клавіатурі ЕОМ. З цією метою в діалогових алгоритмах застосовується спеціальна функція введення окремих символів з клавіатури: с:= клавіша, яка фіксує символ, що відповідає натисненій клавіші на клавіатурі ЕОМ.

Питання для самоконтролю:

1. У чому полягає задача пошуку?

2. Як знайти найбільше яблуко у ящику?

3. Придумайте власний приклад пошуку елемента за якоюсь ознакою.

4. Запишіть алгоритм і блок-схему пошуку найменшого числа в послідовності: 45, 76, 34, 87.

5. Як ведеться пошук елемента за кількома отакими?

6. Наведіть приклад пошуку елемента за кількома параметрами.

7. Назвіть найпоширеніші алгоритми сортування.

8. Як сортуються елементи методом вставок?

9. Підсортуйте у зворотному порядку алфавіту послідовність літер D, R, F, B, A методом вставок.

10. Як сортуються елементи методом вибору?

11. Підсортуйте за алфавітом послідовність літер Ф, Г, Ж, В, Б методом вибору.

12. Як сортуються елементи методом обміну?

13. Підсортуйте за зменшенням послідовність чисел 1, 9, 7, 4, 6 методом обміну.

14. Що таке діалог?

15. Як реалізується вибір за допомогою меню в діалогових алгоритмах?

16. Як реалізується переклад за словником в ЕОМ?

17. Як організується командне керування в діалогових алгоритмах?