# 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. Commented Sep 21, 2017 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. Commented Sep 21, 2017 at 6:00
• Have you tried generating all permutations of short lists, selection-sorting them, and counting the number of swaps? Commented Sep 21, 2017 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? Commented Sep 22, 2017 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
Commented Sep 22, 2017 at 11:10

The correct formula for counting the number of swaps in a selection sort algorithm is not (n-1) but it is { n*(n-1)/2 }, where n is the length of an array.

Example: Let's consider an array of [0,1,2,3,4,5,6,7,8,9,10,11,12,13,23,34], which is sorted in ascending order. if we sort it in descending order, then it will experience the worst-case scenario and It will follow the following formula to count the possible number of swaps.

n=16; Swaps = ( n * ( n - 1) )/ 2 => ( 16 * ( 16 - 1 ) )/2 => 8 * 15 => 120

So in a worst-case scenario, there are no (n-1) swaps at all.

Algorithm:

function LinearSort(arr){
for (var i=0; i<arr.length;i++){
for(var j=0; j<i;j++){
if(arr[i]<arr[j]){
swap(i,j);
//  console.log("i="+i+"\tj="+j);
}
}
}
return arr;
}
function swap(x,y){
swaps+=1;
var temp = myArr[x];
myArr[x]= myArr[y];
myArr[y]= temp;
}


• I see some LinearSort(). I don't see the relation to Selection Sort. Commented Jan 15, 2022 at 16:03
• This algorithm is not Selection Sort. Commented Jan 23, 2022 at 10:46