Перейти к содержанию
Приглашаем вас участвовать в развитии русской версии! Подробнее здесь.

# 11.12 Упражнения

## 11.12.1 Вопросы для самопроверки

### 1. Первые итерации сортировки выбором и пузырьком

Дан массив `[4, 2, 5, 1, 3]`. В обоих случаях элементы сортируются по возрастанию.

1. Выполните первые две итерации сортировки выбором, запишите массив после каждой из них и укажите, какие позиции уже определены.
2. Выполните первую итерацию сортировки пузырьком, запишите состояние массива и число обменов, а также укажите, какая позиция уже определена.

Ответ

1. Первые две итерации:

   Итерация | Состояние массива | Пояснение
   --- | --- | ---
   1 | `[1, 2, 5, 4, 3]` | Наименьший элемент 1 меняется местами с первым элементом
   2 | `[1, 2, 5, 4, 3]` | Значение 2 уже находится по индексу 1, обмен не нужен

   Теперь первые две позиции определены, а дальнейший выбор наименьшего элемента выполняется только в `[5, 4, 3]`.

2. Последовательно сравниваются соседние элементы: 4 и 2 меняются местами; 4 и 5 остаются на месте; 5 и 1 меняются местами; 5 и 3 меняются местами. Получается `[2, 4, 1, 3, 5]`, всего 3 обмена. Наибольший элемент 5 переместился в конец массива, поэтому последняя позиция определена.

### 2. Меняется ли взаимный порядок равных элементов

В массиве \([2_a, 2_b, 1]\) значения \(2_a\) и \(2_b\) равны, но нижние индексы отмечают их исходный порядок.

1. Запишите массив после первой итерации сортировки выбором. Изменился ли взаимный порядок \(2_a\) и \(2_b\)?
2. Запишите массив после первой итерации сортировки пузырьком. Изменился ли взаимный порядок \(2_a\) и \(2_b\)?
3. На основании первых двух ответов объясните, чем различаются эти сортировки в сохранении исходного порядка равных элементов.

Ответ

1. На первой итерации сортировка выбором находит наименьший элемент 1 и меняет его местами с первым элементом \(2_a\), поэтому получается \([1, 2_b, 2_a]\). Элемент \(2_a\) переместился за \(2_b\), и их взаимный порядок изменился.

2. Сортировка пузырьком сначала сравнивает \(2_a\) и \(2_b\). Они равны, поэтому обмена нет. Затем \(2_b\) сравнивается с 1 и меняется с ним местами. После первой итерации получается \([2_a, 1, 2_b]\). Элемент \(2_a\) по-прежнему находится перед \(2_b\), их взаимный порядок не изменился.

3. В этом примере сортировка выбором меняет исходный порядок равных элементов. Сортировка пузырьком обменивает соседние элементы, только когда левый больше правого. Равные элементы не меняются местами, поэтому их исходный взаимный порядок сохраняется.

### 3. Сравнение сортировки подсчетом и поразрядной сортировки

Школе нужно упорядочить большое количество номеров учеников, каждый из которых состоит ровно из 8 цифр. Ответьте на вопросы.

1. Сколько итераций потребуется поразрядной сортировке, начинающей с младшего разряда?
2. Почему сортировка подсчетом, использующая весь номер как целое число, подготовит множество неиспользуемых позиций для счетчиков?
3. Какой из двух способов вы выберете для большого количества 8-значных номеров — сортировку подсчетом или поразрядную сортировку? Обоснуйте выбор с учетом первых двух ответов.

Ответ

1. Номер состоит из 8 разрядов, поэтому от младшего до старшего потребуется 8 итераций; на каждой из них элементы распределяются только по цифрам 0–9.

2. Для прямого подсчета пришлось бы выделить позиции для всех возможных 8-значных значений, хотя в действительности используется лишь небольшая их часть. Большинство счетчиков всегда оставалось бы равным 0.

3. Следует выбрать поразрядную сортировку. Она использует свойства «фиксированное число разрядов и только 10 возможных значений каждого разряда» и требует лишь 8 повторений стабильной группировки. Если же использовать весь 8-значный номер как индекс при сортировке подсчетом, пришлось бы выделить счетчики для множества значений, которые никогда не встретятся.

## 11.12.2 Задачи по программированию

### 1. Сортировка массива слиянием

Дан массив целых чисел `nums`. Самостоятельно реализуйте сортировку слиянием, расположите элементы в неубывающем порядке и верните массив. Не используйте встроенную функцию сортировки языка.

Подсказки

1. Интервал длины не более 1 уже упорядочен
2. Разделите интервал в середине на две половины и рекурсивно отсортируйте каждую
3. Слейте два упорядоченных полуинтервала с помощью двух указателей, а затем запишите результат обратно в исходный массив

LeetCode

### 2. Сортировка массива целых чисел подсчетом

Даны массив целых чисел `nums` и неотрицательное целое число \(K\). Каждый элемент массива находится в диапазоне от \(0\) до \(K\).

Реализуйте сортировку подсчетом, запишите результат в `nums` в неубывающем порядке и верните `nums`. Не определяйте порядок элементов с помощью сравнений между ними и не используйте встроенную функцию сортировки языка.

Подсказки

1. Поскольку каждый элемент находится в диапазоне от 0 до K, значение элемента можно напрямую использовать как индекс массива счетчиков
2. При первом обходе nums увеличивайте счетчик в соответствующей позиции на 1
3. Затем переберите массив счетчиков от 0 до K: если значение x встретилось несколько раз, запишите x в nums подряд столько же раз

##### Оставляйте свои идеи, вопросы и предложения в комментариях