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
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:
[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.
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 :)