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 :)
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 !