{Обмін елементів масиву через третю змінну}
Rez:=Mas[i] ;
Mas [і] :=Mas[i+1];
Mas[i+1]:=Rez;
Flag : =true ;
End;
k:=k+1;
Until Flag = false ;
End .
Другим методом сортування є метод прямого вибору. Один з його різновидів полягає в тому, що вибирається мінімальний елемент масиву, а потім виконується його обмін з першим елементом таблиці. Після цього перший елемент вважається впорядкованим і процес повторюється для підмасиву, що містить на один елемент менше за початковий, тобто елементи з 2-го до останнього. Процес повторюється кожен раз для масиву, зменшеного на один елемент. Закінчується він тоді, коли невпорядкований підмасив стає довжиною в один елемент. Таким чином, загальна кількість повторень дорівнює, як і в попередньому випадку, N - 1 ( N— кількість елементів масиву). Програма методу наведена нижче:
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[i]; {Зберігання еталону мінімуму}
N_Min:=i; {Зберігання номера мінімуму}
For j:=i+l to N do
If Mas[j]<Min
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 ; {Цикл працює, доки лівий елемент більший за правий та доки не досягнуто початох масиву}
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 ... ап. Після впорядкування цієї послідовності за спаданням визначити, скільки членів послідовності залишилося стояти на своїх місцях.
Розв'язання: Для того, щоб визначити, скільки чисел залишилось на своїх місцях, нам необхідно зберігати як вхідний масив, так і відсортований, тому перш за все зарезервуємо два однакових одновимірних масиви: А — вхідний масив та В — відсортований. Метод сортування масиву в даному випадку можна використовувати будь-який, наприклад, метод прямого вибору. Після виконання впорядкування проходом по обох масивах порівнюємо відповідні елементи вхідного та відсортованого масивів і, якщо вони збігаються, виконуємо підрахунок. Програма має вигляд.
Program Example_339_l;
Uses crt;
Const N = 100;
Type Masiv = array[1..N] of real;
Var A,B:Masiv; {A — масив для зберігання початкової послідовності, В — відсортований масив}
і, j,count:byte ; {i,j — змінні циклу, count — кільхість елементів, що залишились на своїх місцях)
Max : real ; {Мах — максимальний елемент підмасиву}
N _ max : byte ; { N _ max — номер максимального елементу}
Begin Randomize ;
Clrscr ;
For i:=1 to N do
Begin A[i]:=random*100-random*50; Write<A[i] :8 :2) ; End;
B := A ; {Копіювання елементів масиву А в масив В}
For i:=1 to N-1 do
Begin
Max:=B[i]; {Зберігання еталону максимуму }
N _ Max := i ; {Зберігання номера максимуму}
For j:=i+1 to N do
If B[j]>Max then
begin
Max := B [ j ]; {Перевизначення еталону}
N _ Max := j ; {Зберігання номеру еталону}
end ;
{Обмін місцями максимуму та першого елементу підмасиву}
B [ N _ Max ] :=В[і]; В[і]:=Мах;
End;
count: =0;
For і:=1 to N do
Begin
If A[i]=B[i]
then count : =count+1 ;
End;
Writeln;
Writeln( ' Кількість елементів, що не змінили місця ' , count) ;
Readkey;
End.
Завдання для самостійної роботи:
1. Дано натуральне число п та послідовність дійсних чисел а 1 , а 2 ... ап. Визначити усі числа, що входять у послідовність по 1-му разу.
2. Впорядкувати за зростанням послідовність чисел, які є кількістю студентів в групах першого курсу нашого технікуму.(22;30;25;20;28;24;34;29;26;33). Знайти середню наповнюваність груп.
3. Впорядкувати за зростанням показники температури повітря в м. Києві за минулий рік та визначити, в якому місяці найтепліше. (-12,3; -14,2; -5,1; +1,4; +19,6; +19,1; +21,1; +20,5; +18,7; +12,3; +5,2; -4,1)