Insertion sort performance

[huangboju]

I tested it a faster

a.

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

b.

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

[hollance]

How did you test it?

[huangboju]

[hollance]

I was looking for answers like these: Is this in release mode? With all optimizations on? On what device? How many times did you repeat the experiment? How big is the difference? Does the size of the array matter? And so on...

[antonio081014]

This is an interesting one. I used the two insertionSort functions, here is a snippet of the test code:

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

    func insertionSort2(_ array: [Int]) -> [Int] {
        var a = array
        for x in 1..<a.count {
            var y = x
            let temp = a[y]
            while y > 0 && temp < a[y - 1] {
                a[y] = a[y - 1]                // 1
                y -= 1
            }
            a[y] = temp                      // 2
        }
        return a
    }

    func testPerformance() {
        var aWins = 0
        var bWins = 0
        var ties = 0

        for index in 0..<50 {
            print("Round: \(index + 1)")
            let list: [Int] = (0..<10000).map { _ in
                return Int(arc4random() % 10000)
            }

            let timestamp1 = CACurrentMediaTime()
            let _ = insertionSort1(list)
            let timestamp2 = CACurrentMediaTime()
            let _ = insertionSort2(list)
            let timestamp3 = CACurrentMediaTime()
            if timestamp3 - timestamp2 > timestamp2 - timestamp1 {
                aWins += 1
            } else if timestamp3 - timestamp2 < timestamp2 - timestamp1 {
                bWins += 1
            } else {
                ties += 1
            }
        }
        print("A Wins: \(aWins)")
        print("B Wins: \(bWins)")
        print("Ties: \(ties)")
    }

The result is

Round: 50 A Wins: 50 B Wins: 0 Ties: 0 Which is the same as @huangboju mentioned above.

Here are few things I need to mention:

1. Use the debug mode, which has no optimizations.
2. Use the same input data.
3. Test on iPad Air.

According to Swift Doc,

Both parameters must be valid indices of the collection that are not equal to endIndex. Calling swapAt(::) with the same index as both i and j has no effect. Complexity: O(1)

and Swift Source Code of swapAt, the complexity of this function(swapAt) should be O(1), so is the implementation of 2nd one(a[y] = a[y - 1]).

Also confused, anyone knows why?

[hollance]

It's not that useful to do speed tests in debug mode. ;-) I'm curious what sort of results you find in release mode.

[antonio081014]

Interesting, under release mode. Here is the result: A Wins: 0 B Wins: 50 Ties: 0

The manually swap will beat the system call.