Сортировки в C++

1. Передача массива в функцию по ссылке

В C++ массивы (чаще всего — vector) почти никогда не передают по значению, потому что это приводит к копированию всех элементов. Если массив большой, такое копирование занимает много времени и памяти.

Передача по ссылке

Если функция должна изменять массив, его передают по ссылке:

void sort_array(vector<int>& a) {
    // функция может изменять массив a
}

В этом случае:

• массив не копируется;
• функция работает с тем же самым массивом, который был передан.

Передача по константной ссылке

Если функция не должна изменять массив, используется константная ссылка:

void print_array(const vector<int>& a) {
    // элементы массива менять нельзя
}

Это означает:

• массив не копируется;
• функция гарантирует, что не изменит массив;
• компилятор не позволит случайно изменить элементы.

Правило:

• если массив нужно менять → vector<int>&
• если массив менять не нужно → const vector<int>&

Передача массива по значению (без ссылки) используется очень редко.

2. Квадратичные сортировки

Существуют три простых алгоритма сортировки:

• сортировка выбором;
• сортировка вставками;
• сортировка пузырьком.

Все они имеют сложность O(n²) и работают медленно на больших массивах.

Сортировка выбором

Массив обрабатывается слева направо.

1. Сначала ищется минимальный элемент во всём массиве.
2. Найденный минимальный элемент меняется местами с элементом на позиции 0.
3. Затем ищется минимальный элемент среди элементов с индексами от 1 до конца массива.
4. Этот элемент меняется местами с элементом на позиции 1.
5. Далее ищется минимум среди элементов, начиная с позиции 2, и меняется местами с элементом на позиции 2.
6. Эти действия повторяются, пока не будут обработаны все элементы массива.

После каждого шага один элемент оказывается на своём окончательном месте.

Сортировка вставками

Массив обрабатывается слева направо, при этом левая часть массива всегда считается отсортированной.

1. Первый элемент массива считается отсортированным.
2. Берётся следующий элемент массива.
3. Этот элемент сравнивается с элементами слева от него.
4. Пока слева есть элементы, которые больше рассматриваемого, они сдвигаются на одну позицию вправо.
5. Рассматриваемый элемент вставляется на освободившееся место.
6. Далее берётся следующий элемент массива, и процесс повторяется.

Алгоритм заканчивается, когда обработаны все элементы массива.

Сортировка пузырьком

Алгоритм выполняет последовательные проходы по массиву.

1. Массив просматривается слева направо.
2. Каждая пара соседних элементов сравнивается.
3. Если элементы стоят в неправильном порядке, они меняются местами.
4. За один проход запоминается, был ли выполнен хотя бы один обмен.
5. Если за полный проход по массиву не произошло ни одного обмена, массив считается отсортированным.
6. Если обмены были, выполняется следующий проход по массиву.

Алгоритм заканчивается, когда за один полный проход не происходит ни одного обмена.

3. Сортировка слиянием

Сортировка слиянием имеет сложность O(n log n) и работает значительно быстрее квадратичных алгоритмов.

Основная идея

1. Если массив содержит 0 или 1 элемент, он уже отсортирован.
2. Иначе массив делится на две части, размеры которых отличаются не более чем на один элемент.
3. Каждая часть сортируется тем же самым алгоритмом.
4. Два отсортированных массива объединяются в один отсортированный массив.

Слияние двух отсортированных массивов

1. Создаётся новый массив для результата.
2. Указатели ставятся на начало каждого из двух массивов.
3. Сравниваются элементы, на которые указывают указатели.
4. Меньший элемент добавляется в результирующий массив, а соответствующий указатель сдвигается.
5. Эти действия повторяются, пока один из массивов не закончится.
6. Все оставшиеся элементы второго массива добавляются в конец результата.

Пример работы

[4, 1, 3, 2]

Он делится на две части:

[4, 1] и [3, 2]

Каждая часть делится дальше, пока не останутся массивы из одного элемента:

[4] [1]   [3] [2]

Затем происходит последовательное слияние:

[1, 4]   [2, 3]

Финальный результат слияния:

[1, 2, 3, 4]

4. Стандартная функция sort

В C++ есть готовая и очень быстрая функция сортировки.

Подключение

Чтобы ей пользоваться, нужно подключить заголовочный файл:

#include <algorithm>

Сортировка по неубыванию

sort(a.begin(), a.end());

Массив будет отсортирован по возрастанию.

Сортировка по невозрастанию

sort(a.rbegin(), a.rend());

Массив будет отсортирован по убыванию.

Здесь:

• begin() и end() — обычные итераторы;
• rbegin() и rend() — обратные (реверс) итераторы.

С итераторами вы познакомитесь позже, сейчас достаточно понимать, что они указывают на начало и конец массива.

Какие элементы можно сортировать

Функция sort работает, если для элементов определён оператор <.

Поэтому можно сортировать:

• все числовые типы (int, double, long long и т.д.);
• строки (string).

Этого достаточно для большинства задач на начальном этапе обучения.