Сортування масивів

Розглянемо масив елементів а₁, а₂, а₃, …, а_n. Нехай потрібно переставити елементи цього масиву так, щоб після перестановки вони були упорядковані за неубуванням: а₁ а₂ … а_n. Ця задача називається задачею сортування чи упорядкування масиву. Для розв’язання цієї задачі можна скористатися, наприклад, такими алгоритмами:

1 Знайти елемент масиву, що має найменше значення, переставити його з першим елементом, потім проробити теж саме, почавши з другого елемента і т.д. (сортування вибором).

2 Послідовним переглядом елементів а₁, …, а_n знайти найменше i таке, що а_i> a_i+1. Поміняти a_i і а_i+1 місцями, відновити перегляд з елемента а_i+1 і т.д. Тим самим найбільший елемент пересунеться на останнє місце. Наступні перегляди починати знову спочатку, зменшуючи на одиницю кількість елементів, що переглядаються (сортування обміном або методом пухирця).

3 Переглядати послідовно а₂, а₃, …, а_n і кожен новий елемент а_i вставляти на придатне місце у вже упорядковану сукупність а₁, а₂, а₃,..., а_i-1. Це місце визначається послідовним порівнянням а_i з упорядкованими елементами а₁, а₂,..., а_i-1 (сортування вставками).

Якщо потрібно відсортувати частину масиву, що задовольняє заданим умовам, то спочатку відбирають елементи, що задовольняють заданій умові, у робочий масив, а потім його сортують.

Приклади виконання завдання лабораторної роботи

Приклад 17. Сформувати новий масив з позитивних елементів вихідного масиву x(15).

Порядок роботи:

Крок 1. Уводимо масив x(15).

Крок 2. Установлюємо вихідний індекс робочого масиву j=0.

Крок 3. Організовуємо цикл, що перебирає елементи вихідного масиву (тобто індекс i), починаючи з 1-го і кінчаючи 15-м.

Крок 4. Якщо x_i £ 0, то йдемо на крок 7.

Крок 5. Встановлюємо індекс наступного елемента робочого масиву j = j + 1.

Крок 6. Привласнюємо елементу робочого масиву значення елемента вихідного масиву y_j = x_i.

Крок 7. Якщо цикл по i не закінчився, йдемо на початок циклу, тобто на крок 3.

Крок 8. Друкуємо j елементів робочого масиву y.

Крок 9. Останов.

Приклад 18. Сформувати і вивести на друк два масиви, що містять значення й індекси від’ємних елементів вихідного масиву В(15).

Програма розв’язання даного прикладу має вид:

program pr18;

uses Crt;

const N=15;

type Mas1=array[1..N] of real;

Mas2=array[1..N] of integer;

VAR B, X: MAS1; Y: MAS2; I, J: INTEGER; P: CHAR;

BEGIN CLRSCR;

WRITELN(' УВЕДІТЬ ', N, ' ЧИСЕЛ');

FOR I: =1 TO N DO READ(B[I]);

WRITELN(' ': 20, 'ВИХІДНИЙ МАСИВ');

for i: =1 to N do write(b[i]: 5: 1);

writeln;

j: =0;

for i: =1 to N do begin

if b[i]< 0 then

begin

j: =j+1; x[j]: =b[i]; y[j]: =i;

end;

END;

WRITELN(' ': 10, 'НОВІ МАСИВИ');

if j> 0 then for i: =1 to j do

writeln(' ': 5, 'x(', i, ')=', x[i]: 5: 1, 'y(', i, ')=', y[i]: 2)

else WRITELN(' ТАКИХ ЕЛЕМЕНТІВ НЕМА);

p: =readkey

end.

Приклад 19. Знайти суму двох найбільших негативних елементів масиву x(15).

Порядок роботи:

Крок 1. Уводимо масив x(15).

Крок 2. Установлюємо вихідний індекс робочого масиву j=0.

Крок 3. Організовуємо цикл, що перебирає елементи вихідного масиву (тобто індекс i), починаючи з 1-го і кінчаючи 15-м.

Крок 4. Якщо x_i ³ 0, то йдемо на крок 7.

Крок 5. Встановлюємо індекс наступного елемента робочого масиву j = j + 1.

Крок 6. Привласнюємо елементу робочого масиву значення елемента вихідного масиву y_j = x_i.

Крок 7. Якщо цикл за i не закінчився, йдемо на початок циклу, тобто на крок 3.

Крок 8. Якщо j < 2, то видаємо повідомлення «Масив не сформований» і йдемо на крок 17.

Крок 9. Організовуємо цикл, що визначає кількість переглядів робочого масиву (тобто індекс k), починаючи з 1-го і кінчаючи j-м.

Крок 10. Організовуємо цикл, що визначає пару елементів робочого масиву, що переглядається, (тобто індекс i), починаючи з 1-го і кінчаючи (j-1) -м.

Крок 11. Якщо перший елемент не більше другого, то йдемо на крок 13.

Крок 12. Змінюємо два елемента місцями:

c = y_i; y_i = y_i+1; y_i+1 = c.

Крок 13. Якщо цикл по i не закінчився, йдемо на початок циклу, тобто на крок 10.

Крок 14. Якщо цикл за k не закінчився, йдемо на початок циклу, тобто на крок 9.

Крок 15. Обчислюємо суму s = y_j + y_j-1.

Крок 16. Друкуємо s.

Крок 17. Останов.

Приклад 20. Знайти добуток чотирьох найменших додатних кратних 5 елементів вихідного масиву Х(20).

Спочатку формуємо новий масив з додатних кратних 5 елементів вихідного масиву, а потім отриманий масив сортуємо методом виштовхування (пухирця). Програма має вид:

program pr20;

uses crt;

LABEL 1;

const n=20;

type raz=1..N; mac=array [raz] of integer;

var x, a: mac; d, i, j, k, r: integer; p: char;

BEGIN CLRSCR; WRITELN('УВЕДИ ', N, ' ЧИСЕЛ');

FOR I: =1 TO N DO READ(X[I]);

WRITELN(' ': 20, 'ВИХІДНИЙ МАСИВ');

FOR I: =1 TO N DO WRITE(X[I]: 4);

{ ФОРМУВАННЯ НОВОГО МАСИВУ }

writeln; j: =0;

for i: = 1 to N do begin

IF (X[I]> 0) AND (X[I] MOD 5 = 0) THEN

BEGIN J: =J+1; A[J]: =X[I]; END; END;

IF J=0 THEN WRITELN(‘ МАСИВ НЕ СФОРМОВАНО’): goto 1;

{ СОРТУВАННЯ ПО ЗРОСТАННЮ }

for k: = 1 to j do

for i: = 1 to j-k do

if a[i+1]< a[i] then

BEGIN D: =A[I]; A[I]: =A[I+1]; A[I+1]: =D; END;

WRITELN(' ': 5, 'ВІДСОРТОВАНИЙ МАСИВ');

for i: = 1 to j do write(a[i]: 4); writeln;

if j> =4 then begin r: =1;

for i: =1 to 4 do r: =r*a[i];

WRITELN('ДОБУТОК 4- Х НАЙМЕНШИХ=', R: 6); end

ELSE WRITELN(‘Масив не містить 4 додатних кратних 5 елементів’);

1: p: =readkey

end.