Swift 为其标准库实现了什么排序算法?

编程入门行业动态更新时间:2024-10-26 12:23:05

本文介绍了Swift 为其标准库实现了什么排序算法?的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！问题描述

我想知道 Swift 的 sort 函数是如何实现的.它使用哪种排序算法——是归并排序、快速排序还是完全不同的排序?该函数提供的时序/复杂度保证是什么?

无论是在网上还是在官方文档中，我都找不到任何关于它是如何实现的说明.

解决方案

更新 2: 正如我们在 Sort.swift，sort() 现在在 Swift 5 中使用修改后的 timsort".Timsort 是一个

... 混合稳定排序算法，衍生自归并排序和插入排序...

在最坏的情况下，Timsort 需要 O(n log n) 次比较来对 n 个元素的数组进行排序.在最好的情况下，当输入已经排序时，它会在线性时间内运行，这意味着它是一种自适应排序算法.

这意味着 sort() 恰好是 Swift 5 中的稳定排序，但这仍然是一个实现细节.MutableCollection.sort 文档指出

排序算法不保证稳定.稳定排序保留比较相等的元素的相对顺序.

另见在 Swift 5 中 sort() 是否稳定? 在 Swift 论坛中:

该算法最近才变得稳定，以准备一项保证其如此稳定的提案.

更新:Swift 现在是开源的，并且在

github/apple/swift/blob/master/stdlib/public/core/Sort.swift

可以看到使用 introsort 对集合进行排序最大递归深度为 2*floor(log_2(N)).对于少于 20 个元素的分区，它切换到插入排序，或者切换到堆排序如果达到递归深度.

旧答案:定义自定义Comparable结构并在<中设置断点:

