swift - 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，所以 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)")
}