Задачи на реализацию конкретных сортировок
Использовать только эффективные алгоритмы:
• Merge Sort
• Quick Sort
• Heap Sort
• TimSort-подобная логика (частично отсортированные данные)
• Counting Sort (для чисел с диапазоном)
Без Bubble / Selection / Insertion.
⸻
Уровень 1 — Легкий (3 задачи)
Задача 1 — Merge Sort для заказов по сумме
Контекст:
Система выгружает заказы в случайном порядке. Требуется стабильная сортировка по сумме заказа.
Входные данные:
orders = [540, 120, 800, 300, 450, 200]
Задача:
1. Реализовать Merge Sort
2. Отсортировать список по возрастанию
3. Вывести результат
Требование:
Нельзя использовать встроенную sort().
Цель:
Отработать:
• рекурсию
• разбиение массива
• слияние списков
⸻
Задача 2 — Quick Sort для цен товаров
Контекст:
Есть список цен товаров. Нужно быстро отсортировать большой объем данных.
Входные данные:
prices = [89, 45, 120, 67, 210, 34, 150]
Задача:
1. Реализовать Quick Sort
2. Использовать pivot
3. Отсортировать по возрастанию
Требование:
Pivot — последний элемент массива.
⸻
Задача 3 — Counting Sort для заказов с фиксированным диапазоном
Контекст:
Количество заказов по часам фиксируется от 0 до 24.
Входные данные:
orders_per_hour = [5, 3, 12, 3, 8, 0, 24, 12, 5]
Диапазон значений:
0–24
Задача:
1. Реализовать Counting Sort
2. Отсортировать значения
Цель:
Понять сортировки без сравнений.
⸻
Уровень 2 — Потяжелее (3 задачи)
Задача 4 — Merge Sort для объектов (заказы)
Контекст:
Каждый заказ содержит:
• id
• сумма
Нужно отсортировать по сумме.
Входные данные:
orders = [
(101, 540),
(102, 120),
(103, 800),
(104, 300),
(105, 450)
]
Задача:
1. Реализовать Merge Sort
2. Сортировать по второму элементу кортежа
3. Сохранить структуру данных
⸻
Задача 5 — Quick Sort по прибыли сотрудников
Контекст:
Есть список прибыли сотрудников.
Входные данные:
profits = [3200, 5400, 2100, 7800, 4300, 1200]
Задача:
1. Реализовать Quick Sort
2. Сортировать по убыванию
3. Pivot — средний элемент
⸻
Задача 6 — Heap Sort для рейтингов
Контекст:
Система хранит рейтинги продавцов.
Входные данные:
ratings = [4.5, 3.9, 4.8, 4.1, 3.7, 5.0]
Задача:
1. Реализовать Heap Sort
2. Построить max-heap
3. Отсортировать по возрастанию
Цель:
Понять работу кучи.
⸻
Уровень 3 — Сложно (3 задачи)
Задача 7 — Quick Sort для сложных объектов
Контекст:
Каждый заказ содержит:
• id
• сумма
• количество товаров
Сортировка:
1. По сумме (убывание)
2. При равенстве — по количеству товаров (убывание)
Входные данные:
orders = [
(101, 540, 3),
(102, 120, 1),
(103, 800, 5),
(104, 540, 2),
(105, 450, 4)
]
Задача:
Реализовать Quick Sort с двумя критериями.
⸻
Задача 8 — Merge Sort для логов транзакций
Контекст:
Есть временные метки транзакций. Требуется стабильная сортировка.
Входные данные:
timestamps = [
"2024-05-01 12:45",
"2024-05-01 09:10",
"2024-05-02 08:00",
"2024-04-30 18:30"
]
Задача:
1. Реализовать Merge Sort
2. Отсортировать строки как даты
Цель:
Стабильная сортировка строк.
⸻
Задача 9 — Counting Sort для частоты заказов
Контекст:
Есть оценки удовлетворенности клиентов от 1 до 10.
Входные данные:
ratings = [7, 5, 9, 10, 6, 5, 8, 7, 9, 6]
Диапазон:
1–10
Задача:
1. Реализовать Counting Sort
2. Дополнительно вывести:
• сколько раз встречается каждое значение
⸻
Уровень 4 — Тяжело (1 задача)
Задача 10 — Гибрид Quick + Merge для аналитики заказов
Контекст:
Большая система заказов.
Особенности:
• Маленькие массивы быстрее сортировать Merge
• Большие — Quick
Нужно реализовать гибридную стратегию.
Входные данные:
orders = [
540, 120, 800, 300, 450,
220, 710, 640, 90, 510,
430, 150, 780, 620, 310
]
Задача:
1. Если размер массива < 5 → использовать Merge Sort
2. Иначе → Quick Sort
3. Реализовать переключение алгоритма
4. Отсортировать массив
Цель:
Понимание:
• выбора алгоритма
• комбинированных стратегий
• оптимизации сортировки