Какой алгоритм сортировки реализует Swift для своей стандартной библиотеки?

Мне интересно, как реализована функция sort Swift. Какой алгоритм сортировки он использует - это сортировка слиянием, быстрая сортировка или что-то совершенно другое? Какие гарантии времени/сложности предоставляются этой функцией?

Я не могу найти никаких указаний на то, как это реализовано ни в Интернете, ни в официальной документации.

Ответ 1

Обновление 2: Как мы видим в Sort.swift, sort() теперь использует "модифицированный timsort" в Swift 5. Timsort - это

... гибридный алгоритм стабильной сортировки, полученный из сортировки слиянием и сортировки вставкой...

В худшем случае Timsort берет O (n log n) сравнений, чтобы отсортировать массив из n элементов. В лучшем случае, который происходит, когда входные данные уже отсортированы, он выполняется за линейное время, что означает, что это алгоритм адаптивной сортировки.

Это означает, что sort() является стабильной сортировкой в Swift 5, но это все еще деталь реализации. Документация MutableCollection.sort утверждает, что

Алгоритм сортировки не гарантируется быть стабильным. Стабильная сортировка сохраняет относительный порядок элементов, которые сравниваются равными.

См. Также Является ли sort() стабильным в Swift 5? в форуме Swift:

Алгоритм был только недавно сделан стабильным при подготовке предложения, чтобы сделать его гарантированным как таковой.

Обновление: Swift сейчас с открытым исходным кодом, и в

https://github.com/apple/swift/blob/master/stdlib/public/core/Sort.swift

Можно видеть, что сортировка коллекции выполняется с помощью интросорта с максимальной глубиной рекурсии 2 * floor (log_2 (N)). Он переключается на сортировку вставки для разделов с менее чем 20 элементами или на heapsort, если достигнута глубина рекурсии.

Старый ответ: Определение настраиваемой Comparable структуры и настройка точки останова в <:

struct MyStruct : Comparable {
    let val : Int
}

func ==(x: MyStruct, y: MyStruct) -> Bool {
    println("\(x.val) ==  \(y.val)")
    return x.val == y.val
}
func <(x: MyStruct, y: MyStruct) -> Bool {
    println("\(x.val) < \(y.val)")
    return x.val < y.val // <--- SET BREAKPOINT HERE
}

var array = [MyStruct]()
for _ in 1 ... 30 {
    array.append(MyStruct(val: Int(arc4random_uniform(1000))))
}
sort(&array)

показывает следующую трассировку стека:

(lldb) bt
* thread #1: tid = 0x5a00, 0x00000001001cb806 sort'sort. Swift.Bool + 454 at main.swift:22, queue = 'com.apple.main-thread', stop reason = breakpoint 1.1
  * frame #0: 0x00000001001cb806 sort'sort. Swift.Bool + 454 at main.swift:22
    frame #1: 0x00000001001cb62b sort'protocol witness for Swift._Comparable.(Swift._Comparable.Self.Type)(Swift._Comparable.Self, Swift._Comparable.Self) -> Swift.Bool in conformance sort.MyStruct : Swift._Comparable + 27 at main.swift:20
    frame #2: 0x00000001000f5a98 sort'Swift._partition (inout A, Swift.Range) -> A.Index + 3224
    frame #3: 0x00000001000f756a sort'Swift._introSortImpl (inout A, Swift.Range, Swift.Int) -> () + 2138
    frame #4: 0x00000001000f6c01 sort'Swift._introSort (inout A, Swift.Range) -> () + 1233
    frame #5: 0x00000001000fc47f sort'Swift.sort (inout A) -> () + 607
    frame #6: 0x000000010013ea77 sort'partial apply forwarder for Swift.(sort (inout Swift.Array) -> ()).(closure #1) + 183
    frame #7: 0x000000010013eaf8 sort'partial apply forwarder for reabstraction thunk helper  from @callee_owned (@inout Swift.UnsafeMutableBufferPointer) -> (@unowned ()) to @callee_owned (@inout Swift.UnsafeMutableBufferPointer) -> (@out ()) + 56
    frame #8: 0x0000000100046c4b sort'Swift.Array.withUnsafeMutableBufferPointer (inout Swift.Array)((inout Swift.UnsafeMutableBufferPointer) -> B) -> B + 475
    frame #9: 0x00000001000fc5ad sort'Swift.sort (inout Swift.Array) -> () + 157
    frame #10: 0x00000001001cb465 sort'top_level_code + 1237 at main.swift:29
    frame #11: 0x00000001001cbdca sort'main + 42 at main.swift:0
    frame #12: 0x00007fff8aa9a5fd libdyld.dylib'start + 1

