Сортировка данных - это задача, которая была (и, вероятно, всегда будет) главной заботой компьютеров. Не потому, что сортировка сама по себе очень интересная тема, а потому, что другие алгоритмы полагаются на отсортированные данные для правильного функционирования. Сегодня мы рассмотрим, как реализовать алгоритм сортировки, широко известный как Сортировка кучи, который основан на принципах структуры данных, широко известной как Куча.
Файлы XCode Playground с реализациями доступны по этой ссылке.
Возвращаясь к куче
Куча - это полная и частично упорядоченная двоичная древовидная структура. На языке обычных людей это означает, что он всегда вставляет новые узлы данных как можно левее на самом высоком уровне узлов. Это также означает, что элементы в некотором смысле упорядочены, даже если они не отсортированы.
В этом руководстве мы собираемся использовать Max Heap для реализации алгоритма сортировки, который всегда выполняется за O (n * log (n)) времени. Мы начнем с реализации конкретного класса SortingAlgorithms со статической функцией, которая сортирует ваш массив, а затем перейдем к решению, более ориентированному на протокол.
При использовании максимальной кучи следует понимать три важных момента:
- Он всегда сохраняет самый большой элемент в корне.
- Он поддерживает свойство, согласно которому значение узла всегда больше, чем значение его дочерних узлов (если они есть).
- Куча обычно может быть реализована в виде массива, где родительские узлы и дочерние узлы определенного индекса могут быть вычислены с использованием очень простых математических формул. Это позволит нам реализовать быструю и эффективную сортировку на месте.
Знакомство с кодом
Во-первых, мы собираемся начать с расширения реализации структуры Int в стандартной библиотеке Swift, чтобы абстрагироваться от математических расчетов, необходимых для отслеживания индексов массивов для родительских и дочерних узлов. Это должно выглядеть примерно так:
private extension Int {
var parent: Int {
return (self - 1) / 2
}
var leftChild: Int {
return (self * 2) + 1
}
var rightChild: Int {
return (self * 2) + 2
}
}
Эта реализация позволяет вычислять индексы, вызывая вычисляемое свойство, вместо того, чтобы помещать математику прямо в код. Главный выигрыш - читаемость. Также обратите внимание, что это частное расширение, то есть оно не повлияет на структуру Int в целом, а будет доступно только в рамках этого файла.
Теперь давайте разберем разные этапы, на которых будет происходить этот вид.
Во-первых, мы собираемся создать Max Heap из нашего массива. Используя тот факт, что все новые элементы вставляются в конец кучи, а затем меняются местами, мы можем имитировать вставку с помощью простого цикла for. Мы начнем с того, что представим, что в нашем массиве всего два элемента, «насыпь» эти два элемента в кучу, и для каждой итерации в нашем цикле мы будем делать вид, что новый элемент был только что вставлен, и повторно скопировать оттуда. Это будет выглядеть примерно так:
После выполнения этой операции массив не будет выглядеть особенно отсортированным. На самом деле, это будет выглядеть так, как будто мы сделали еще хуже. Это связано с тем, как мы используем массив для хранения узлов дерева. Взгляните на это изображение до / после:
Похоже, мы просто перемешали элементы. Но на самом деле мы только что установили свойство, которое собираемся использовать для завершения сортировки.
Взяв первый элемент и заменив его последним элементом в массиве, мы получим самый большой элемент на последнем месте. Если мы затем сделаем вид, что массив на один элемент меньше, чем был раньше, и перекомпилируем меньший массив, мы снова получим самый большой элемент в первом индексе. Это означает, что мы можем снова выполнить ту же операцию, и в конечном итоге мы получим полностью отсортированный массив. Гениально!
Код нашего .heapSort(_:) метода выглядит следующим образом, включая создание и сжатие кучи.
class SortingAlgorithms {
private init() {}
public static func heapSort<DataType: Comparable>(_ array: inout [DataType]) {
if array.count < 2 { return }
buildHeap(&array)
shrinkHeap(&array)
}
private static func buildHeap<DataType: Comparable>(_ array: inout [DataType]) {
for index in 1..<array.count {
var child = index
var parent = child.parent
while child > 0 && array[child] > array[parent] {
swap(child, with: parent, in: &array)
child = parent
parent = child.parent
}
}
}
private static func shrinkHeap<DataType: Comparable>(_ array: inout [DataType]) {
for index in stride(from: array.count - 1, to: 0, by: -1) {
swap(0, with: index, in: &array)
var parent = 0
var leftChild = parent.leftChild
var rightChild = parent.rightChild
while parent < index {
var maxChild = -1
if leftChild < index {
maxChild = leftChild
} else {
break
}
if rightChild < index && array[rightChild] > array[maxChild] {
maxChild = rightChild
}
guard array[maxChild] > array[parent] else { break }
swap(parent, with: maxChild, in: &array)
parent = maxChild
leftChild = parent.leftChild
rightChild = parent.rightChild
}
}
}
private static func swap<DataType: Comparable>(_ firstIndex: Int, with secondIndex: Int, in array: inout [DataType]) {
let temp = array[firstIndex]
array[firstIndex] = array[secondIndex]
array[secondIndex] = temp
}
}
Идеально! Это именно то, что мы хотим! Но… можем ли мы сделать его чище?
Протокол-ориентированный подход
Расширяя тип Array для сопоставимых типов элементов, мы получаем несколько преимуществ. Во-первых, нам нужно меньше кода, но основной выигрыш в том, что мы сможем вызывать метод непосредственно для одного из наших объектов, поэтому вместо этого:
SortingAlgorithms.heapSort(&myArray)
Мы сможем это сделать:
myArray.heapSort()
Это намного чище, и компилятор даже не покажет нам возможность вызвать .heapSort() для массива, элементы которого не соответствуют протоколу Comparable.
public extension Array where Element: Comparable {
public mutating func heapSort() {
buildHeap()
shrinkHeap()
}
private mutating func buildHeap() {
for index in 1..<self.count {
var child = index
var parent = child.parent
while child > 0 && self[child] > self[parent] {
swapAt(child, parent)
child = parent
parent = child.parent
}
}
}
private mutating func shrinkHeap() {
for index in stride(from: self.count - 1, to: 0, by: -1) {
swapAt(0, index)
var parent = 0
var leftChild = parent.leftChild
var rightChild = parent.rightChild
while parent < index {
var maxChild = -1
if leftChild < index {
maxChild = leftChild
} else {
break
}
if rightChild < index && self[rightChild] > self[maxChild] {
maxChild = rightChild
}
guard self[maxChild] > self[parent] else { break }
swapAt(parent, maxChild)
parent = maxChild
leftChild = parent.leftChild
rightChild = parent.rightChild
}
}
}
}
На этот раз все! Не стесняйтесь комментировать, если у вас есть вопросы, и подписывайтесь, чтобы получать уведомления о будущих статьях.
Чтобы узнать больше о разработке для iOS, ознакомьтесь с моими предыдущими статьями:
