JuniorКодОчень частоЕщё не отвечали
Реализуйте любую сортировку
Реализуйте сортировку сравнениями, упорядочивающую вектор по возрастанию «на месте» (in-place). Выберите один алгоритм (например, quicksort или merge sort) и будьте готовы обсудить его сложность и стабильность.
Требования:
- Среднее O(n log n).
- Обработайте базовые случаи (размер 0 и 1) и дубликаты.
- Не вызывайте
std::sort— реализуйте алгоритм сами.
#include <vector>
void sort(std::vector<int>& arr) {
// ваш код здесь
}Допишите реализацию.
Quicksort: среднее O(n log n), in-place, нестабильная, деградирует до O(n²) при неудачном опорном — используйте медиану трёх или случайный пивот. Merge sort: гарантированное O(n log n), стабильная, требует O(n) доп. памяти.
- ✗Всегда выбирать первый элемент как опорный — O(n²) на отсортированном входе
- ✗Не обрабатывать базовый случай (массив размера 0 или 1)
- ✗Путать стабильность merge sort со свойством in-place у quicksort
- →Что такое introsort и почему
std::sortиспользует его вместо чистого quicksort? - →Когда следует предпочесть merge sort перед quicksort?
Оглавление
Задача
Реализуйте алгоритм быстрой сортировки (quicksort) и сортировки слиянием (merge sort).
Решение
#include <vector>
#include <algorithm>
#include <cassert>
// ===== Quicksort =====
int partition(std::vector<int>& arr, int lo, int hi) {
// Медиана трёх для выбора опорного элемента
int mid = lo + (hi - lo) / 2;
if (arr[mid] < arr[lo]) std::swap(arr[mid], arr[lo]);
if (arr[hi] < arr[lo]) std::swap(arr[hi], arr[lo]);
if (arr[mid] < arr[hi]) std::swap(arr[mid], arr[hi]);
int pivot = arr[hi]; // hi теперь медиана
int i = lo - 1;
for (int j = lo; j < hi; ++j) {
if (arr[j] <= pivot) std::swap(arr[++i], arr[j]);
}
std::swap(arr[i + 1], arr[hi]);
return i + 1;
}
void quickSort(std::vector<int>& arr, int lo, int hi) {
if (lo >= hi) return;
int p = partition(arr, lo, hi);
quickSort(arr, lo, p - 1);
quickSort(arr, p + 1, hi);
}
// ===== Merge sort =====
void merge(std::vector<int>& arr, int lo, int mid, int hi) {
std::vector<int> tmp(arr.begin() + lo, arr.begin() + hi + 1);
int left = 0, right = mid - lo + 1, k = lo;
int rightEnd = hi - lo;
while (left <= mid - lo && right <= rightEnd)
arr[k++] = (tmp[left] <= tmp[right]) ? tmp[left++] : tmp[right++];
while (left <= mid - lo) arr[k++] = tmp[left++];
while (right <= rightEnd) arr[k++] = tmp[right++];
}
void mergeSort(std::vector<int>& arr, int lo, int hi) {
if (lo >= hi) return;
int mid = lo + (hi - lo) / 2;
mergeSort(arr, lo, mid);
mergeSort(arr, mid + 1, hi);
merge(arr, lo, mid, hi);
}
int main() {
auto check = [](std::vector<int> v, auto fn) {
fn(v, 0, static_cast<int>(v.size()) - 1);
assert(std::is_sorted(v.begin(), v.end()));
};
check({5, 3, 1, 4, 2}, quickSort);
check({5, 3, 1, 4, 2}, mergeSort);
check({1}, quickSort);
check({}, quickSort);
check({2, 2, 2}, mergeSort);
}Сравнение алгоритмов
| Алгоритм | Среднее | Худшее | Память | Стабильная |
|---|---|---|---|---|
| Quicksort | O(n log n) | O(n²) | O(log n) | Нет |
| Merge sort | O(n log n) | O(n log n) | O(n) | Да |
| std::sort | O(n log n) | O(n log n) | O(log n) | Нет |
Оглавление
