Фундаментальная информатика
Сортировка слиянием – это алгоритм сортировки, использующий принцип "разделяй и властвуй". Это быстрее, чем сортировка вставками и сортировка выбором. Сортировка слиянием также является стабильным алгоритмом сортировки, то есть порядок одинаковых элементов на входе и выходе одинаков.
Вот анимация того, как работает сортировка слиянием для входного массива. Сверху вниз происходит деление массива, а снизу вверх — слияние разделенных массивов.
Алгоритм
- Разделил входной массив на две половины
- Неоднократно вызывает себя до тех пор, пока каждая половина не будет содержать только один элемент
- Повторно объединяет две отсортированные половины
Псевдокод
mergeSort(arr[]) If arr.size() >= 2 1. Find the middle point to divide the array into two halves: mid = arr.size()/2 2. Call mergeSort for first half: firstHalf = mergeSort(arr[0..<mid]) 3. Call mergeSort for second half: secondHalf = mergeSort(arr[mid..<arr.size()]) 4. Merge the two halves sorted in step 2 and 3: return merge(firstHalf, secondHalf)
Здесь я расскажу о пошаговом процессе реализации сортировки слиянием в Swift.
Мы определим две функции:
1. merge()
2. mergeSort()
1. Создайте функцию, которая принимает два входных массива и возвращает отсортированный массив.
Итак, здесь я определил функцию merge
, которая будет принимать два массива и возвращать новый массив, отсортированный в порядке возрастания.
- Первый цикл
while
, строки 6–15 гарантирует, что цикл продолжится, если иi
, иj
находятся на границеarrA
иarrB.
. Он находит меньший элемент из обоих массивов и добавляетmergedArr.
- Второй цикл
while
, строки 17–20 гарантирует, что после завершения первого циклаwhile
, если вarrA
есть какие-либо оставшиеся элементы, он добавит эти элементы вmergedArr.
- Третий цикл
while
, строки 22–25 работает так же, как второй циклwhile
, но дляarrB.
- Наконец, эта
merge
функция возвращает отсортированный массив, которыйmergedArr
Вы должны понимать эту
merge
функцию. Попробуйте передать разные размеры массивов для отладки и выяснить, как это работает.
2. Создайте функцию, которая многократно делит массив пополам и объединяет
Давайте определим функциюmergeSort
, которая принимает массив в качестве входных данных, многократно делит половину размера массива и объединяет половинки. Эта mergeSort
является рекурсивной функцией, что означает, что функция будет вызывать сама себя.
Если вы впервые слышите о рекурсивной функции, помните, что функция называется рекурсивной, если она вызывает сама себя.
Каждая рекурсивная функция имеет два свойства или случая:
- Базовый случай — Когда функция перестанет вызывать себя
- Рекурсивный случай — когда функция будет вызывать сама себя.
Вот код mergeSort
- Выражение
guard
является базовым случаем этой рекурсивной функции, которая гарантирует, что еслиarr
не содержит двух или более элементов; он возвращаетarr
без дальнейшей обработки. Итак, еслиarr=[4]
, он просто вернет массив[4].
- Когда оператор
guard
не прошел, он найдет среднюю точку входного массиваmid.
- Затем
mergeSort
вызываетсядля первой половины входного массива, который0..<mid.
помните, в Swift, когда вы используете оператор диапазона в массивеarr[0..<mid]
, он вернетArraySlice
объект, который нужен быть брошенным наArray.
Таким образом, вы видите,Array(arr[0..<mid])).
- Снова вызывается
mergeSort
для второй половины входного массива,то естьmid..<arr.count.
- Наконец, вызывается функция
merge
для объединения массивовfirstHalf
иsecondHalf
и возврата результата.
Полный алгоритм сортировки слиянием
[1, 2, 3, 4, 10, 20, 40, 68, 100]
Если вам все еще трудно понять, попробуйте изучить следующий рисунок.
Красные цвета — это когда mergeSort
многократно делит входные массивы на две половины.
Зеленые цвета — это когда происходит слияние.
Алгоритм анализа
- Время: O(n log n) —где n — количество элементов в массиве. Это лучший, худший и средний случай алгоритма сортировки слиянием.
Поскольку сортировка слиянием является рекурсивным алгоритмом, следующее рекуррентное соотношение может выражать временную сложность.
T(n) = 2T(n/2) + e(n)
Если вы хотите понять, как анализировать это отношение, вы можете изучить основную теорему.
- Пробел: O(n) — где n — количество элементов в массиве. Технически это O(n) + O(log n), где O(log n) — высота стека рекурсии.
Приложения
- Предпочтительно сортировать связанный список за время O (n log n)
- Быстрее, чем быстрая сортировка, когда входной массив или набор данных большой
Недостаток
- Требует дополнительной памяти, которая не требуется при быстрой сортировке
- Медленнее по сравнению с другим алгоритмом сортировки для небольших наборов данных. Потому что он проходит весь процесс, даже если массив отсортирован