# Swaps Used in Selection Sort

I was trying to come up with a formula for the number of swaps used in selection sort. So we know that selection sort gives the minimum number of swaps to sort an array.

The formula I came up with is given an unsorted array and it's descending or ascending order. We find the number of elements dissimilar to the sorted array. When we subtract 1 from this number we can get the number of swaps.

For example, Let the array be

[3, 4,2 ,9,1]

Using selection sort for descending order:

[9,4,2,3,1] ---[9,4,3,2,1] which gives a total of 2 swaps

My logic:

Descending array is [9,4,3,2,1]. So three elements are in incorrect position which are 9, 3 and 2. So, 3-1 = 2 swaps.

Let us consider ascending order:

Section sort:

[1,4,2,9,3]--[1,2,4,9,3]--[1,2,3,9,4]--[1,2,3,4,9] which gives a total of 4 swaps.

My logic:

Ascending array is [1,2,3,4,9]. So all five elements are in incorrect position from the sorted array which gives a total swap count of 5-1 = 4.

But my logic seems to be incorrect when tested on hacker rank. Could you give me an example where this logic fails. Thanks :)

• "So we know that selection sort gives the minimum number of swaps to sort an array." -- citation needed. – Raphael Sep 21 '17 at 5:59
• The problem with your logic is there is no logic. You are saying something about a five-element array. In algorithm analysis, you need to say something about all arrays. – Raphael Sep 21 '17 at 6:00
• Have you tried generating all permutations of short lists, selection-sorting them, and counting the number of swaps? – adrianN Sep 21 '17 at 10:24

Considering following array [5,4,3,2,1]

Now for ascending order, four elements are in incorrect position i.e. 5,4,2 and 1

So according to your logic, No of swaps = No. of elements at incorrect position - 1 therefore No. of swaps = 4-1 i.e. 3

Now, according to Selection sort,

[5,4,3,2,1] Original Array

1st Pass: [1,4,3,2,5] i.e. 1 swap

2nd Pass: [1,2,3,4,5] i.e. 2 swaps

We are done, with Only 2 swaps not 3 swaps.

Similarly for Descending order,

Now, according to Selection sort,

[1,2,3,4,5] Original Array

1st Pass: [5,2,3,4,1] i.e. 1 swap

2nd Pass: [5,4,3,2,1] i.e. 2 swaps

We are done, with Only 2 swaps not 3 swaps.

Hope this helps !

• This shows that the formula suggested by the OP is wrong. What is the correct formula? – Yuval Filmus Sep 22 '17 at 9:30
• @YuvalFilmus I actually didn't think about it but i searched for it because of your question. Thanks. I think this link GeeksForGeeks explains it very well – rdj7 Sep 22 '17 at 11:10