и позже

(lldb) bt
* thread #1: tid = 0x5a00, 0x00000001001cb806 sort'sort. Swift.Bool + 454 at main.swift:22, queue = 'com.apple.main-thread', stop reason = breakpoint 1.1
  * frame #0: 0x00000001001cb806 sort'sort. Swift.Bool + 454 at main.swift:22
    frame #1: 0x00000001001cb62b sort'protocol witness for Swift._Comparable.(Swift._Comparable.Self.Type)(Swift._Comparable.Self, Swift._Comparable.Self) -> Swift.Bool in conformance sort.MyStruct : Swift._Comparable + 27 at main.swift:20
    frame #2: 0x00000001000f449e sort'Swift._insertionSort (inout A, Swift.Range) -> () + 2958
    frame #3: 0x00000001000f730e sort'Swift._introSortImpl (inout A, Swift.Range, Swift.Int) -> () + 1534
    frame #4: 0x00000001000f797d sort'Swift._introSortImpl (inout A, Swift.Range, Swift.Int) -> () + 3181
    frame #5: 0x00000001000f6c01 sort'Swift._introSort (inout A, Swift.Range) -> () + 1233
    frame #6: 0x00000001000fc47f sort'Swift.sort (inout A) -> () + 607
    frame #7: 0x000000010013ea77 sort'partial apply forwarder for Swift.(sort (inout Swift.Array) -> ()).(closure #1) + 183
    frame #8: 0x000000010013eaf8 sort'partial apply forwarder for reabstraction thunk helper  from @callee_owned (@inout Swift.UnsafeMutableBufferPointer) -> (@unowned ()) to @callee_owned (@inout Swift.UnsafeMutableBufferPointer) -> (@out ()) + 56
    frame #9: 0x0000000100046c4b sort'Swift.Array.withUnsafeMutableBufferPointer (inout Swift.Array)((inout Swift.UnsafeMutableBufferPointer) -> B) -> B + 475
    frame #10: 0x00000001000fc5ad sort'Swift.sort (inout Swift.Array) -> () + 157
    frame #11: 0x00000001001cb465 sort'top_level_code + 1237 at main.swift:29
    frame #12: 0x00000001001cbdca sort'main + 42 at main.swift:0
    frame #13: 0x00007fff8aa9a5fd libdyld.dylib'start + 1

Это подтверждает гипотезу ответа Airspeed о том, что интросорт используется в сочетании с сортировкой вставок для меньших диапазонов.

Если в массиве менее 20 элементов, то используется только сортировка вставок. Это может указывать на то, что пороговое значение для переключения с сортировки вставки на сортировку вставки составляет 20.

Конечно, реализация может измениться в будущем.

Ответ 2

Не окончательный ответ, просто догадка - ~~только команда Swift std lib dev может сказать, и они havent~~ (царапины, @martin-r показывает, как вы можете сказать через отладчик! Это гибрид introsort/insertion sort):

Документы для sort не соответствуют сложности. Они утверждают, что он не является стабильным, хотя (т.е. Равные элементы arent гарантированно остаются в своем первоначальном порядке), что указывает на то, что он не является типом слияния (который обычно стабилен).

Theres несколько функций в swift std lib, которые выглядят как theyre там как помощники для других функций в lib. Функция a partition, которая является ключевым строительным блоком для быстрых сортировок. В ранних бета-версиях Swift в дополнение к не-брендовому названию были два вида: quickSort и insertionSort.

Реализация GNU в каталоге std библиотеки С++ использует гибрид introsort (который сам по себе является гибридом быстросортирующего и heapsort) иногда в сочетании с сортировкой вставки. Таким образом, возможно, что эти два варианта были первоначально реализованы как строительные блоки для фактической функции сортировки.

quickSort и insertionSort исчезли в более поздних бета-версиях - если бы сортировка была наилучшим вариантом для обоих, то не было бы одной точки, вызывающей одну из них. partition все еще существует, предположительно, поскольку он полезен как автономная функция.