0
$\begingroup$

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

$\endgroup$
3
  • 2
    $\begingroup$ "So we know that selection sort gives the minimum number of swaps to sort an array." -- citation needed. $\endgroup$
    – Raphael
    Sep 21, 2017 at 5:59
  • 1
    $\begingroup$ 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. $\endgroup$
    – Raphael
    Sep 21, 2017 at 6:00
  • $\begingroup$ Have you tried generating all permutations of short lists, selection-sorting them, and counting the number of swaps? $\endgroup$
    – adrianN
    Sep 21, 2017 at 10:24

2 Answers 2

2
$\begingroup$

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 !

$\endgroup$
2
  • $\begingroup$ This shows that the formula suggested by the OP is wrong. What is the correct formula? $\endgroup$ Sep 22, 2017 at 9:30
  • $\begingroup$ @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 $\endgroup$
    – rdj7
    Sep 22, 2017 at 11:10
-1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ I see some LinearSort(). I don't see the relation to Selection Sort. $\endgroup$
    – greybeard
    Jan 15, 2022 at 16:03
  • $\begingroup$ This algorithm is not Selection Sort. $\endgroup$
    – Nathaniel
    Jan 23, 2022 at 10:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.