Swap integers algorithm

Question

I study algorithms and try to swap integers in an array using Swift, I know it is efficient to use the "swap" function, but I am trying to learn different approaches. So I try to use different methods, and I don’t understand anything - I have an array of 200 int 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 takes 7 seconds and the swap code works 7282 (or so) 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) } 

Does it work only 198 times in 1.3 seconds?

I don’t understand why there are so many different runs. It appears only in sorting. There are no such differences in the number of runs if I use, for example, bubble sorting.

Answer 1

After further consideration, I think I found the problem. The first sort will have to move the number many times to get it in the correct position. The second sort moves several numbers at the same time, because the insert will push the other numbers forward in the array. I checked it with an array of 5 integers.

Here is the debugger before the first sorting method begins:

Note that 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 right position, but 4 is now far from its right position. He will have to repeat this and move 4 times until he reaches his final position. The next swap is as follows

Now 14 was moved before 17, as it should, but it is still far from the correct position. Therefore, it will need to be moved again!

---

Let's look at the second sorting method.

Here's what it looks like before sorting

and after the first swap it looks like

Now you can see that after ONLY ONE swap 3 and 4 are in the correct positions. 3 was moved only once, and because of this, it was moved before 4, which moved 4 to the correct position.

Now after the next exchange ...

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

The second method moves several numbers by pushing the numbers back one index each time it inserts ...

example: 4,17,14,3,20

• 4 currently has an index of 0
• 17 is currently at index 1
• 14 currently has an index of 2

if I insert 3 in front ...

3,4,17,14,3,20

now delete the previous 3 ...

3,4,17,14,20

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

Answer 2

The methods are completely different.

The first one makes a simple exchange each time array[j] < array[i] , as you expect.

Second, when array[j] < array[i] true, it moves array[j] to the i position, and shifts the rest of the array by one position .

Having said that, I had a little time on my hands, so I decided to write your algorithms in Swift 3 (note how you can avoid using temp ):

 func selectionSort(_ array: [Int]) { var array = array for i in 0..<array.count { for j in i+1..<array.count { if array[j] < array[i] { (array[j], array[i]) = (array[i], array[j]) } } } print(array) } func selectionSort2(_ array: [Int]) { var array = array for i in 0..<array.count { for j in i+1..<array.count { if array[j] < array[i] { array.insert(array[j], at: i) array.remove(at: j+1) } } } print(array) } 

Hooray!