Що означає відсортувати масив
У масиві є числа 5 2 4 1. Розташуємо їх від меншого до більшого:
Таке впорядкування називають сортуванням за неспаданням. Кожне наступне число не менше від попереднього. Повторення дозволені: 1 2 2 5 теж упорядковано правильно.
Під час сортування кількість елементів не змінюється. Ми лише переставляємо наявні числа. Індекси комірок залишаються 0, 1, 2, …, а значення в них можуть змінитися.
Розглянемо три способи. Вони дають однаковий результат, але виконують різні дії. Спочатку зрозумій ці дії на прикладах. Код можна розгорнути окремо.
1 · Сортування вибором
Знаходимо найменше число в решті масиву й ставимо його на наступне місце. Це також називають методом простого вибору.
- Шукаємо мінімум у всьому масиві та міняємо його місцями з першим елементом.
- Перше місце вже готове. Шукаємо мінімум серед решти й ставимо його на друге місце.
- Продовжуємо, поки залишиться один елемент: він уже на своєму місці.
У цьому прикладі весь масив упорядкувався після першого обміну. Але алгоритм ще перевіряє решту чисел. Якщо мінімум уже на потрібній позиції, обмін не виконуємо.
Функція SelectionSort на C++
void SelectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) minIndex = j;
}
if (minIndex != i) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}i є позицією, яку заповнюємо. minIndex зберігає індекс найменшого знайденого числа. j перебирає решту масиву. Змінна temp потрібна для обміну двох чисел.
2 · Бульбашкове сортування
Порівнюємо сусідів і міняємо їх місцями, якщо ліве число більше. Це метод простого обміну, або «бульбашка».
Перший прохід для того самого масиву:
Найбільше число 5 опинилося в кінці. Далі його вже не перевіряємо. Повторюємо прохід для трьох чисел, потім для двох:
Функція BubbleSort на C++
void BubbleSort(int arr[], int n) {
for (int pass = 0; pass < n - 1; pass++) {
for (int j = 0; j < n - 1 - pass; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}pass рахує завершені проходи, починаючи з 0. На кожному проході j і j + 1 є індексами сусідів. Межа n − 1 − pass скорочується, бо правий край уже готовий.
3 · Сортування вставленням
Беремо наступне число й знаходимо йому місце серед уже впорядкованих чисел ліворуч. Інша назва: метод прямого включення.
- Перше число вважаємо впорядкованою частиною з одного елемента.
- Зберігаємо наступне число в окремій змінній value.
- Зсуваємо більші числа праворуч і записуємо value на звільнене місце.
- Беремо наступне початкове число й повторюємо дії.
Вертикальна риска лише відокремлює впорядковану частину у схемі. У масиві такої риски немає.
На попередній сторінці ми додавали новий елемент і збільшували n. Тут переставляємо число, яке вже є в масиві. Тому n не змінюємо, функцію InsArr не викликаємо й додаткову комірку в масиві не використовуємо. Число тимчасово зберігаємо у змінній value.
Функція InsertionSort на C++
void InsertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int value = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > value) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = value;
}
}i позначає число, яке вставляємо; j рухається ліворуч. Умова спочатку перевіряє j ≥ 0. Коли j стає −1, друга частина умови вже не обчислюється, тож звернення до arr[−1] немає. Збережене число записуємо в позицію j + 1.
Порівняй три способи на одному масиві
Помаранчеві комірки беруть участь у поточній дії. Зелені показують готові позиції для вибору й бульбашки; для вставлення це впорядкована частина, яка ще може змінитися.
Для порівняння змінюй лише спосіб сортування: числа залишаться тими самими. У сортуванні вставленням під час зсуву на екрані тимчасово можуть бути два однакові числа: потрібне число в цей час зберігається окремо у value.
Як їх розрізняти
| Спосіб | Основна дія | Що зростає після проходу |
|---|---|---|
| Вибором | Знаходимо мінімум у решті масиву й обмінюємо два елементи | Кількість готових позицій зліва |
| Бульбашкою | Порівнюємо й обмінюємо сусідів | Кількість готових позицій справа |
| Вставленням | Зберігаємо число, зсуваємо більші числа й вставляємо збережене | Довжина впорядкованої частини зліва |
Для одного елемента всі три способи одразу дають готовий результат. Від’ємні та однакові числа теж можна сортувати.
Як викликати функцію у програмі
Цей приклад використовує сортування вибором. Введіть n, а потім n цілих чисел. Наприклад: 4 5 2 4 1. Результат: 1 2 4 5.
Повна програма C++
#include <iostream>
using namespace std;
void SelectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) minIndex = j;
}
if (minIndex != i) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
int main() {
const int capacity = 100;
int arr[capacity];
int n;
cout << "Введіть кількість чисел від 1 до 100: ";
cin >> n;
if (n < 1 || n > capacity) {
cout << "Некоректна кількість\n";
} else {
cout << "Введіть числа: ";
for (int i = 0; i < n; i++) cin >> arr[i];
SelectionSort(arr, n);
for (int i = 0; i < n; i++) cout << arr[i] << " ";
cout << "\n";
}
return 0;
}Щоб випробувати інший спосіб, замініть визначення функції SelectionSort на BubbleSort або InsertionSort із відповідного розділу. У main замініть виклик на BubbleSort(arr, n); або InsertionSort(arr, n);.
Окремі демонстрації
За потреби можна відкрити й окремі демонстрації з підручника: