TwiddleLab / Код / Алгоритмы в движении

Слияние отсортированных стопок

Урок 6 из 11 · 7 мин · Бесплатно, без аккаунта

Что ты узнаешь

• Чтобы слить две отсортированные стопки, сравнивай только две верхние карты; меньшая уходит.
• Каждое сравнение ставит одну карту, поэтому слияние n карт требует не больше n - 1 сравнений: O(n).
• Когда одна стопка кончается, скопируй остаток другой. Если забыть, карты теряются.

Начать урок

Как идёт урок

1. Два друга ведут каждый отсортированный список времени кругов. Объедини их, быстро.

   Каждая стопка отсортирована, самый быстрый сверху. Нажми на самый быстрый круг из всех 10.

2. Слей две стопки вручную.

   Перетаскивай меньшую верхнюю карту в «Слито». Считай сравнения.

3. Программа сливает с двумя указателями, i и j.

   Перед каждым шагом нажми на список, чья карта следующей пойдёт в result.

4. Слияние.

   Чтобы слить два отсортированных списка, сравнивай элементы под указателями i и j. Меньший идёт в результат, а его указатель сдвигается.

   Каждое сравнение ставит один элемент, поэтому слияние n элементов требует не больше n - 1 сравнений: O(n).

   Когда один список кончается, скопируй остаток другого. Он уже по порядку.

5. Напиши слияние.

   Повторяй цикл, пока в обоих списках есть карты. Потом добавь остатки.

6. Это слияние теряет карты. Запусти его, потом исправь.

   Входят шесть карт. Посчитай, сколько выходит.

7. Спринт слияния.

   Три пары стопок, всё больше. Нажимай на меньшую верхнюю, быстро и без промахов.

8. Стопки из 5 и 7. Какое наибольшее число сравнений может понадобиться слиянию?

   Каждое сравнение отправляет одну карту в результат. Последняя ставится без него, потому что другая стопка уже пуста.

9. Две отсортированные таблицы лидеров по 50. Слить их или отсортировать все 100 с нуля?

   Нажми на более быстрый план. Твоё слияние запустится по-настоящему.

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

Предыдущий урок: O-большое: как растут столбики · Следующий урок: Сортировка слиянием: слить и снова слить · Часть курса: Алгоритмы в движении

Уроки интерактивные и работают на JavaScript. Включи его, чтобы играть.