C++ · Масиви
Одновимірні масиви · 8.12.1

Як упорядкувати числа

Три способи сортування: вибором, бульбашкою та вставленням

Що означає відсортувати масив

У масиві є числа 5 2 4 1. Розташуємо їх від меншого до більшого:

Було: 5 2 4 1 Стало: 1 2 4 5

Таке впорядкування називають сортуванням за неспаданням. Кожне наступне число не менше від попереднього. Повторення дозволені: 1 2 2 5 теж упорядковано правильно.

Під час сортування кількість елементів не змінюється. Ми лише переставляємо наявні числа. Індекси комірок залишаються 0, 1, 2, …, а значення в них можуть змінитися.

Розглянемо три способи. Вони дають однаковий результат, але виконують різні дії. Спочатку зрозумій ці дії на прикладах. Код можна розгорнути окремо.

1 · Сортування вибором

Знаходимо найменше число в решті масиву й ставимо його на наступне місце. Це також називають методом простого вибору.

  1. Шукаємо мінімум у всьому масиві та міняємо його місцями з першим елементом.
  2. Перше місце вже готове. Шукаємо мінімум серед решти й ставимо його на друге місце.
  3. Продовжуємо, поки залишиться один елемент: він уже на своєму місці.
5 2 4 1 1 2 4 5 мінімум 1 поставили на початок 1 2 4 5 мінімум решти 2 уже на місці 1 2 4 5 мінімум решти 4 уже на місці

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

Функція 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 2 4 1 → 2 5 4 1 обміняли 5 і 2 2 5 4 1 → 2 4 5 1 обміняли 5 і 4 2 4 5 1 → 2 4 1 5 обміняли 5 і 1

Найбільше число 5 опинилося в кінці. Далі його вже не перевіряємо. Повторюємо прохід для трьох чисел, потім для двох:

Після 1-го проходу: 2 4 1 5 Після 2-го проходу: 2 1 4 5 Після 3-го проходу: 1 2 4 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 · Сортування вставленням

Беремо наступне число й знаходимо йому місце серед уже впорядкованих чисел ліворуч. Інша назва: метод прямого включення.

  1. Перше число вважаємо впорядкованою частиною з одного елемента.
  2. Зберігаємо наступне число в окремій змінній value.
  3. Зсуваємо більші числа праворуч і записуємо value на звільнене місце.
  4. Беремо наступне початкове число й повторюємо дії.
5 | 2 4 1 спочатку впорядкована лише 5 2 5 | 4 1 вставили 2 перед 5 2 4 5 | 1 вставили 4 між 2 та 5 1 2 4 5 | вставили 1 на початок

Вертикальна риска лише відокремлює впорядковану частину у схемі. У масиві такої риски немає.

На попередній сторінці ми додавали новий елемент і збільшували 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);.