struct MyStruct : Comparable {让 val : 整数}func ==(x: MyStruct, y: MyStruct) ->布尔{println("(x.val) == (y.val)")返回 x.val == y.val}func <(x: MyStruct, y: MyStruct) ->布尔{println("(x.val) <(y.val)")返回 x.val <y.val//<--- 在此处设置断点}var 数组 = [MyStruct]()对于 _ 在 1 ... 30 {array.append(MyStruct(val: Int(arc4random_uniform(1000))))}排序(&数组)

显示以下堆栈回溯:

(lldb) bt* 线程 #1:tid = 0x5a00, 0x00000001001cb806 sort`sort.Swift.Bool + 454 at main.swift:22，队列 = 'com.apple.main-thread'，停止原因 = 断点 1.1* 帧 #0: 0x00000001001cb806 sort`sort.Swift.Bool + 454 在 main.swift:22帧 #1:0x00000001001cb62b sort`协议见证 Swift._Comparable.(Swift._Comparable.Self.Type)(Swift._Comparable.Self, Swift._Comparable.Self) -> Swift.Bool 符合 sort.MyStruct : Swift._Comparable+ 27 在 main.swift:20帧 #2:0x00000001000f5a98 sort`Swift._partition (inout A, Swift.Range) -> A.Index + 3224帧 #3:0x00000001000f756a sort`Swift._introSortImpl (inout A, Swift.Range, Swift.Int) -> () + 2138第 4 帧:0x00000001000f6c01 sort`Swift._introSort (inout A, Swift.Range) -> () + 1233第 5 帧:0x00000001000fc47f sort`Swift.sort (inout A) -> () + 607帧 #6:0x000000010013ea77 sort`部分应用转发器为 Swift.(sort (inout Swift.Array) -> ()).(closure #1) + 183帧 #7:0x000000010013eaf8 sort`partial apply forwarder for reabstraction thunk helper from @callee_owned (@inout Swift.UnsafeMutableBufferPointer) -> (@unowned ()) 到 @callee_owned (@inout Swift.UnsafeMutableBufferPointer) -> (@out+ 56帧 #8:0x0000000100046c4b sort`Swift.Array.withUnsafeMutableBufferPointer (inout Swift.Array)((inout Swift.UnsafeMutableBufferPointer) -> B) -> B + 475帧 #9:0x00000001000fc5ad sort`Swift.sort (inout Swift.Array) -> () + 157帧 #10:0x00000001001cb465 sort`top_level_code + 1237 at main.swift:29第 11 帧:0x00000001001cbdca sort`main + 42 at main.swift:0第 12 帧:0x00007fff8aa9a5fd libdyld.dylib`start + 1

以后

(lldb) bt* 线程 #1:tid = 0x5a00, 0x00000001001cb806 sort`sort.Swift.Bool + 454 at main.swift:22，队列 = 'com.apple.main-thread'，停止原因 = 断点 1.1* 帧 #0: 0x00000001001cb806 sort`sort.Swift.Bool + 454 在 main.swift:22帧 #1:0x00000001001cb62b sort`协议见证 Swift._Comparable.(Swift._Comparable.Self.Type)(Swift._Comparable.Self, Swift._Comparable.Self) -> Swift.Bool 符合 sort.MyStruct : Swift._Comparable+ 27 在 main.swift:20帧 #2:0x00000001000f449e sort`Swift._insertionSort (inout A, Swift.Range) -> () + 2958帧 #3:0x00000001000f730e sort`Swift._introSortImpl (inout A, Swift.Range, Swift.Int) -> () + 1534帧 #4:0x00000001000f797d sort`Swift._introSortImpl (inout A, Swift.Range, Swift.Int) -> () + 3181帧 #5:0x00000001000f6c01 sort`Swift._introSort (inout A, Swift.Range) -> () + 1233第 6 帧:0x00000001000fc47f sort`Swift.sort (inout A) -> () + 607帧 #7:0x000000010013ea77 sort`部分应用转发器为 Swift.(sort (inout Swift.Array) -> ()).(closure #1) + 183帧 #8:0x000000010013eaf8 排序`部分应用转发器用于重新抽象 thunk 助手从 @callee_owned (@inout Swift.UnsafeMutableBufferPointer) -> (@unowned ()) 到 @callee_owned (@inout Swift.UnsafeMutableBufferPointer) -> (@out+ 56帧 #9:0x0000000100046c4b sort`Swift.Array.withUnsafeMutableBufferPointer (inout Swift.Array)((inout Swift.UnsafeMutableBufferPointer) -> B) -> B + 475帧 #10: 0x00000001000fc5ad sort`Swift.sort (inout Swift.Array) -> () + 157帧 #11:0x00000001001cb465 sort`top_level_code + 1237 at main.swift:29第 12 帧:0x00000001001cbdca sort`main + 42 at main.swift:0第 13 帧:0x00007fff8aa9a5fd libdyld.dylib`start + 1

这证实了 Airspeed's answer 使用 introsort 的猜想结合插入排序用于较小的范围.

如果数组少于 20 个元素，则似乎只使用插入排序.这可能表明从 introsort 切换到插入排序是 20.

当然，未来的实施可能会发生变化.

I am wondering how Swift's sort function is implemented. Which sorting algorithm does it use—is it a mergesort, quicksort, or something completely different? What are the timing/complexity guarantees provided by this function?

I can't find any indication of how it is implemented either online or in the official documentation.

解决方案

Update 2: As we can see in Sort.swift, sort() now uses a "modified timsort" in Swift 5. Timsort is a

... hybrid stable sorting algorithm, derived from merge sort and insertion sort ...

In the worst case, Timsort takes O(n log n) comparisons to sort an array of n elements. In the best case, which occurs when the input is already sorted, it runs in linear time, meaning that it is an adaptive sorting algorithm.

This means that sort() happens to be a stable sort in Swift 5, but that is still an implementation detail. The MutableCollection.sort documentation states that

The sorting algorithm is not guaranteed to be stable. A stable sort preserves the relative order of elements that compare equal.

See also Is sort() stable in Swift 5? in the Swift forum:

The algorithm was only recently made stable in preparation for a proposal to make it guaranteed as such.

Update: Swift is open source now, and in

github/apple/swift/blob/master/stdlib/public/core/Sort.swift

one can see that sorting a collection is done using introsort with a maximum recursion depth of 2*floor(log_2(N)). It switches to insertion sort for partitions with less than 20 elements, or to heapsort if the recursion depth is reached.

Old answer: Defining a custom Comparable structure and setting in breakpoint in <:

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)

shows the following stack backtrace:

(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

and later

(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

This confirms the conjecture of Airspeed's answer that introsort is used in combination with insertion sort for the smaller ranges.

If the array has less than 20 elements then only insertion sort seems to be used. This could indicate that the threshold for switching from introsort to insertion sort is 20.