Фундаментальная информатика

Сортировка слиянием – это алгоритм сортировки, использующий принцип "разделяй и властвуй". Это быстрее, чем сортировка вставками и сортировка выбором. Сортировка слиянием также является стабильным алгоритмом сортировки, то есть порядок одинаковых элементов на входе и выходе одинаков.

Вот анимация того, как работает сортировка слиянием для входного массива. Сверху вниз происходит деление массива, а снизу вверх — слияние разделенных массивов.

Алгоритм

  1. Разделил входной массив на две половины
  2. Неоднократно вызывает себя до тех пор, пока каждая половина не будет содержать только один элемент
  3. Повторно объединяет две отсортированные половины

Псевдокод

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 является рекурсивной функцией, что означает, что функция будет вызывать сама себя.

Если вы впервые слышите о рекурсивной функции, помните, что функция называется рекурсивной, если она вызывает сама себя.

Каждая рекурсивная функция имеет два свойства или случая:

  1. Базовый случай — Когда функция перестанет вызывать себя
  2. Рекурсивный случай — когда функция будет вызывать сама себя.

Вот код 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)
  • Быстрее, чем быстрая сортировка, когда входной массив или набор данных большой

Недостаток

  • Требует дополнительной памяти, которая не требуется при быстрой сортировке
  • Медленнее по сравнению с другим алгоритмом сортировки для небольших наборов данных. Потому что он проходит весь процесс, даже если массив отсортирован

Дополнительные алгоритмы сортировки:

  1. Сортировка выбором
  2. Сортировка вставками
  3. Быстрая сортировка