Swift中的TimSort

Question

我正在尝试在Swift中实现TimSort。我引用了这两个链接：This和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，因此需要用min(x + runCount, arr.count)替换x + runCount。添加了这些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中找到有关它的更多信息