Dev Blog

Пошук, сортування та матриці ​

Пошук, сортування та колекції структур ​

Лінійний пошук переглядає елементи по черзі до збігу або кінця. Він працює без попереднього впорядкування і потребує в найгіршому разі N порівнянь. Для порожнього вектора повертається «не знайдено». Не використовуйте значення елемента 0 як результат невдалого пошуку: воно може бути справжнім допустимим значенням.

Бінарний пошук щоразу відкидає половину впорядкованого інтервалу. Його передумова – сортування за тим самим правилом, за яким порівнюють ключ. Зручний інтервал [left,right) включає ліву межу і виключає праву. Середину обчислюють left + (right-left)/2, щоб уникати зайвого ризику переповнення суми меж. Якщо дані не впорядковані, коректний код пошуку не гарантує результату.

Сортування вибором знаходить найменший елемент решти і ставить його на наступну позицію. Після i кроків перші i елементів уже впорядковані й не більші за решту. Алгоритм простий, але виконує квадратичну кількість порівнянь. Для практичних задач бібліотека має std::ranges::sort із <algorithm>; тут його згадуємо як готовий засіб, а механіку вивчаємо вручну.

Приклад 2. Журнал оцінок ​

Структура Student пов’язує ім’я та бал. Програма додає запис, вилучає один за перевіреним індексом і впорядковує решту за спаданням балів. Дані задані в коді, щоб зосередитися на операціях колекції.

cpp
#include <vector>
#include <string>
#include <print>
#include <utility>

struct Student { std::string name; int score; };

int main()
{
    std::vector<Student> group{{"Olena", 88}, {"Ivan", 72}};
    group.push_back({"Nina", 95});
    const std::size_t remove = 1;
    if (remove < group.size())
        group.erase(group.begin() + remove);
    for (std::size_t i = 0; i < group.size(); ++i)
    {
        std::size_t best = i;
        for (std::size_t j = i + 1; j < group.size(); ++j)
            if (group[j].score > group[best].score) best = j;
        std::swap(group[i], group[best]);
    }
    for (const auto& student : group)
        std::println("{:<10} {:3}", student.name, student.score);
}
text
Nina        95
Olena       88

Обмінюється вся структура, тому бал залишається пов’язаним з ім’ям. Якби сортували окремий масив балів, а імена залишили без змін, журнал став би недостовірним. Для однакових балів алгоритм вибором не гарантує збереження початкового порядку; якщо потрібне правило розв’язання нічиєї, його треба задати явно.

Матриці та двовимірні дані ​

Матриця має рядки й стовпці. Вбудований int a[2][3]{} є прямокутним набором шістьох цілих значень. Для динамічного розміру зручно використовувати vector<vector<int>>, де зовнішній вектор зберігає рядки. Проте він дозволяє рядки різної довжини; якщо потрібна математична матриця, програма має зберігати прямокутність як інваріант.

Перед matrix[0].size() перевірте, що є хоча б один рядок. Для кожного рядка перевіряйте власну довжину, якщо дані могли змінюватися. Порядок індексів matrix[row][column] має бути послідовним. Транспонування обмінює ролі рядків і стовпців, тому результат матриці R×C має розмір C×R, а не R×C.

Приклад 3. Транспонування ​

cpp
#include <vector>
#include <print>

int main()
{
    const std::vector<std::vector<int>> a{{1, 2, 3}, {4, 5, 6}};
    const auto rows = a.size();
    const auto columns = a[0].size();
    std::vector<std::vector<int>> b(columns,
        std::vector<int>(rows));
    for (std::size_t r = 0; r < rows; ++r)
        for (std::size_t c = 0; c < columns; ++c)
            b[c][r] = a[r][c];
    for (const auto& row : b)
    {
        for (int value : row) std::print("{:3}", value);
        std::println();
    }
}
text
  1  4
  2  5
  3  6

Приклад має сталу непорожню прямокутну матрицю. У версії з введенням обмежте рядки й стовпці до виділення пам’яті. Для перевірки корисна властивість: подвійне транспонування повертає початкову матрицю. Прямокутний тест 2×3 краще виявляє переплутані межі, ніж лише квадратний 3×3.