Swap integers algorithm

Question

I am learning algorithms and try to to swap to integers in an array using Swift, I know that it is effective to use 'swap' function but I try to learn different approaches. So I try different methods and I don't understand one thing - I have an array of 200 ints and when I use this method:

func selectionSort(var array: [Int]) {
 print("Selection Sort")
 for i in 0..<array.count {
    for j in i+1..<array.count {
        if array[j] < array[i] {
            let temp = array[j] //runs 7282 times
            array[j] = array[i] // runs 7282 times
            array[i] = temp     // runs 7282 times
        }
    }
 }
 print(array)
}

it runs for 7 seconds and swap code runs 7282 (or so) times, but when I use this:

func selectionSort(var array: [Int]) {
  print("Selection Sort")
  for i in 0..<array.count {
    for j in i+1..<array.count {
        if array[j] < array[i] {
            array.insert(array[j], atIndex: i)
            array.removeAtIndex(j+1)

        }
    }
  }
  print(array)
}

it runs only 198 times in 1.3 seconds?

I don't get why there is such different in number of runs? It appears only in selection sort. There is no such differences in number of runs if I use ,for example, bubble sort.

Answer 1

Upon further review I think I found the problem. The first sort will have to move the number many times to get it in its correct position. The second sort moves multiple numbers at the same time because the insert will push other numbers forward in the array. I tested it out with an array of 5 integers.

Here is the debugger before the first sort method begins:

Notice how 3 is far from its correct position, now after the first method sorts once, the array now looks like this

Now 3 is in the correct position, but 4 is now far from its correct position. It will have to repeat this and move 4 many times until it gets to its final position. The next swap looks like this

Now 14 was moved in front of 17 as it should, but its still far from its correct position. So it will have to be moved again!

---

Let's look at the second sort method.

Here's what it looks like before the sort

and after the first swap it looks like this

Now you can see that after just ONE swap, 3 AND 4 are in the correct positions. 3 was moved just one time, and because of this, it was moved in front of 4, which moved 4 to its correct position.

Now after one more swap...

Now you can see that it already is correctly sorted after 2 swaps using the second method, but it took the first method 4 swaps. The difference only grows when you have a larger array.

The second method moves multiple numbers by pushing numbers back by one index every time it inserts...

an example: 4,17,14,3,20

• 4 is currently at index 0
• 17 is currently at index 1
• 14 is currently at index 2

if i insert 3 in the front...

3,4,17,14,3,20

now remove the previous 3...

3,4,17,14,20

• 4 is now at index 1!
• 17 is now at index 2!
• 14 is now at index 3!