Вставка: кожний новий елемент вставляється у правильну позицію стосовно вже розміщених у масиві і впорядкованих елементів.

4. Злиття: впорядковані підмножини елементів об’єднуються в більші впорядковані підмножини.

5. Розподіл: машинна модифікація ручних методів упорядкування. Наприклад, упорядкування листів на пошті. Перша механічна версія такого упорядкування називається цифровим упорядкуванням. Ключ упорядкування розділяється на цифри, дані впорядковуються за значенням старшої цифри, потім отримані підмножини упорядковуються за значенням наступної цифри і так далі.

Розглянемо алгоритм упорядкування вибіркою.

Приклад. Нехай задано масив цілих чисел . Розробити програму, яка упорядковує цей масивів за зростанням елементів.

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

Програма упорядкування за зростанням масиву цілих чисел має вигляд:

Program LABR5_1;

{$APPTYPE CONSOLE}

uses Sysutils;

VAR a: array[1..300] of integer;

n, i, j, k, r: integer;

BEGIN

{Введення початкових даних}

writeln(‘Введіть розмір масиву а, (n< =300)’);

readln(n);

writeln(‘Введіть елементи масиву а’);

for i: =1 to n do

read(a[i]);

{Упорядкування за зростанням методом вибірки}

for i: =1 to n-1 do

begin k: =i;

for j: =i+1 to n do

if a[j]< a[k] then k: =j;

r: =a[i];

a[i]: =a[k];

a[k]: =r;

end;

{Виведення масиву по п’ять елементів у рядку}

for i: =1 to n do

if i mod 5 < > 0 then write(a[i]: 6)

else writeln(a[i]: 6);

readln;

END.

Розглянемо алгоритм злиття упорядкованих масивів. Цей алгоритм можна використовувати як для внутрішнього, так і зовнішнього впорядкування.

Приклад. Нехай задано два впорядкованих за зростанням елементів масиви цілих чисел і . Розробити програму, яка зливає ці масиви в один упорядкований за неспаданням елементів масив .

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

Program LABR5_2;

{$APPTYPE CONSOLE}

uses Sysutils;

VAR a: array[1..300] of integer;

b: array[1..200] of integer;

c: array[1..500] of integer;

n, m, i, j, k: integer;

BEGIN

{Введення початкових даних}

writeln(‘Введіть розмір масиву а, (n< =300)’);

readln(n);

writeln(‘Введіть впорядковані елементи масиву а’);

for i: =1 to n do

read(a[i]);

writeln(‘Введіть розмір масиву b, (m< =200)’);

readln(m);

writeln(‘Введіть впорядковані елементи масиву b’);

for i: =1 to m do

read(b[i]);

{Впорядкування злиттям}

i: =1; j: =1; k: =0;

while (i < = n) and (j < = m) do

if a[i] < b[j] then

begin k: =k+1; c[k]: =a[i]; i: =i+1; end

else

begin k: =k+1; c[k]: =b[j]; j: =j+1; end;

if i > n then

for i: =j to m do

begin k: =k+1; c[k]: =b[i]; end

else

for j: =i to n do

begin k: =k+1; c[k]: =a[j]; end;

{Виведення впорядкованого масиву}

{ по п’ять елементів у рядку}

for i: =1 to k do

if i mod 5 < > 0 then write(c[i]: 6)

else writeln(c[i]: 6);

readln;

END.

Пошук даних. Задача пошуку даних є основною при роботі з великими обcягами інформації. Якщо дані не впорядковані, то пошук зводиться до послідовного перегляду всіх ключів. Якщо дані впорядковані, то існує ряд ефективних алгоритмів пошуку даних.

Розглянемо один з таких алгоритмів пошуку ключа поділом масиву даних навпіл.

Приклад. Нехай задано масив упорядкованих за зростанням цілих чисел , . Розробити програму, яка знаходить у цьому масиві порядковий номер елемента .

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

Програма пошуку ключа в упорядкованому масиві методом поділу масиву навпіл має вигляд:

Program LABR5_3;

{$APPTYPE CONSOLE}

uses Sysutils;

VAR x: array[1..300] of integer;

n, i, a, b, kl: integer;

f: boolean;

BEGIN

{Введення початкових даних}

writeln(‘Введіть розмір масиву x, (n< =300)’);

readln(n);

writeln(‘Введіть упорядковані елементи масиву x’);

for i: =1 to n do

read(x[i]);

writeln(‘Введіть елемент kl’);

readln(kl);

{Пошук заданого елемента в упорядкованому масиві x}

a: =1; b: =n; f: =false;

while (a < b) and (not f) do

begin i: =(a+b) div 2; {поділ масиву навпіл}

if x[i] = kl then f: =true;

if x[i] < kl then a: =i+1;

if x[i] > kl then b: =i -1;

end;

if f then writeln(‘Номер шуканого ключа в масиві =’, i)

else writeln(‘Шуканого ключа у масиві немає’);

readln;

END.