Сортировка упорядочивает массив. Простые сортировки — пузырьком, выбором, перемешиванием — учат понимать сравнения и обмены, а на практике пользуются стандартной std::sort.
Что нужно знать
- Пузырёк: сравниваются соседи, за проход наибольший «всплывает» в конец; если обменов не было — массив отсортирован.
- Выбор: ищется минимум неупорядоченной части и ставится на её начало — один обмен за проход.
- Шейкерная (перемешивание): проходы попеременно в обе стороны.
- Обмен: через временную переменную или
swap(a, b). - Простые сортировки делают порядка $n^2$ сравнений;
std::sort— около $n \log n$. - Инверсия — пара элементов в неправильном порядке; пузырёк делает столько обменов, сколько инверсий.
- Устойчивая сортировка сохраняет порядок равных элементов.
- По убыванию:
sort(a, a + n, greater<int>()).
Где чаще всего ошибаются
- Обменивать без временной переменной:
a = b; b = a;. - Ожидать, что сортировка выбором устойчива.
- Писать свою сортировку для миллиона элементов вместо
std::sort.
Проверить себя
По этой же теме курса есть проверочная работа из 15 заданий на 30 минут. Проверка автоматическая, результат виден сразу — и по работе целиком, и по каждой теме.