SeniorКодРедкоЕщё не отвечали
Реализуйте алгоритм сортировки (уровень Senior): merge sort или introsort с обоснованием
Реализуйте сортировку вектора с гарантированным O(n log n) «на месте» (in-place) — например, bottom-up merge sort или гибрид в стиле introsort. Будьте готовы обосновать, когда предпочесть её quicksort или heapsort.
Требования:
- Худший случай O(n log n) — без деградации до O(n²) на враждебном входе.
- Укажите, стабилен ли ваш выбор и сколько доп. памяти он использует.
- Обработайте пустой вход, один элемент и вход с множеством дубликатов.
#include <vector>
void sort(std::vector<int>& arr) {
// ваш код здесь
}Допишите реализацию.
Merge sort гарантирует O(n log n) и является стабильной — подходит для связных списков и внешней сортировки. Introsort (quicksort + fallback на heapsort + сортировка вставками для малых диапазонов) используется в std::sort: гарантированное O(n log n), in-place, но нестабильная.
- ✗Не знать, почему
std::sortиспользует introsort вместо чистого quicksort - ✗Реализовывать merge sort с O(n log n) дополнительной памятью, когда просят in-place
- ✗Игнорировать оптимизацию сортировкой вставками для малых подмассивов (< 16 элементов)
- →При каком пороге глубины introsort переключается с quicksort на heapsort?
- →Чем
std::stable_sortотличается отstd::sortс точки зрения алгоритма и сложности?
Оглавление
Задача
Реализуйте bottom-up merge sort (без рекурсии) и обсудите, когда предпочесть его другим алгоритмам сортировки.
Решение
#include <vector>
#include <algorithm>
#include <cassert>
// Bottom-up merge sort — O(n log n), стабильная, O(n) доп. память
void mergeSortBottomUp(std::vector<int>& arr) {
const int n = static_cast<int>(arr.size());
std::vector<int> tmp(n);
for (int width = 1; width < n; width *= 2) {
for (int lo = 0; lo < n; lo += 2 * width) {
int mid = std::min(lo + width, n);
int hi = std::min(lo + 2 * width, n);
// Слияние [lo, mid) и [mid, hi)
std::merge(arr.begin() + lo, arr.begin() + mid,
arr.begin() + mid, arr.begin() + hi,
tmp.begin() + lo);
std::copy(tmp.begin() + lo, tmp.begin() + hi,
arr.begin() + lo);
}
}
}
// Краткое сравнение: когда использовать
// merge sort: стабильность нужна; внешняя сортировка; данные в связном списке
// quicksort: in-place; cache-friendly; средний O(n log n) достаточен
// heapsort: гарантированный O(n log n) in-place; не нужна стабильность
// introsort: std::sort — лучший общий выбор для массивов
int main() {
std::vector<int> v = {5, 1, 4, 2, 8, 3, 7, 6};
mergeSortBottomUp(v);
assert(std::is_sorted(v.begin(), v.end()));
std::vector<int> empty;
mergeSortBottomUp(empty);
std::vector<int> single = {42};
mergeSortBottomUp(single);
assert(single[0] == 42);
std::vector<int> dup = {3, 1, 2, 1, 3};
mergeSortBottomUp(dup);
assert(std::is_sorted(dup.begin(), dup.end()));
}Анализ алгоритмов сортировки
| Алгоритм | Лучший | Средний | Худший | Память | Стабильный |
|---|---|---|---|---|---|
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) | Нет |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Да |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) | Нет |
| Introsort | O(n log n) | O(n log n) | O(n log n) | O(log n) | Нет |
| Timsort | O(n) | O(n log n) | O(n log n) | O(n) | Да |
Bottom-up (итеративный) merge sort предпочтительнее рекурсивного: нет накладных расходов рекурсии.
Оглавление
