 |
2.1 Впорядкування вибором. Розв’язок задачі. Private Sub Command1_Click(). Dim N As Byte, k_min, j, i As Byte, A(1 To 10) As Integer
|
|
|
|
2. 1 Впорядкування вибором
Впорядкування вибором - це досить простий алгоритм. Його завдання – пошук найменшого елемента, який потім міняється місцями з елементом на початку списку. Потім знову знаходимо найменший елемент, з тих, що залишилися і міняємо його з другим елементом. Даний процес триває доти, поки всі елементи не займуть своє кінцеве положення.
Наприклад:
А(1) = 2 А(2) = 4 А(3) = 5 А(4) = 3 А(5) = 10 А(6) =8 А(7) =1
2 4 5 3 10 8 1
1. Визначаємо найменший елемент а(7) =1
2. Міняємо місцем з першим елементом 1 4 5 3 10 8 2
3. Серед всіх елементів, починаючи з другого, знову шукаємо мінімальний елемент і міняємо його місцем з другим 1 2 5 3 10 8 4
4. і т. п.
Для реалізації цього алгоритму необхідно використати вкладені цикли For. Зовнішній цикл (по i ) призначений для послідовного фіксування елементів масиву, внутрішній цикл (по j ) – здійснює пошук мінімуму (максимуму) і його позиції. Після виходу з внутрішнього циклу необхідно поміняти елементи місцями. Останній елемент у зовнішньому циклі не розглядається: він сам встає на своє місце.
Розв’язок задачі.
1. Створити форму за зразком рис. 2. 1, надати всім об’єктам значення властивостей відповідно таблиці 5.
Рис. 2. 1. Приклад початкового розміщення об'єктів на формі
Таблиця 5. Значення властивостей об’єктів до форми рис. 2. 1.
| ЕЛЕМЕНТ КЕРУВАННЯ | НАЗВА ВЛАСТИВОСТІ | ЗНАЧЕННЯ ВЛАСТИВОСТІ |
| Form1 | Caption | Сортування вибором |
| Text1 | Text | Порожньо |
| Label1 | Caption | Порожньо |
| Label2 | Caption | Порожньо |
| Picture1, Picture2 | - | (Всі властивості стандартні) |
| Command1 | Caption | Обчислення |
| Command2 | Caption | Вихід |
2. Ввести програмний код:
|
|
|
Private Sub Command1_Click()
Dim N As Byte, k_min, j, i As Byte, A(1 To 10) As Integer
Dim b, Min_el As Integer
'Введення й вивід вхідних даних
N = InputBox(" Введи розмірність масиву від 2 до 10" )
Label1 = " Розмірність масиву: "
Text1 = N
Label2 = " Mасив: А(" & N & " )"
For i = 1 To N
A(i) = InputBox(" Введи значення А(" & i & " )-го елемента" )
Picture1. Print A(i); " ";
Next i
'Впорядкування вибором
For i = 1 To N - 1
Min_el = A(i)
k_min = i
For j = i + 1 To N
If A(j) < Min_el Then
Min_el = A(j)
k_min = j
End If
Next j
A(k_min) = A(i)
A(i) = Min_el
'Вивід даних масиву А після кожної перестановки
For b = 1 To N
Picture2. Print A(b); " ";
Next b
Picture2. Print
Next i
End Sub
Private Sub Command2_Click()
End
End Sub
Впорядкування вибором працює досить добре зі списками, де елементи розташовані випадково або в прямому порядку, але для обернено впорядкованих списків продуктивність цього алгоритму трохи гірша. Для пошуку мінімального елемента списку впорядкування вибором виконує наступну послідовність операторів:
If A(j) < Min Then
Min = A(j)
k_min = j
End If
Якщо список впорядковано в зворотному порядку, умова A(j)< Min виконується за більший проміжок часу. Під час першого проходу через список елементів, вона буде істинна для всіх елементів, тому, що кожен елемент менший за попередній. Програма виконує порівняння багато разів, що призводить до деякого гальмування роботи алгоритма.
Це не найшвидший алгоритм, але він досить простий, а також швидко впорядковує невеликі списки.
3. Запустити програму на виконання, отримати результати.
Рис. 2. 2. Результати роботи програми Впорядкування вибором
|
|
|
Рис. 2. 3. Результати роботи програми Впорядкування вибором
2. 2 Сортування вставкою
Впорядкування вставкою – заснований на впровадженні в впорядковану частину масиву елемента, який знаходиться за цією частиною, якщо він задовольняє умовам впорядкування. Алгоритм переглядає вхідний список в порядку зростання і шукає місце, де необхідно вставити новий елемент. Потім він розміщує новий елемент в знайдену позицію.
При першому проходженні другий елемент порівнюється з першим, при другому – третій елемент порівнюється з першим і другим і т. д. Якщо елемент, що перевіряється ( (і+1) -тий елемент) задовольняє умові впорядкування серед і елементів, то він вставляється на j -е місце без порушення порядку, тобто елементи з індексами > =j і < =i-1 збільшують свій індекс на 1.
1. Створити форму за зразком рис. 2. 4., надати всім об’єктам значення властивостей відповідно таблиці 6.
Рис. 2. 4. Приклад початкового розміщення об'єктів на формі
Таблиця 6. Значення властивостей об’єктів до форми рис. 2. 4.
| ЕЛЕМЕНТ КЕРУВАННЯ | НАЗВА ВЛАСТИВОСТІ | ЗНАЧЕННЯ ВЛАСТИВОСТІ |
| Form1 | Caption | Сортування вставкою |
| Text1 | Text | Порожньо |
| Label1 | Caption | Порожньо |
| Label2 | Caption | Порожньо |
| Picture1, Picture2 | - | (Всі властивості стандартні) |
| Command1 | Caption | Обчислення |
| Command2 | Caption | Вихід |
2. Ввести програмний код:
|
|
|
