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

Program Selection;

Const N=20;

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

і,j, Min,N_Min:integer;

Begin

For i:=1 to N-1 do

Begin

Min:=Mas[x]; {Зберігання еталону мінімуму}

N_Min:=i; {Зберігання номера мінімуму}

For j:=i+l to N do

If Mas[j]

then begin

Min:=Mas[j]; {Перевизначекня еталону}

N_Min:=j; {Зберігання номеру еталону}

end;

{Обмін місцями мінімуму та першого елементу підмасиву}

Mas[N_Min]:=Mas[i];

Mas[i]:=Min;

End;

End.

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

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

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

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; {Цикл працює, доки лівий елемент більший за правий та доки не досягнуто початох масиву}