Алгоритм впорядкування елементів масиву

Під час опрацювання сукупностей даних часто виникає потреба впорядкувати ці дані за деякою ознакою. Числові дані можна відсортувати за
величиною (наприклад, створити рейтинг навчальних досягнень), рядкові
дані — в алфавітному порядку (упорядкувати список учнів).

Сортування елементів масиву — це впорядкування їх за деякою ознакою.Розглянемо два найпростіші методи сортування масиву. Нехай потрібно впорядкувати масив X: аrray[1..10] оf Real; за неспаданням: X[1] ≤ X[2] ≤ ... ≤ X[10]. Сортування вибором максимального елемента

Цей метод заснований на тому, що під час кожного проходу циклу
переглядається частина масиву завдовжки К елементів. Наприклад, для
масиву X[1..10] під час першого проходу К = 10.Алгоритм сортування за зростанням (рис. 36.1):• відшукати максимальний з елементів X[1]..X[10];• максимальний елемент поміняти місцями з X[10];• відшукати максимальний елемент із частини масиву X[1]..X[9];• максимальний елемент із цієї частини поміняти місцями з X[9];<…>• максимальний елемент із частини масиву X[1]..X[2] поміняти місцями
з X[2].
фрагмент програмного модуля виглядатиме саме так:
For K := 10 downto 2 do
begin{ пошук М — номера Мах(X[1..K] }
M := 1; Max := X[1];For i := 2 to K do
If X[i] > Max Then beginMax := X[i]; M := i;end;{ перестановка X[K] і X[M] з використанням допоміжної комірки С }
C := X[M];    X[M] := X[K];     X[K] := C;end;

Вигляд масиву X[1..10] на кожному кроці сортування за неспаданням
вибором максимального елемента зображено на малюнку.

Сортування обміном (метод бульбашки)  

Метод бульбашки ґрунтується на порівнянні та перестановці сусідніх
чисел.Алгоритм сортування за зростанням:
1) послідовно порівнювати пари сусідніх елементів X[і] і X[і + 1] (і:1..N – 1),
і, якщо X[і] > X[і + 1], то поміняти їх місцями і логічній змінній Prap надати значення True. У результаті першого перегляду елементів масиву на N-му місці буде найбільший з усіх елементів, тобто він, як бульбашка, «спливе» вгору;
2) виконати такі самі дії з елементами від 1 до (N – 2): на (N – 1)-му місці з’явиться
найбільший серед (N – 1) елементів і т. д.
Змінна Prap: Boolean виконує роль прапорця. Вона отримує значення True за умови, що відбулась хоча б одна перестановка сусідніх елементів. Якщо значення Prap не змінилось, це означає, що елементи масиву вже впорядковані і подальший перегляд послідовності значень не потрібний .

Дано масив А[1..10], значення якого задані випадковим чином і містяться в діапазоні від 0 до 19. Упорядкувати масив за спаданням (А[1] ≥ А[2] ≥ ... ≥ А[10]) методом бульбашки.
Для покрокового аналізу ходу впорядкування додамо на форму компонент StringGrid і налаштуємо його властивості таким чином:  

  ColCount - 10          FixedRows - 1
  FixedCols - 0             RowCount  - 11

Виведення заголовків стовпців запрограмуємо в процедурі обробки події OnCreate (див. § 35) 

Алгоритм упорядкування масиву реалізуємо в процедурі обробки події OnClick командної кнопки Button1.

Опис величин. Опишемо змінні, потрібні для реалізації алгоритму:var А: array[1..10] of Integer;
i, c, j: Integer; 
Prap: Boolean;
Очищення рядків таблиці StringGrid1:
For i := 1 to 10 do StringGrid1.Rows[i].Clear;
Задавання значень елементів масиву А випадковим чином:
Randomize;
For i := 1 to 10 do 
begin
A[i] := Random(20);
StringGrid1.Cells[i – 1, 1] := IntToStr(A[i]);
end; 

Упорядкування масиву A[1..10] за спаданням методом бульбашки.До тіла циклу Repeat додамо оператори для виведення елементів масиву А на кожному кроці сортування:j := 1; // номер кроку сортуванняRepeat Prap := False;
For i := 1 to 9 do
If A[i] < A[i + 1] Then 
beginC := A[i]; 
A[i] := A[i + 1]; 
A[i + 1] := C;
Prap := True end;
j := j+1;
{ виведення масиву; j — номер кроку сортування і рядка таблиці }
For i := 1 to 10 doStringGrid1.Cells[i – 1, j] := IntToStr(A[i]);
Until Prap = False;  

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

Практична частина

1. Впорядкуйте масив А(10) за зростанням будь-яким методом. Протестуйте програму на різних даних. Чекаю на копії програмного модуля, форми, які надішліть на електронну адресу lgskuratovska@gmail.com

2. Виконайте комп'ютерне тестування 36 з перевіркою на сайті
interactive.ranok.com.ua. Збережіть результати тесту у pdf-файлі і відправьте його на електронну адресу lgskuratovska@gmail.com