Bubble sorting an array in Swift, compiler error o

问题:

I wrote a really simple bubble sort for a card game. It takes an array of "Card" objects, each of which has a an "order" attribute which indicates the value to be sorted against for the game in question.

The following code stopped compiling some time between Swift Beta 1 and Beta 6, and I'm not exactly sure why.

 ///Sort the cards array by order
  func sortCards(cards: Array<Card>) -> Array<Card> {
    var sorted = false
    while sorted == false {
      sorted = true
      for i in 0...cards.count - 2 {
        if cards[i].order > cards[i+1].order {
          sorted = false
          var first = cards[i]
          var second = cards[i + 1]
          cards[i] = second    //ERROR
          cards[i + 1] = first //ERROR
        }
      }
    }
    return cards
  }

The lines where the swap occurs bombs out with a very cryptic message:

@!value $T5 is not identical to 'Card'

What changed, and what am I doing wrong here?

Bonus question: How am I supposed to understand the error message?

回答1:

If you declare the function like this, then the array is inmutable. You need to use the keyword inoutlike this:

func sortCards(inout cards: Array<Card>) -> Array<Card> {
//code
}

Then you call it with &:

sortCards(&myArray)

Explanation

The whole model of Arrays and pass by value/reference has changed during the beta process.

In beta 1 arrays passed into subroutines were only kind of passed by value. Arrays passed by value (and let arrays) were still modifiable as long as you didn't change the length of the array, thus breaking the pass-by-value rules and allowing your original code to work.

In beta 4 I believe it was, they changed arrays to effectively always be passed by value and changed constant arrays (let) do be truly unmodifiable, which resulted in your code not working and breaking in the compile phase.

The inout keyword changes the array to be passed by reference instead of by value and changes it from being implicitly defined with let to defined with var, which means the array is now mutable, and changes to the array are seen by the caller.

回答2:

Function parameters are by default constant (as if declared with let). If you want to modify the parameter inside your function, you have to declare it as a variable:

func sortCards(var cards: Array<Card>) -> Array<Card> { ...

Note that only the local parameter cards is modified, not the array passed as an argument to the function (which seems to be your intention because the function returns a new array).

回答3:

I played with the following using swift 3. Hope it'll help some people who come here.

bubble sort:

func bubble(arr: inout [Int]) {
    for i in (1..<arr.count).reversed() {
        for j in 0..<i where arr[j] > arr[j + 1] {
            swap(&arr[j], &arr[j + 1])
        }
    }
}

using stride:

func bubbleStride(arr: inout [Int]) {
    for i in stride(from: arr.count - 1, to: 1, by: -1) {
        for j in 0..<i where arr[j] > arr[j + 1] {
            swap(&arr[j], &arr[j + 1])
        }
    }
}

using while:

func bubbleWhile(arr: inout [Int]) {
    var i = arr.count - 1
    while(i > 0) {
        var j = 0
        while(j < i) {
            if arr[j] > arr[j + 1] {
                swap(&arr[j], &arr[j + 1])
            }
            j += 1
        }
        i -= 1
    }
}

This can be used to generate a random array of integers:

import Cocoa

func ints(cnt: Int, ceiling: Int) -> [Int] {
    let arr = Array(repeating: 0, count: cnt)
    return arr.map { _ in Int(arc4random_uniform(UInt32(ceiling))) }
}

E.g.:

let a = ints(cnt: 10, ceiling: 100)
print(a)

var b = a
bubble(arr: &b)
print(b)

output:

[13, 30, 68, 19, 1, 4, 28, 65, 96, 13]
[1, 4, 13, 13, 19, 28, 30, 65, 68, 96]

回答4:

Here is bubble sort implemented in swift 4.0.2

var array = [15,11,20,14,12,13,17,16,18,19]
var sortedArray = Array(array)
var sortedAboveIndex = array.count 

for i in 0 ..< sortedAboveIndex-1 {

  for j in 0 ..< sortedAboveIndex-i-1 {

      if (sortedArray[j] > sortedArray[j+1]) {

          sortedArray.swapAt(j, j+1)        
      }
  }

}

print(sortedArray)

if any queries on above code please comment below

回答5:

The function always runs O(n^2) time even if the array is sorted. It can be optimized by stopping the algorithm if inner loop didn’t cause any swap.

func main() {
    var array: [Int] = [1, 3, 15, 6, 8, 12, 10, 33, 2, 88]
    var swapped = false

    for i in 0..<array.count {
        for j in 0..<array.count - i - 1 {
            if array[j] > array[j + 1] {
//                let temp = array[j]
//                array[j] = array[j+1]
//                array[j+1] = temp
                array.swapAt(j, j + 1)
                swapped = true
            }
        }

        if swapped == false {
            break
        }
    }

    print(array)
}