Swift 中的 TimSort

Question

我正在尝试在 Swift 中实现 TimSort。我已经提到了这两个链接：This and this 我转换为 Swift 的代码是：

import UIKit

class ViewController: UIViewController {

var arr : [Int] = []
let run : Int = 5

override func viewDidLoad() {
    super.viewDidLoad()
    for _ in 0..<10 {
        arr.append(Int(arc4random_uniform(100)))
    }
    timSort()
}

override func didReceiveMemoryWarning() {
    super.didReceiveMemoryWarning()
    // Dispose of any resources that can be recreated.
}

func insertionSort(_ array:[Int]) -> [Int] {
    var a = array
    for x in 1..<a.count {
        var y = x
        while y > 0 && a[y] < a[y - 1] {
            a.swapAt(y - 1, y)
            y -= 1
        }
    }
    return a
}

func merge(leftPile: [Int], rightPile: [Int]) -> [Int] {
    var leftIndex = 0
    var rightIndex = 0

    var orderedPile = [Int]()

    while leftIndex < leftPile.count && rightIndex < rightPile.count {
        if leftPile[leftIndex] < rightPile[rightIndex] {
            orderedPile.append(leftPile[leftIndex])
            leftIndex += 1
        } else if leftPile[leftIndex] > rightPile[rightIndex] {
            orderedPile.append(rightPile[rightIndex])
            rightIndex += 1
        } else {
            orderedPile.append(leftPile[leftIndex])
            leftIndex += 1
            orderedPile.append(rightPile[rightIndex])
            rightIndex += 1
        }
    }

    while leftIndex < leftPile.count {
        orderedPile.append(leftPile[leftIndex])
        leftIndex += 1
    }

    while rightIndex < rightPile.count {
        orderedPile.append(rightPile[rightIndex])
        rightIndex += 1
    }

    return orderedPile
}

func timSort() {
    print("Unsorted : \(arr)")
    for i in stride(from: 0, to: arr.count, by: run) {
        print("i : \(min((i + run),(arr.count)))")
        arr.replaceSubrange(i..<min((i + run),(arr.count)), with: insertionSort(Array(arr[i..<min((i + run),(arr.count))])))
    }
    print("after insertion sort \(arr)")

    var runCount = run
    while runCount < arr.count{
        for x in stride(from: 0, to: arr.count, by: 2 * runCount) {
            print("x : \(x) runcount \(runCount) calc : \(x + 2 * runCount)")
            arr.replaceSubrange(x..<min((x + 2 * runCount),(arr.count)), with: merge(leftPile: Array(arr[x..<(x + runCount)]), rightPile: Array(arr[(x + runCount)..<min((x + 2 * runCount),(arr.count))])))
        }
        runCount = runCount * 2
    }

    print("Sorted : \(arr)")
}
}

我面临的问题是，当我在两个链接中执行代码时，它适用于任何运行值（如 run = 7），但同样的情况并没有发生在我的代码。

我的代码只有在 run = 5 和 arr.count = 10 时才能正常工作。在所有其他情况下，它会在 arr.replaceSubrange(x..<min((x + 2 * runCount),(arr.count)), with: merge(leftPile: Array(arr[x..<(x + runCount)]), rightPile: Array(arr[(x + runCount)..<min((x + 2 * runCount),(arr.count))]))) 这一行崩溃。

我尝试了各种解决方法，但无法解决问题。请有人帮我指出一下。

Answer 1

您还需要进行几次 min 检查。在你最后的while循环中，x + runCount可以超过arr.count，所以x + runCount需要替换成min(x + runCount, arr.count)。添加了 min 检查后，代码现在可以针对 run 和 arr.count:

的各种大小运行

func timSort() {
    print("Unsorted : \(arr)")
    for i in stride(from: 0, to: arr.count, by: run) {
        print("i : \(min((i + run),(arr.count)))")
        arr.replaceSubrange(i..<min((i + run),(arr.count)), with: insertionSort(Array(arr[i..<min((i + run),(arr.count))])))
    }
    print("after insertion sort \(arr)")

    var runCount = run
    while runCount < arr.count{
        for x in stride(from: 0, to: arr.count, by: 2 * runCount) {
            print("x : \(x) runcount \(runCount) calc : \(x + 2 * runCount)")
            arr.replaceSubrange(x..<min(x + 2 * runCount, arr.count), with: merge(leftPile: Array(arr[x..<min(x + runCount, arr.count)]), rightPile: Array(arr[min(x + runCount, arr.count)..<min(x + 2 * runCount, arr.count)])))
        }
        runCount = runCount * 2
    }

    print("Sorted : \(arr)")
}

Answer 2

从 Swift 5.0 开始，'sort()' 方法使用 timsort 作为其默认实现。您可以在 Here

中找到更多相关信息

Swift 中的 TimSort

TimSort in Swift

timsort

swift