11.12 Упражнения¶
11.12.1 Вопросы для самопроверки¶
1. Первые итерации сортировки выбором и пузырьком¶
Дан массив [4, 2, 5, 1, 3]. В обоих случаях элементы сортируются по возрастанию.
- Выполните первые две итерации сортировки выбором, запишите массив после каждой из них и укажите, какие позиции уже определены.
- Выполните первую итерацию сортировки пузырьком, запишите состояние массива и число обменов, а также укажите, какая позиция уже определена.
Ответ
-
Первые две итерации:
Итерация Состояние массива Пояснение 1 [1, 2, 5, 4, 3]Наименьший элемент 1 меняется местами с первым элементом 2 [1, 2, 5, 4, 3]Значение 2 уже находится по индексу 1, обмен не нужен Теперь первые две позиции определены, а дальнейший выбор наименьшего элемента выполняется только в
[5, 4, 3]. -
Последовательно сравниваются соседние элементы: 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\) равны, но нижние индексы отмечают их исходный порядок.
- Запишите массив после первой итерации сортировки выбором. Изменился ли взаимный порядок \(2_a\) и \(2_b\)?
- Запишите массив после первой итерации сортировки пузырьком. Изменился ли взаимный порядок \(2_a\) и \(2_b\)?
- На основании первых двух ответов объясните, чем различаются эти сортировки в сохранении исходного порядка равных элементов.
Ответ
-
На первой итерации сортировка выбором находит наименьший элемент 1 и меняет его местами с первым элементом \(2_a\), поэтому получается \([1, 2_b, 2_a]\). Элемент \(2_a\) переместился за \(2_b\), и их взаимный порядок изменился.
-
Сортировка пузырьком сначала сравнивает \(2_a\) и \(2_b\). Они равны, поэтому обмена нет. Затем \(2_b\) сравнивается с 1 и меняется с ним местами. После первой итерации получается \([2_a, 1, 2_b]\). Элемент \(2_a\) по-прежнему находится перед \(2_b\), их взаимный порядок не изменился.
-
В этом примере сортировка выбором меняет исходный порядок равных элементов. Сортировка пузырьком обменивает соседние элементы, только когда левый больше правого. Равные элементы не меняются местами, поэтому их исходный взаимный порядок сохраняется.
3. Сравнение сортировки подсчетом и поразрядной сортировки¶
Школе нужно упорядочить большое количество номеров учеников, каждый из которых состоит ровно из 8 цифр. Ответьте на вопросы.
- Сколько итераций потребуется поразрядной сортировке, начинающей с младшего разряда?
- Почему сортировка подсчетом, использующая весь номер как целое число, подготовит множество неиспользуемых позиций для счетчиков?
- Какой из двух способов вы выберете для большого количества 8-значных номеров — сортировку подсчетом или поразрядную сортировку? Обоснуйте выбор с учетом первых двух ответов.
Ответ
-
Номер состоит из 8 разрядов, поэтому от младшего до старшего потребуется 8 итераций; на каждой из них элементы распределяются только по цифрам 0–9.
-
Для прямого подсчета пришлось бы выделить позиции для всех возможных 8-значных значений, хотя в действительности используется лишь небольшая их часть. Большинство счетчиков всегда оставалось бы равным 0.
-
Следует выбрать поразрядную сортировку. Она использует свойства «фиксированное число разрядов и только 10 возможных значений каждого разряда» и требует лишь 8 повторений стабильной группировки. Если же использовать весь 8-значный номер как индекс при сортировке подсчетом, пришлось бы выделить счетчики для множества значений, которые никогда не встретятся.
11.12.2 Задачи по программированию¶
1. Сортировка массива слиянием¶
Дан массив целых чисел nums. Самостоятельно реализуйте сортировку слиянием, расположите элементы в неубывающем порядке и верните массив. Не используйте встроенную функцию сортировки языка.
Подсказки
- Интервал длины не более 1 уже упорядочен
- Разделите интервал в середине на две половины и рекурсивно отсортируйте каждую
- Слейте два упорядоченных полуинтервала с помощью двух указателей, а затем запишите результат обратно в исходный массив
2. Сортировка массива целых чисел подсчетом¶
Даны массив целых чисел nums и неотрицательное целое число \(K\). Каждый элемент массива находится в диапазоне от \(0\) до \(K\).
Реализуйте сортировку подсчетом, запишите результат в nums в неубывающем порядке и верните nums.
Не определяйте порядок элементов с помощью сравнений между ними и не используйте встроенную функцию сортировки языка.
Подсказки
- Поскольку каждый элемент находится в диапазоне от 0 до K, значение элемента можно напрямую использовать как индекс массива счетчиков
- При первом обходе nums увеличивайте счетчик в соответствующей позиции на 1
- Затем переберите массив счетчиков от 0 до K: если значение x встретилось несколько раз, запишите x в nums подряд столько же раз