Swift排序算法实现

Question

不幸的是我在互联网上找不到任何东西,虽然我确信它可以找到 - 我想知道Swift的sort算法是如何实现的.它是使用mergesort还是quicksort还是完全不同的东西？

是否有文档的任何部分可以建议使用哪种算法？

Answer 1

更新2:正如我们在此提交中所看到的,introsort已被Swift 5的"modified timsort"取代.

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

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

人们可以看到,排序的集合是使用进行内省排序 具有最大递归深度2*地板(log_2(N)).它切换到少于20个元素的分区的插入排序,或者如果达到递归深度则切换到heapsort.

旧答案:在以下位置定义自定义sort()结构并设置断点sort():

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的答案猜想,即对于较小的范围,introsort与插入排序组合使用.

如果数组少于20个元素,那么似乎只使用插入排序.这可能表示从introsort切换到插入排序的阈值是20.

当然,实施可能会在未来发生变化.

Answer 2

不是一个明确的答案,只是猜测 - 只有Swift标准的lib开发团队可以告诉他们没有(从头开始,@ martin-r显示你如何通过调试器告诉它!它是一个混合的introsort /插入排序):

这些文档sort并未说明复杂性.他们确实表示它不稳定(即不保证相同的元素保持其原始顺序),这表明它不是合并排序(通常是稳定的).

Swift std lib中有几个函数看起来像是作为lib中其他函数的帮助器.有一个partition功能,这是快速排序的关键构建块.在非常早期的Swift测试版中,除了非品牌名称之外,过去常常有两种类型:quickSort和insertionSort.

C++ std库排序的GNU实现使用了introsort(它本身就是quicksort和heapsort的混合体)的混合体,有时与插入排序相结合.因此,这两个变体最初可能被实现为实际排序功能的构建块.

quickSort并且insertionSort在后来的测试版中消失了 - 如果排序是两者的最佳情况混合,那么就没有必要调用其中一个.partition仍然存在,大概是因为它作为一个独立的功能很有用.