| //===--- IntroSort.swift --------------------------------------*- swift -*-===// |
| // |
| // This source file is part of the Swift.org open source project |
| // |
| // Copyright (c) 2014 - 2018 Apple Inc. and the Swift project authors |
| // Licensed under Apache License v2.0 with Runtime Library Exception |
| // |
| // See https://swift.org/LICENSE.txt for license information |
| // See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors |
| // |
| //===----------------------------------------------------------------------===// |
| // RUN: %empty-directory(%t) |
| // RUN: %target-build-swift -g -Onone -DUSE_STDLIBUNITTEST %s -o %t/a.out |
| // RUN: %target-codesign %t/a.out |
| // RUN: %target-run %t/a.out |
| // REQUIRES: executable_test |
| |
| // Note: This introsort was the standard library's sort algorithm until Swift 5. |
| |
| import Swift |
| import StdlibUnittest |
| |
| extension MutableCollection { |
| /// Sorts the elements at `elements[a]`, `elements[b]`, and `elements[c]`. |
| /// Stable. |
| /// |
| /// The indices passed as `a`, `b`, and `c` do not need to be consecutive, but |
| /// must be in strict increasing order. |
| /// |
| /// - Precondition: `a < b && b < c` |
| /// - Postcondition: `self[a] <= self[b] && self[b] <= self[c]` |
| @inlinable |
| public // @testable |
| mutating func _sort3( |
| _ a: Index, _ b: Index, _ c: Index, |
| by areInIncreasingOrder: (Element, Element) throws -> Bool |
| ) rethrows { |
| // There are thirteen possible permutations for the original ordering of |
| // the elements at indices `a`, `b`, and `c`. The comments in the code below |
| // show the relative ordering of the three elements using a three-digit |
| // number as shorthand for the position and comparative relationship of |
| // each element. For example, "312" indicates that the element at `a` is the |
| // largest of the three, the element at `b` is the smallest, and the element |
| // at `c` is the median. This hypothetical input array has a 312 ordering for |
| // `a`, `b`, and `c`: |
| // |
| // [ 7, 4, 3, 9, 2, 0, 3, 7, 6, 5 ] |
| // ^ ^ ^ |
| // a b c |
| // |
| // - If each of the three elements is distinct, they could be ordered as any |
| // of the permutations of 1, 2, and 3: 123, 132, 213, 231, 312, or 321. |
| // - If two elements are equivalent and one is distinct, they could be |
| // ordered as any permutation of 1, 1, and 2 or 1, 2, and 2: 112, 121, 211, |
| // 122, 212, or 221. |
| // - If all three elements are equivalent, they are already in order: 111. |
| |
| switch try (areInIncreasingOrder(self[b], self[a]), |
| areInIncreasingOrder(self[c], self[b])) { |
| case (false, false): |
| // 0 swaps: 123, 112, 122, 111 |
| break |
| |
| case (true, true): |
| // 1 swap: 321 |
| // swap(a, c): 312->123 |
| swapAt(a, c) |
| |
| case (true, false): |
| // 1 swap: 213, 212 --- 2 swaps: 312, 211 |
| // swap(a, b): 213->123, 212->122, 312->132, 211->121 |
| swapAt(a, b) |
| |
| if try areInIncreasingOrder(self[c], self[b]) { |
| // 132 (started as 312), 121 (started as 211) |
| // swap(b, c): 132->123, 121->112 |
| swapAt(b, c) |
| } |
| |
| case (false, true): |
| // 1 swap: 132, 121 --- 2 swaps: 231, 221 |
| // swap(b, c): 132->123, 121->112, 231->213, 221->212 |
| swapAt(b, c) |
| |
| if try areInIncreasingOrder(self[b], self[a]) { |
| // 213 (started as 231), 212 (started as 221) |
| // swap(a, b): 213->123, 212->122 |
| swapAt(a, b) |
| } |
| } |
| } |
| } |
| |
| extension MutableCollection where Self: RandomAccessCollection { |
| /// Reorders the collection and returns an index `p` such that every element |
| /// in `range.lowerBound..<p` is less than every element in |
| /// `p..<range.upperBound`. |
| /// |
| /// - Precondition: The count of `range` must be >= 3 i.e. |
| /// `distance(from: range.lowerBound, to: range.upperBound) >= 3` |
| @inlinable |
| internal mutating func _partition( |
| within range: Range<Index>, |
| by areInIncreasingOrder: (Element, Element) throws -> Bool |
| ) rethrows -> Index { |
| var lo = range.lowerBound |
| var hi = index(before: range.upperBound) |
| |
| // Sort the first, middle, and last elements, then use the middle value |
| // as the pivot for the partition. |
| let half = distance(from: lo, to: hi) / 2 |
| let mid = index(lo, offsetBy: half) |
| try _sort3(lo, mid, hi, by: areInIncreasingOrder) |
| |
| // FIXME: Stashing the pivot element instead of using the index won't work |
| // for move-only types. |
| let pivot = self[mid] |
| |
| // Loop invariants: |
| // * lo < hi |
| // * self[i] < pivot, for i in range.lowerBound..<lo |
| // * pivot <= self[i] for i in hi..<range.upperBound |
| Loop: while true { |
| FindLo: do { |
| formIndex(after: &lo) |
| while lo != hi { |
| if try !areInIncreasingOrder(self[lo], pivot) { break FindLo } |
| formIndex(after: &lo) |
| } |
| break Loop |
| } |
| |
| FindHi: do { |
| formIndex(before: &hi) |
| while hi != lo { |
| if try areInIncreasingOrder(self[hi], pivot) { break FindHi } |
| formIndex(before: &hi) |
| } |
| break Loop |
| } |
| |
| swapAt(lo, hi) |
| } |
| |
| return lo |
| } |
| |
| @inlinable |
| public // @testable |
| mutating func _introSort( |
| within range: Range<Index>, |
| by areInIncreasingOrder: (Element, Element) throws -> Bool |
| ) rethrows { |
| |
| let n = distance(from: range.lowerBound, to: range.upperBound) |
| guard n > 1 else { return } |
| |
| // Set max recursion depth to 2*floor(log(N)), as suggested in the introsort |
| // paper: http://www.cs.rpi.edu/~musser/gp/introsort.ps |
| let depthLimit = 2 * n._binaryLogarithm() |
| try _introSortImpl( |
| within: range, |
| by: areInIncreasingOrder, |
| depthLimit: depthLimit) |
| } |
| |
| @inlinable |
| internal mutating func _introSortImpl( |
| within range: Range<Index>, |
| by areInIncreasingOrder: (Element, Element) throws -> Bool, |
| depthLimit: Int |
| ) rethrows { |
| |
| // Insertion sort is better at handling smaller regions. |
| if distance(from: range.lowerBound, to: range.upperBound) < 20 { |
| try _insertionSort(within: range, by: areInIncreasingOrder) |
| } else if depthLimit == 0 { |
| try _heapSort(within: range, by: areInIncreasingOrder) |
| } else { |
| // Partition and sort. |
| // We don't check the depthLimit variable for underflow because this |
| // variable is always greater than zero (see check above). |
| let partIdx = try _partition(within: range, by: areInIncreasingOrder) |
| try _introSortImpl( |
| within: range.lowerBound..<partIdx, |
| by: areInIncreasingOrder, |
| depthLimit: depthLimit &- 1) |
| try _introSortImpl( |
| within: partIdx..<range.upperBound, |
| by: areInIncreasingOrder, |
| depthLimit: depthLimit &- 1) |
| } |
| } |
| |
| @inlinable |
| internal mutating func _siftDown( |
| _ idx: Index, |
| within range: Range<Index>, |
| by areInIncreasingOrder: (Element, Element) throws -> Bool |
| ) rethrows { |
| var idx = idx |
| var countToIndex = distance(from: range.lowerBound, to: idx) |
| var countFromIndex = distance(from: idx, to: range.upperBound) |
| // Check if left child is within bounds. If not, stop iterating, because |
| // there are no children of the given node in the heap. |
| while countToIndex + 1 < countFromIndex { |
| let left = index(idx, offsetBy: countToIndex + 1) |
| var largest = idx |
| if try areInIncreasingOrder(self[largest], self[left]) { |
| largest = left |
| } |
| // Check if right child is also within bounds before trying to examine it. |
| if countToIndex + 2 < countFromIndex { |
| let right = index(after: left) |
| if try areInIncreasingOrder(self[largest], self[right]) { |
| largest = right |
| } |
| } |
| // If a child is bigger than the current node, swap them and continue |
| // sifting down. |
| if largest != idx { |
| swapAt(idx, largest) |
| idx = largest |
| countToIndex = distance(from: range.lowerBound, to: idx) |
| countFromIndex = distance(from: idx, to: range.upperBound) |
| } else { |
| break |
| } |
| } |
| } |
| |
| @inlinable |
| internal mutating func _heapify( |
| within range: Range<Index>, |
| by areInIncreasingOrder: (Element, Element) throws -> Bool |
| ) rethrows { |
| // Here we build a heap starting from the lowest nodes and moving to the |
| // root. On every step we sift down the current node to obey the max-heap |
| // property: |
| // parent >= max(leftChild, rightChild) |
| // |
| // We skip the rightmost half of the array, because these nodes don't have |
| // any children. |
| let root = range.lowerBound |
| let half = distance(from: range.lowerBound, to: range.upperBound) / 2 |
| var node = index(root, offsetBy: half) |
| |
| while node != root { |
| formIndex(before: &node) |
| try _siftDown(node, within: range, by: areInIncreasingOrder) |
| } |
| } |
| |
| @inlinable |
| public // @testable |
| mutating func _heapSort( |
| within range: Range<Index>, |
| by areInIncreasingOrder: (Element, Element) throws -> Bool |
| ) rethrows { |
| var hi = range.upperBound |
| let lo = range.lowerBound |
| try _heapify(within: range, by: areInIncreasingOrder) |
| formIndex(before: &hi) |
| while hi != lo { |
| swapAt(lo, hi) |
| try _siftDown(lo, within: lo..<hi, by: areInIncreasingOrder) |
| formIndex(before: &hi) |
| } |
| } |
| } |
| |
| //===--- Tests ------------------------------------------------------------===// |
| //===----------------------------------------------------------------------===// |
| |
| var suite = TestSuite("IntroSort") |
| |
| // The routine is based on http://www.cs.dartmouth.edu/~doug/mdmspe.pdf |
| func makeQSortKiller(_ len: Int) -> [Int] { |
| var candidate: Int = 0 |
| var keys = [Int: Int]() |
| func Compare(_ x: Int, y : Int) -> Bool { |
| if keys[x] == nil && keys[y] == nil { |
| if (x == candidate) { |
| keys[x] = keys.count |
| } else { |
| keys[y] = keys.count |
| } |
| } |
| if keys[x] == nil { |
| candidate = x |
| return true |
| } |
| if keys[y] == nil { |
| candidate = y |
| return false |
| } |
| return keys[x]! > keys[y]! |
| } |
| |
| var ary = [Int](repeating: 0, count: len) |
| var ret = [Int](repeating: 0, count: len) |
| for i in 0..<len { ary[i] = i } |
| ary = ary.sorted(by: Compare) |
| for i in 0..<len { |
| ret[ary[i]] = i |
| } |
| return ret |
| } |
| |
| suite.test("sorted/complexity") { |
| var ary: [Int] = [] |
| |
| // Check performance of sorting an array of repeating values. |
| var comparisons_100 = 0 |
| ary = Array(repeating: 0, count: 100) |
| ary._introSort(within: 0..<ary.count) { comparisons_100 += 1; return $0 < $1 } |
| var comparisons_1000 = 0 |
| ary = Array(repeating: 0, count: 1000) |
| ary._introSort(within: 0..<ary.count) { comparisons_1000 += 1; return $0 < $1 } |
| expectTrue(comparisons_1000/comparisons_100 < 20) |
| |
| // Try to construct 'bad' case for quicksort, on which the algorithm |
| // goes quadratic. |
| comparisons_100 = 0 |
| ary = makeQSortKiller(100) |
| ary._introSort(within: 0..<ary.count) { comparisons_100 += 1; return $0 < $1 } |
| comparisons_1000 = 0 |
| ary = makeQSortKiller(1000) |
| ary._introSort(within: 0..<ary.count) { comparisons_1000 += 1; return $0 < $1 } |
| expectTrue(comparisons_1000/comparisons_100 < 20) |
| } |
| |
| suite.test("sort3/simple") |
| .forEach(in: [ |
| [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1] |
| ]) { |
| var input = $0 |
| input._sort3(0, 1, 2, by: <) |
| expectEqual([1, 2, 3], input) |
| } |
| |
| func isSorted<T>(_ a: [T], by areInIncreasingOrder: (T, T) -> Bool) -> Bool { |
| return !zip(a.dropFirst(), a).contains(where: areInIncreasingOrder) |
| } |
| |
| suite.test("sort3/stable") |
| .forEach(in: [ |
| [1, 1, 2], [1, 2, 1], [2, 1, 1], [1, 2, 2], [2, 1, 2], [2, 2, 1], [1, 1, 1] |
| ]) { |
| // decorate with offset, but sort by value |
| var input = Array($0.enumerated()) |
| input._sort3(0, 1, 2) { $0.element < $1.element } |
| // offsets should still be ordered for equal values |
| expectTrue(isSorted(input) { |
| if $0.element == $1.element { |
| return $0.offset < $1.offset |
| } |
| return $0.element < $1.element |
| }) |
| } |
| |
| suite.test("heapSort") { |
| // Generates the next permutation of `num` as a binary integer, using long |
| // arithmetics approach. |
| // |
| // - Precondition: All values in `num` are either 0 or 1. |
| func addOne(to num: [Int]) -> [Int] { |
| // `num` represents a binary integer. To add one, we toggle any bits until |
| // we've set a clear bit. |
| var num = num |
| for i in num.indices { |
| if num[i] == 1 { |
| num[i] = 0 |
| } else { |
| num[i] = 1 |
| break |
| } |
| } |
| return num |
| } |
| |
| // Test binary number size. |
| let numberLength = 11 |
| var binaryNumber = Array(repeating: 0, count: numberLength) |
| |
| // We are testing sort on all permutations off 0-1s of size `numberLength` |
| // except the all 1's case (its equals to all 0's case). |
| while !binaryNumber.allSatisfy({ $0 == 1 }) { |
| var buffer = binaryNumber |
| buffer._heapSort(within: buffer.startIndex..<buffer.endIndex, by: <) |
| expectTrue(isSorted(buffer, by: <)) |
| binaryNumber = addOne(to: binaryNumber) |
| } |
| } |
| |
| runAllTests() |
| |