Swaps Used in Selection Sort

Question

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

Answer 1

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 !

Answer 2

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;
}