swift - 插入排序和冒泡排序如何统计比较次数和交换次数？ ( swift )

Question

我正在尝试创建两个函数来对数组进行排序——第一个用于冒泡排序，第二个用于插入排序。它们不仅应该返回排序后的数组，还应该返回排序过程中发生的比较和交换的次数。我该怎么做？

这是我当前的代码:

func insertionSort(a: [Int]) -> (comparisonsCount: Int, swapsCount: Int, sortedArray: [Int]) {
    guard a.count > 1 else { return (0, 0, a) }

    var comparisons = 0
    var swaps = 0
    var b = a

    for i in 1..<b.count {
        var y = i

        while y > 0 && b[y] < b[y - 1] {
            b.swapAt(y - 1, y)
            y -= 1

        }
    }

    return (comparisons, swaps, b)
}

func bubbleSort(a: [Int]) -> (comparisonsCount: Int, swapsCount: Int, sortedArray: [Int]) {

    var b = a
    var comparisons = 0
    var swaps = 0

    for i in 0..<a.count-1 {
        for j in 0..<a.count-i-1 {

            if(b[j] > b[j+1]) {
                let temp = b[j]
                b[j] = b[j+1]
                b[j+1] = temp
                swaps += 1
            }

            comparisons += 1

        }
    }

    return (comparisons, swaps, b)

}

Answer 1

func insertionSort(a: [Int]) -> (comparisonsCount: Int, swapsCount: Int, sortedArray: [Int]) {
guard a.count > 1 else { return (0, 0, a) }

var comparisons = 0 
var swaps = 0
var b = a
for i in 1..<b.count {
    var y = i
    comaprisons += 2 // two comparison in while and it will happen at least once
    while y > 0 && b[y] < b[y - 1] {
        b.swapAt(y - 1, y)
        y -= 1
        swaps += 1
        comparisons += 2
    }

    if (y == 0){
       comparisons -= 1  // && Operator short circuiting explanation below
    }
}

 return (comparisons, swaps, b)
}

&& 和 ||运算符都是短路运算符。因此，如果在内部 while 循环中输入 y -= 1 会导致 y==0 。在这种情况下 b[y] < b[y - 1] 这种比较不会发生。这就是为什么比较减少了 1