Примечание:
Сортировка пузырьком: выполняется некоторое количество проходов по массиву — начиная от начала массива, перебираются пары соседних элементов массива. Если 1-й элемент пары больше (в случае сортировки по возрастанию; в случае сортировки по убыванию – меньше) 2-го, элементы переставляются (выполняется обмен). Пары элементов массива перебираются (проходы по массиву повторяются) либо n-1 раз (где n – число элементов массива), либо до тех пор, пока на очередном проходе не обнаружится, что более не требуется выполнять перестановки (обмены) (массив отсортирован).
При каждом проходе алгоритма по внутреннему циклу очередной наибольший (в случае сортировки по возрастанию; в случае сортировки по убыванию – наименьший) элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом» (в случае сортировки по возрастанию; в случае сортировки по убыванию –
наименьшим), а наименьший (в случае сортировки по возрастанию; в случае сортировки по убыванию – наибольший) элемент перемещается на одну позицию к началу массива.
Сортировка слиянием работает по следующему принципу:
1. Если в рассматриваемом массиве один элемент, то он уже отсортирован — алгоритм завершает работу.
2. Иначе массив разбивается на две части, которые сортируются рекурсивно (т.е. на каждой из частей выполняется описанный алгоритм сортировки слиянием).
3. После сортировки двух частей массива к ним применяется процедура слияния, которая по двум отсортированным частям получает исходный отсортированный массив. В рамках процедуры слияния сравниваются элементы сливаемых массивов (начиная с начала) и меньший (в случае сортировки по возрастанию) из них записываем в финальный. И затем, в массиве у которого оказался меньший (в случае сортировки по возрастанию) элемент, переходим к следующему элементу и сравниваем теперь его. В конце, если один из массивов закончился, мы просто дописываем в финальный другой массив. После мы наш финальный массив записываем заместо двух исходных и
получаем отсортированный участок. С точки зрения исходного массива данная операция атомарна, то есть не имеет промежуточных этапов.
Пример работы сортировки слиянием:
1. [4 3 1 6 5] – исходный массив
2. [[4 3 1][6 5]] – разделение массивов
3. [[[4 3][1]][6 5]] – самый первый неотсортированный подмассив разделяется
4. [[[4][3][1]][6 5]] – самый первый неотсортированный подмассив разделяется
5. [[3 4][1][6 5]] – производится слияние первых двух одноэлементных массивов. Порядок элементов изменился – шаг 1
6. [[1 3 4][6 5]] – производится слияние первых двух отсортированных массивов (результата слияния и
одноэлементного). Порядок изменился – шаг 2.
7. [[1 3 4][6][5]] – неотсортированный подмассив разделяется
8. [[1 3 4][5 6]] – производится слияние одноэлементных подмассивов. Порядок изменился – шаг 3
9. [1 3 4 5 6] – производится слияние подмассивов. Порядок элементов не изменился – таким образом, было 3 шага.
Сегодня на спецкурсе по олимпиадному программированию Илья узнал про два алгоритма сортировки: сортировку пузырьком и сортировку слиянием. Илья стал изучать, как эти сортировки работают на частично отсортированных массивах.
Особенно его интересует, какая из сортировок занимает меньше шагов. Шагом Илья называет изменение порядка элементов массива в ходе работы алгоритма. Например, в сортировке пузырьком на массиве [4 2 1 3] по мнению Ильи 4 шага:
1. [4 2 1 3] -> [2 4 1 3]
2. [2 4 1 3] -> [2 1 4 3]
3. [2 1 4 3] -> [2 1 3 4]
4. [2 1 3 4] -> [1 2 3 4]
А в сортировке слиянием на массиве [4 2 3 1] 3 шага:
1. [4 2 3 1] -> [2 4 3 1]
2. [2 4 3 1] -> [2 4 1 3]
3. [2 4 1 3] -> [1 2 3 4]
Помогите Илье определить, какая сортировка сделает меньше шагов на массиве [1 2 3 … 127 128 256 255 … 130 129], состоящем из двух частей – в первой половине натуральные числа от 1 до 128 отсортированы по возрастанию, во второй – числа от 129 до 256 отсортированы по убыванию (таким образом, всего в массиве 256 элементов). В ответе укажите два числа – количество шагов при сортировке массива пузырьком и число шагов при сортировке слиянием.