Я готуюсь до курсу інформатики. Алгоритмізація та програмування

елемент підмасиву. Але оскільки підмасив увесь час змінює свій розмір, за еталон береться перший елемент саме того підмасиву, який розглядається на наступному кроці, тобто г’-ий елемент початкового масиву (і — змінна зовнішнього циклу, що вказує на початок нового підмасиву на кожному кроці).

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

Щоб оптимізувати розглянутий алгоритм, можна поєднати зсув елементів з пошуком місця вставляння. Для цього перевірки виконуються в зворотному напрямку від елемента, що потрібно вставити до місця вставки (тобто справа наліво). Оскільки елемент, що вставляється, береться першим з невпорядкованої частини масиву, то ліворуч від нього всі елементи вже впорядковані. Тому фактично необхідно порівнювати даний елемент з усіма лівішими від нього і, якщо даний елемент менший за той, з яким порівнюється, то виконується обмін елементів. Елемент наче «пливе» ліворуч від свого початкового місця розташування, і процес цей припиняється, якщо знайдений елемент не більший за даний або ми досягай початку масиву. Наприклад, даний такий масив:

12 -8 0 30 5 100

Розбиваємо його на дві частини. До першої входить єдиний впорядкований елемент {12}, а до другої—всі останні {-80305100}. Запишемо тепер процес впорядкування по етапах:

І етап: елемент, що впорядковується = - 8.

1) - 8 < 12, тому виконується обмін, тобто після першого кроку масив має вигляд:

-8 12 0 30 5 100

На цьому цикл припиняє свою роботу, тому що досягнуто початку масиву (і= 1).

IIетап: елемент, що впорядковується = 0.

1) 0 < 12, значить виконується обмін, тобто після першого кроку масивмає вигляд:

-8 0 12 30 5 100

2) 0 > - 8, значить обмін не виконується, здійснюється вихід із циклу,масив залишається без змін.

III етап: елемент, що впорядковується = 30.

1) 30 > 12, вхід до циклу не відбувається, масив залишається без змін.

IVетап: елемент, що впорядковується = 5.

1) 5 < 30, виконується обмін, після перестановки масив має вигляд:

-8 0 12 5 30 100

2) 5 < 12, здійснюється обмін, масив набуває вигляду:

-8 0 5 12 30 100

3) 5 > 0, цикл припиняє свою роботу, масив залишається без змін.

V етап: елемент, що впорядковується = 100.

1) 100 < 30, вхід до циклу не відбувається, тому що умова відразу хибна і масив залишається без змін. Програму наведено нижче:

Program Insert;

Const N=20;

Var Mas:array[1..N] of integer;

і,j,Rez:integer;

Begin

For i:=2 to N do

Begin

j:=i; {Цикл працює, доки лівий елемент більший за правий та доки не досягнуто початох масиву}

while (j>1) and (Mas[j]<Mas[j-1]) do

Begin

Rez:=Mas[j]; Mas[j]:=Mas[j-1]; Mas[j-1]:=Rez; j:=j-1;

End;

End;

End.

Домашнє завдання:

• Створити блок-схему запропонованих алгоритмів сортування («бульбашка» — 1-й та 2-й методи, метод