Поиск и сортировка: ваши первые алгоритмы

Научите компьютер находить данные и раскладывать их по порядку

Главная идея: алгоритм — это просто чёткий список шагов, который решает задачу. В этой теме вы познакомитесь со своими первыми знаменитыми алгоритмами: способами искать значение в массиве и способами сортировать массив по порядку. И самое приятное: у вас уже есть все нужные инструменты — массивы, циклы и функции из прошлых уроков.

К концу темы вы сможете:

выполнять линейный поиск, проверяя элементы по одному,
выполнять двоичный поиск в отсортированном массиве, разрезая его пополам,
сортировать массив с помощью пузырьковой сортировки и сортировки выбором,
объяснять, почему одни шаги намного быстрее других.

1. Что такое алгоритм?

Алгоритм — это набор чётких пошаговых инструкций, который всегда завершается и даёт ответ. Кулинарный рецепт — это алгоритм. Шаги, как завязать шнурки, — тоже алгоритм. В программировании мы записываем алгоритмы кодом на C++, чтобы компьютер мог им следовать.

Две самые частые задачи компьютера — это поиск (найти один элемент среди многих) и сортировка (расставить элементы по порядку, например от меньшего к большему). Вспомните библиотеку: вы быстро находите книгу только потому, что книги уже отсортированы на полках. Поиск и сортировка всё время работают вместе.

Все сегодняшние алгоритмы работают с массивом чисел с помощью обычных циклов for и while. Ничего нового — лишь умные способы расставить уже знакомые вам циклы.

2. Линейный поиск: проверяем по одному

Линейный поиск — самый простой способ что-то найти. Вы начинаете с первого элемента и идёте дальше, по одному, пока не найдёте нужное или не дойдёте до конца. Именно так вы ищете друга, вглядываясь в каждое лицо в толпе.

Функция ниже возвращает индекс, где найден искомый элемент, или -1, если значения нет в массиве. Мы используем -1, потому что настоящих отрицательных позиций в массиве не бывает, поэтому это безопасный знак «не найдено».

#include <iostream>
using namespace std;

// Возвращает индекс target или -1, если его нет в массиве.
int linearSearch(int arr[], int size, int target) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) {
            return i;        // нашли - остановиться и сообщить где
        }
    }
    return -1;               // прошли весь массив, здесь нет
}

int main() {
    int nums[5] = {4, 8, 15, 16, 23};
    cout << linearSearch(nums, 5, 15) << endl;   // 2
    cout << linearSearch(nums, 5, 99) << endl;   // -1
    return 0;
}

Ожидаемый вывод:

2
-1

Линейный поиск работает всегда, даже на неаккуратном, неотсортированном массиве. Его минус — скорость: если значение последнее (или его нет), придётся проверить каждый элемент.

Поиск и сортировка: ваши первые алгоритмы