В предыдущих статьях мы проанализировали несколько довольно простых алгоритмов сортировки. Сегодня мы рассмотрим чуть более сложный алгоритм сортировки под названием Quick Sort. Держитесь крепче, потому что это будет глубокое погружение.
Файлы XCode Playground с реализациями доступны по этой ссылке.
Что такое быстрая сортировка?
Быстрая сортировка - это алгоритм сортировки, основанный на так называемой технике «разделяй и властвуй». Идея, как и в случае с сортировкой в куче, состоит в том, что гораздо проще отсортировать два меньших массива, чем один большой. Для этого в Quick Sort используется так называемый сводный элемент (вскоре я объясню, что такое сводный элемент). Поскольку это довольно сложный алгоритм, давайте сделаем общий обзор того, что мы хотим сделать:
- По определению, массив будет отсортирован, если размер меньше двух элементов. Поэтому мы определим это как наш базовый случай и просто вернемся из функции.
- Если в нашем массиве 2 или более элементов, мы будем искать элемент поворота. В идеале сводный элемент должен быть средним для всех значений. На обычном языке это означает, что массив должен содержать столько же значений, которые меньше или равны элементу сводной таблицы, так и значениям, превышающим этот элемент.
- Поскольку в идеале элемент поворота должен располагаться в середине нашего массива, мы начинаем сравнивать значения в первой половине со значениями, расположенными во второй половине нашего массива. Если мы находим какие-либо значения в первой половине, которые больше, чем наш элемент поворота, мы меняем их на значение во второй половине, которое оказывается меньше или равно элементу поворота. Затем он выполнит два рекурсивных вызова, разделит массив на две части и выполнит те же операции с двумя срезами.
- Обратите внимание: поскольку наш сводный элемент не может быть расположен точно в середине массива, наша реализация должна быть немного гибкой, когда она определяет две «половинки» нашего массива. Эта гибкость предоставит нам свойство, что у неуместного элемента в первой половине всегда будет соответствующий неуместный элемент во второй половине, который нужно заменить.
Это может показаться пугающим, но взгляните на этот эскиз, чтобы увидеть, как будет выполняться один раунд этого обмена (P обозначает элемент поворота, lo и hi обозначают элементы, которые в настоящее время сравниваются для возможного обмена):
В чем сложность быстрой сортировки?
Мы собираемся несколько раз проверить каждый элемент во всем массиве, чтобы выполнить сортировку. Однако, благодаря стратегии Divide and Conquer, нам нужно будет всего лишь просмотреть все элементы log (n) раз, поэтому сложность времени выполнения этого алгоритма составляет O (n * log (п)). Предупреждение: эта сложность предполагает, что элемент поворота на самом деле является элементом, который может быть расположен где-то близко к середине массива. Если нам не удастся выбрать хороший сводный элемент, мы можем разделить массив на «половинки», где одна содержит единственный элемент, а другая - остальные значения. Это приведет к сложности O (n²), что намного хуже.
Давайте углубимся в код
Давайте начнем с определения расширения типа Array и общедоступной функции-оболочки, которая может быть вызвана любым, кто хочет выполнить сортировку:
extension Array where Element: Comparable {
public mutating func quickSort() {
quickSort(&self[...])
}
}
Обертка довольно проста. Это будет сортировка на месте, и мы собираемся использовать класс ArraySlice, чтобы убедиться, что мы всегда работаем с уже выделенной памятью, даже если мы логически разделяем массив на несколько отдельных частей. Теперь давайте посмотрим на метод .quickSort(_:):
private func quickSort(_ array: inout ArraySlice<Element>) {
if array.count < 2 {
return
}
sortPivot(in: &array)
let pivot = partition(&array)
quickSort(&array[array.startIndex..<pivot])
quickSort(&array[pivot + 1..<array.endIndex])
}
Здесь мы определяем наш базовый случай. Если в массиве меньше 2 элементов, его можно считать отсортированным, и мы можем вернуться из этого вызова. Если нет, мы ищем наш сводный элемент, выполняем необходимые перестановки, описанные выше, и делаем два рекурсивных вызова, по одному для каждой новой половины нашего массива. Этот метод не так уж и интересен, потому что в нем нет никакой логики. Давайте посмотрим на метод .sortPivot(in:):
private func sortPivot(in array: inout ArraySlice<Element>) {
let startPoint = array.startIndex
let midPoint = (array.startIndex + array.endIndex) / 2
let endPoint = array.endIndex - 1
if array[startPoint] > array[midPoint] {
array.swapAt(startPoint, midPoint)
}
if array[midPoint] > array[endPoint] {
array.swapAt(midPoint, endPoint)
}
if array[startPoint] > array[midPoint] {
array.swapAt(startPoint, midPoint)
}
}
Этот метод, вероятно, выглядит более сложным, чем есть на самом деле. Чтобы найти элемент поворота, у которого есть хорошие шансы быть близким к среднему значению, мы выбираем первый, последний и средний элемент массива. Выбор этих элементов также улучшает работу алгоритма, когда массив уже близок к сортировке. Затем мы сравниваем их друг с другом и меняем их местами, чтобы они удовлетворяли условию
array [startPoint] ≤ array [midPoint] ≤ array [endPoint].
После этой операции наш сводный элемент будет расположен в середине массива, и мы можем выполнять наши операции обмена. Взгляните на реализацию .partition(_:):
private func partition(_ array: inout ArraySlice<Element>) -> ArraySlice<Element>.Index {
let midPoint = (array.startIndex + array.endIndex) / 2
array.swapAt(midPoint, array.startIndex)
let pivot = array[array.startIndex]
var lower = array.startIndex
var upper = array.endIndex - 1
repeat {
while lower < array.endIndex - 1 && array[lower] <= pivot {
lower += 1
}
while array[upper] > pivot {
upper -= 1
}
if lower < upper {
array.swapAt(lower, upper)
}
} while lower < upper
array.swapAt(array.startIndex, upper)
return upper
}
Теперь может потребоваться несколько прочтений, чтобы действительно понять, потому что здесь есть некоторые условия и ограничения, которые не совсем очевидны. Давайте пройдемся по коду:
Мы вычисляем индекс, в котором расположен наш сводный элемент, после того, как метод .sortPivot(in:) выполнил свою работу. Затем мы меняем местами сводный элемент с первым элементом, чтобы он не мешал остальным свопам, которые мы собираемся выполнить.
Следующим шагом является создание двух индексных переменных, чтобы отслеживать, какие элементы это нужно поменять местами. Переменная lower будет двигаться вверх по массиву и искать любое значение, которое больше, чем наш сводный элемент, переменная upper будет перемещаться по массиву назад и искать элементы, которые меньше или равны нашему сводному элементу. Как только они находят такой элемент, они останавливаются и меняют местами элементы друг с другом. Как только переменные пересекаются или встречаются (lower >= upper), мы знаем, что поменяли местами все элементы, которые нужно поменять местами, и мы также знаем, что переменная upper указывает на то место, где должен находиться наш сводный элемент. Мы меняем элемент поворота на место, а затем возвращаем индекс того места, где он оказался, чтобы мы могли использовать его для разделения нашего массива для рекурсивных вызовов.
Это в целом быстрая сортировка. Как я сказал в начале, это сложный алгоритм, и может потребоваться несколько чтений, чтобы понять, как он работает (я знаю, что это помогло мне). Просто продолжайте и поиграйте с файлами игровых площадок, указанными в верхней части статьи, и скоро все станет на свои места!
На этот раз все! Не стесняйтесь комментировать, если у вас есть вопросы, и подписывайтесь, чтобы получать уведомления о будущих статьях.
Чтобы узнать больше о разработке для iOS, ознакомьтесь с моими предыдущими статьями:
Эта история опубликована в The Startup, крупнейшем предпринимательском издании Medium, за которым следят +431 678 человек.
Подпишитесь, чтобы получать наши главные новости здесь.
